Thread: Large Fibonacci

Sure is, I'm pretty sure you can use an array of any type you want other than float or double or long double. The best ones to use will probably be char or unsigned char, but it's up to you. Since finbonacci only requires addition, it shouldn't be too difficult to write a routine that does long addition, using the elements of each array as the ones/tens/etc. digits.

However, unless you want to just use huge arrays and hope they're big enough to hold your largest number, you'll need to use dynamic memory, which can get unnecessarily messy. As such, if at all possible (i.e. it's allowed, and you know about them or are willing to read up about them on this site's tutorials), I highly recommend you use either std::string or std::vector<char> or std::vector<unsigned char> instead of an array.

Good luck

I'm pretty sure that the big number libraries also use arrays(or vectors). The detalis could be hidden from you, but there's really no other way to do it. The hard thing about big numbers isn't so much storing them... the tricky part is the mathmematical operations. You need special functions and/or you need to overload the operators. The big-number math functions are the most valuable part of the big number library!

If this is a homework assignment, there should be some hints from your studies/book/lecture about to approach the assignment. Maybe you can ask your instructor for a hint... You are probably not supposed to use a big number library.

Maybe this is a "trick" assignment designed to show you (or remind you of) the limits of your system. (???) The first time I heard of Fibonacci was in an example of recursion. I seem to remember the book said you could overflow the stack by calling the function too many times.

>>I'm pretty sure that the big number libraries also use arrays
Hmm, that would probably be simplest to implement, and might be more efficient speed-wise.. but I would imagine that the possibility is still there that they store/manipulate numbers in binary using bitwise operations or whatnot? In terms of memory usage, it would hold 25.6^n times as large a number in the same space as if you used arrays (n == size in bytes).

Using an array of unsigned char types and actually using the full binary representation of the number (as opposed to trying to force a decimal representation) is certainly the most efficient in terms of storage space and speed.

Also, if all you need this for is to compute large Fibonacci numbers, the only operation you will need is addition. This is rather nice, because you know that the length in (digits/bits/etc) of the sum will be at most one bit/digit/etc more than your largest operand, which will make the coding less messy.

Unless you want to implement the constant-time direct Fibonacci computation.

The Wikipedia entry for Fibonacci numbers explicitely mentions a good approach for bignum libraries:
http://en.wikipedia.org/wiki/Fibonacci_number

I once had this code nicely obfuscated at flashdaddee.

Code:

#include <stdio.h>
#include <string.h>

#define SIZE 4096

char A[SIZE] = "0";
char B[SIZE] = "1";
char C[SIZE];

int main(void)
{
   int i = 2, carry = 0;
   printf("fibonacci(0) = %s\n", A);
   printf("fibonacci(1) = %s\n", B);
   while ( i <= 10000 )
   {
      char *a = A, *b = B, *c = C;
      for ( ;; )
      {
         int sum = 0;
         if ( *a )
         {
            sum += *a - '0';
            ++a;
         }
         if ( *b )
         {
            sum += *b - '0';
            ++b;
         }
         sum += carry;
         carry = sum > 10;
         if ( !sum && !*a && !*b )
         {
            break;
         }
         else if ( sum > 9 )
         {
            carry = 1;
            sum -= 10;
         }
         else
         {
            carry = 0;
         }
         *c++ = sum + '0';
         if ( c >= &C[sizeof(C)] )
         {
            puts("too big");
            return 0;
         }
      }
      *c = '\0';

      printf("fibonacci(%d) = ", i++);
      while ( --c >= C )
      {
         putchar(*c);
      }
      putchar('\n');

      strcpy(A,B);
      strcpy(B,C);
   }
   fflush(stdout);
   return 0;
}

[edit]Works best if output is piped to a file.
[edit too]The file ends up about 10,650,846 bytes.

Code:

carry = sum > 10;
...
>>else if ( sum > 9 )
{
    carry = 1;

It looks to me like the carry = 1; can be taken out, and the sum > 10 should be sum > 9?

Code:

else
{
    carry = 0;
}

Similarly, this seems to be unnecessary.

Code:

if ( *a )

Doesn't this assume that all elements past the end of the string are '\0'? I'm not sure that assigning an initial string to A and B automatically zeroes all other elements.

Otherwise, that seems to do the job very nicely with fixed-length arrays

>It looks to me like the carry = 1; can be taken out, and the sum > 10 should be sum > 9?
>Similarly, this seems to be unnecessary.

Ya know, it's been so damn long that I've been trying to figure this code out since I posted it.

[edit]You are right. That section might be written like this.

Code:

         sum += carry;
         if ( !sum && !*a && !*b )
         {
            break;
         }
         carry = sum > 9;
         if ( carry )
         {
            sum -= 10;
         }
         *c++ = sum + '0';

The *a part though checks to see whether the first number is shorter (in digits) than the second.
[/edit]

>Doesn't this assume that all elements past the end of the string are '\0'? I'm not sure that assigning an initial string to A and B automatically zeroes all other elements.

That I know -- it does.

>Otherwise, that seems to do the job very nicely with fixed-length arrays

Thank you.

[I still gotta try to figure this code out though.
One thing I think I figured out is that the strings are stored "backwards".]

Alright guys this is my first attempt at it. I am a begginner and my logic is probably flawed but before I continue can you please look this over. I also cant seem to fix this error message that says error C2064: term does not evaluate to a function taking 4 arguments and it points to my sum function in main. So here it is :

Code:

#include "stdafx.h"

#using <mscorlib.dll>
using namespace System;

void sum(Int32[],Int32 [],Int32[], int);
void copy(Int32 [], Int32[]);
void print(Int32 []);

int _tmain()
{
	Int32 f[] = new Int32[1000];
	Int32 s[] = new Int32[1000];
	Int32 sum[] = new Int32[1000];
	
	f[0]=1;
	s[0]=1;

	Console::WriteLine(S"Input N: ");
	int n =Int32::Parse(Console::ReadLine());
	
	sum(sum,f,s,n);

	return 0;
}

void sum(Int32 su[], Int32 fir[], Int32 sec[], int nv) {

	int sum,carry;
	for(int i=carry=0; i<=nv; i++){
		sum = fir[i] + sec[i] + carry;
		su[i]=sum%10;
		carry = sum/10;
		copy(sec,fir);
		copy(su,sec);
	}
print(su);
}

void copy(Int32 a[], Int32 b[]){

	for(int i=0; i<a->Length; i++)
		a[i] = b[i];
}

void print(Int32 b[]){

for(int i=0; i<b->Length; i++)
Console::WriteLine(S"{0}",b[i].ToString());
}

I'ts probably because you have a function called sum and an array called sum so when you use the line:

sum(sum, f, s, n);

it can't tell the sum used as the first parameter to the function called sum from the function called sum. I'd try changing the array name or the function name to see what happens.

cool that fixed the area but the numbers arent being generated the first element is always one and by default every other element is zero. So it prints 10000000000000000000 etc every time. I am probably not storing the sum correctly.

[Edit] I think see my problem let me try to fix it.

try calling the print function after assigning 1 to f[0] and s[0] back in main() to be sure the correct values are assigned where you think they are, and that you can retrieve them appropriately there before passing them to sum(). The syntax you are using for the print function is not known to me, particularly, I don't know what S"{0}", means/does.

Some other concerns:
you have a variable called sum in the sum function. Change one or the other, unless you've already done so.

I also think you might want to change this:

Code:

a[i] = b[i];
 
to this:
 
b[i] = a[i];

in copy, but you'll have to confirm that.