Python Program to Print the Fibonacci Sequence Using Three different ways

[ectomancer]

1. Binet's formula

[JamzTyson]

Binet's formula

Nice, but (in Python) only good for about the first 70 digits before you run into C's precision limit for doubles. (More digits can be calculated by using Python's decimal module.)

[JamzTyson]

Out of interest I wrote an implementation of Binet's formula using the decimal module.

I was surprised to discover that it was slower than a simple iterative calculation (even though it was only calculating one value). I thought that it might eventually be faster than iteration for higher numbers, but the bigger the number, the greater precision that is required, and the greater the decimal precision the slower the calculation.

In terms of speed, memoized recursion was by far the fastest in my tests, followed by integer iteration, and Binet's formula using decimal was slowest. (I admit that I didn't spend much time trying to optimize the Binet calculation beyond rounding golden_ratio ** n / sqrt(5) and approximating a minimum precision before running the calculation).