### 100 Fibonacci numbers

Is it even possible to store the 100th Fibonacci number (beginning with the numbers 1 and 1) into a variable? I know the number is pretty huge, and wondered if there is a data type to hold a number that big.
I do not know how large it is but a long long int should store it.
After about the 48th number, I start getting some negative numbers. Anyone have any ideas? I will post the code.
 ``123456789101112131415161718192021222324252627282930313233343536373839`` ``````#include #include using namespace std; int computeFibonacciNums(int, int, int); int main() { long long number; cout << "Hello" << endl; for (int i = 0; i < 100; i++) { number = computeFibonacciNums(1, 1, i + 1); cout << number << endl; } return 0; } int computeFibonacciNums (int first, int second, int position) { if (position == 1) { return first; } else if (position == 2) { return second; } else { return computeFibonacciNums(first, second, position - 1) + computeFibonacciNums(first, second, position - 2); } }``````
`uint64_t` I think...

E: This one is right up to the 93rd fib

 ``12345678910111213141516171819`` ``````#include typedef uint64_t u64_t; int main() { u64_t start = 0; u64_t next = 1; u64_t _new; for (int r = 1; r < 93; r++) { _new = next + start; start = next; next = _new; } cout << next << endl; }``````

 `12200160415121876738`

Easiest way to do this is python or ruby because of their arbitrary precision calculators

E: Using BigInteger library

 ``12345678910111213141516171819`` ``````#include #include using namespace std; int main() { BigInteger start = 0; BigInteger next = 1; BigInteger _new; for (int r = 1; r < 1000; r++) { _new = next + start; start = next; next = _new; } cout << next << endl; }``````

 ```43466557686937456435688527675040625802564660517371780 402481729089536555417949051890403879840079255169295922593080 322634775209689623239873322471161642996440906533187938298969 649928516003704476137795166849228875```
Last edited on
Wow, and I thought recursion was the best way. Thanks.
The 100th Fibonacci number (beginning with the numbers 1 and 1) is 354224848179261915075
http://planetmath.org/ListOfFibonacciNumbers.html

Compile and run this program on your implementation; if the second number printed out is smaller than the first one, you would need to use a user defined big integer type. If an approximate value is adequate, a floating point type can be used.

 ``123456789`` ``````#include #include #include int main() { std::cout << "354224848179261915075" << '\n' << std::numeric_limits::max() << '\n' ; }``````

> and I thought recursion was the best way.

It is as good a way as iteration. Particularly if it is tail call recursive.
Taking logarithm of the 100th fibonacci number (354224848179261915075) in the base 2 gives 68.2632273156
Hence, 69 bits are required to store this number.

It seems you have to use two long longs to store this number.
Last edited on
Topic archived. No new replies allowed.