Prob 0025 ‐ 1000‐Digit Fibonacci Number - maccergit/Euler GitHub Wiki

More Fibonacci fun. While the direct approach is fast enough, looking at alternative solutions leads us into details of Python numerics that we have not yet needed to investigate.

01

The direct approach is to generate numbers in the sequence until we get one of the required length. We don't even need to do string conversion to get the length if we realize that the first number in the sequence greater than $10^{limit}-1$ is what we need. The result is surprisingly fast :

02

From our previous work with Fibonacci numbers, we can try using Binet's formula - but we then hit a snag :

OverflowError: (34, 'Result too large')

A little experimentation reveals that we can get to 308 digits - but any more digits overflows. This is cause by the use of floating point values for the constants in the formula - we then produce very large floating point values to compute the result. However, the binary floating point representation can only handle numbers up to $10^{308}$ - anything larger causes the binary exponent field to overflow (see Range of Floating Point Numbers on Wikipedia).

This is disconcerting, as one of the reasons for using Python is its native support for arbitrarily large numbers - this support has made several of the earlier problems much easier to solve. However, this built in support does not extend to floating point values.

03

The Python standard library includes the "decimal" library, which brings in the Decimal type. By default, it can can handle much larger exponents than floating-point, and it can be configured to have arbitrary precision. It turns out the default values are good for most cases, and the library appears to be optimized for these default values, as changing the limits tended to hurt performance - and in extreme cases caused the unit tests to fail. Using the defaults, we are now able to run the program :

04

While the decimal library allows the code to work, it's also much slower. There is another arbitrary precision library called "gmpy2" - it brings in the mpfr datatype that can be used like a Decimal. Similar to decimal, the default values appear to be the best ones for most purposes - and it's quite a bit faster than decimal :

05

Now that we have ways to generate a Fibonacci number without iterating through all the earlier ones, we can see if we can't speed up the search for the one we want. A simple approach is to generate a number, and if the number is too small, then double the index and try again. We keep doubling the index until we overshoot - at which point, we can do a binary search for the number we want. With the decimal library, we get performance similar to the direct approach :

06

...and with gmpy2, we now get the fastest version :

Final Notes

One thing to keep in mind : we used the arbitrary precision libraries so that we could have larger floats - not so that we could have better precision. While there may be cases where the better precision is needed, that was not the case here. Increasing the precision slows down performance - doubling the precision cuts the performance in half. This might make it seem that reducing the precision from the default would help performance - but that turns out not to be the case. It appears that the libraries are tuned to be optimal at the default settings, and reducing the precision simply causes a reduction in functionality for no performance gain (and possibly a performance decrease).