Fibonacci large sum problem

Question

It works for small integers but not for large integers.Can anybody help me?
https://code.sololearn.com/cm31LUiU5Tii/?ref=app

Answer 1

a 64-bit two's complement type (which is almost certainly what the "long long" type is in your case) has enough capacity to store the 92nd fibonacci number:

9223372036854775807 → largest 64-bit two's complement
7540113804746346429 → 92nd fibonacci number

but the 93rd one is too large for it: 12200160415121876738 → 93rd Fibonacci number.

If you want to calculate fibonacci numbers beyond the 92nd, you'll need a "wider" data type, one able to handle larger numbers. switching to unsigned long long will allow you to to calculate the 93rd ( 18446744073709551615 → largest 64-bit unsigned) but nothing beyond that.

by switching to "unsigned long long" the negative result won't go any more (since it's unsigned) but it will still give an erroneous result since the 94th seems to be smaller than the 93rd, something that's clearly impossible in the fibonacci sequence where each term is the sum of the two previous terms, always positive, see the 94th:
https://code.sololearn.com/cldAbQvHzpU8/#cpp

for larger values, you can switch to an arbitrary-precision mathematical library like:
GMP → https://gmplib.org/#FUNCCLASSES
or
Boost.multiprecision → https://www.boost.org/doc/libs/1_73_0/libs/multiprecision/doc/html/index.html

here is an example using Boost.multiprecision::::cpp_int :
https://godbolt.org/z/tZfDYm