fibonacci algorithm?

[rabidmachine9]

Hello there,
I implemented this small algorithm for fibonacci numbers calulation.
But after fibonacci number 50 more or less it gives a wrong output
Its probably because the variable defined cant handle such big numbers
Is there a way to get over this problem?
Is there a variable in c++ bigger than unsigned long for integers?
Here is the code:


#include<iostream>
using namespace std;


int main()
{
unsigned long fibo[30] = {0,1};
cout << "The size of an unsinged long is " << sizeof(unsigned long) << endl;

for(int index = 0; index < 30; index++)
{

if(index == 0)
{ fibo[index] = 0;
cout << "Fibo " << index << ":" << fibo[index] << endl;
}
else if(index == 1)
{fibo[index] = 1;
cout << "Fibo " << index << ":" << fibo[index] << endl;
}
else
{
fibo[index] = fibo[index - 1] + fibo[index -2];

cout << "Fibo " << index << ":" << fibo[index] << endl;
}

}


return 0;

}

[kevinchkin]

Well size of unsigned long is 4 bytes (on GCC compiler), Try double it's 8 bytes

[turbozedd]

You may be able to use "unsigned long long". double only has 12 digits of accuracy (depends on your system). "long double" has 17 digits of accuracy (again dependent) and you may not have it. Floating point numbers (float, double, long double) are not good for what you are doing. You cant use it because you will have only 12 digits and a power, then next fib number will be wrong.

If you don't have long long you may want to make a multiprecision number class or struct. A simple way is to use an array and give it a size with the number of digits you want you number to hold. Ex: I want to have an Integer with 1000 digits, so I declare short myInt[1000];. This wastes some space if you use base ten, but you wont have to do base conversions. Then you have to write methods for addition etc. and keep track of carrying, borrowing etc. since you are only adding it shouldn't be too hard. If you want to have more fun, write all the operation methods, and extend your "Integer" class to a "Rational" class and again to a "Real" class. I'm sure theres alot of stuff on this if you check. Your problem as it stands really only needs an array and an addition operation (with carrying). You can always make things more sophisticated if you want.

Another option is to store the numbers modulo N and then resolve the actual value yourself. N should be large, like one bigger than the largest unsigned long long.