100 Fibonacci numbers

[Joseph Fiddler]

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.

[Script Coder]

I do not know how large it is but a long long int should store it.

[Joseph Fiddler]

After about the 48th number, I start getting some negative numbers. Anyone have any ideas? I will post the code.

#include <iostream>
#include <string>

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);
    }
}

[Smac89]

uint64_t I think...

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

#include <iostream>

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

#include <iostream>
#include <bigint/BigIntegerLibrary.hh>
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

[Joseph Fiddler]

Wow, and I thought recursion was the best way. Thanks.

[JLBorges]

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.

#include <iostream>
#include <cstdint>
#include <limits>

int main()
{
    std::cout << "354224848179261915075" << '\n'
              << std::numeric_limits<std::uintmax_t>::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.

[eklavya sharma 2]

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.