Playing with Fibonacci

Playing with Fibonacci

When we wish to write efficient code, we always start with the algorithm, nothing beats reducing the order of complexity.

But complexity is only the beginning. We need to consider the real cost of each “unit” of computation, in some cases we need to consider memory (disk and core) footprint, and we need to consider accuracy.

For example, there is a mathematically beautiful solution for obtaining any Fibonacci number, based on the fact that there are

exactly two Fibonacci (like) series of the form t0 t1 t2 ... tn. These two series also span a vector space (of rank 2) of all the Fibonacci like series (an = an-1 + an-2) so the conversion to the Fibonacci series (that starts with 0,1) is simply a change of basis.

However, while beautiful, this algorithm has two practical limitations: firstly, tn grows very fast, and while there are efficient algorithm to compute tn , The “unit” of computation cost grows with size of n (for arbitrary precision numbers). The second problem is that the two values of t are the golden numbers: (1 ±√5)/2, which are irrational and so accuracy becomes more challenging.

The following include self-contained (statically linked, stripped) Fibonacci programs (executable) for linux x86-64 (can be run in VM such as [Virtual Box]). Times reported are from running on Ubuntu 14.04.3 running in virtual Box on Mac ini 2011 running El-Capitan. Each program gets a number n from the command line (argv) and prints Fibonacci(n) to the standard output.

[1] The easiest program to write is also the fastest - the code (executable) is available [HERE]

It is arbitrary precision program that computes Fibonacci of 10,000,000 in just 0.484 sec (user time).

The result is 2,089,877 decimal digits long... However, this code also has the largest footprint of over 935KB in size (statically linked and stripped).

[2] The smallest program was also easy to write, but required a bit of hacking. It is limited to 64 bits and thus can only compute up to Fibonacci(93), which is not much of a challenge computationally. However it is rather small - only 939 bytes in length.

This is over x1000 smaller that the fastest code above. The program will print a usage message (“Usage: fib n (n <= 0 <= 93)”) if run without an argument or if the arguments is out of range - the code (executable) is available [HERE]

(Note: this code is not using a lookup table [THIS] code does and it is larger - 1360 bytes in length).

[3] Writing a balanced program that will be small and reasonably fast and can compute very large numbers took longer to write. The resulting program is slower than the fastest code above and also more limited. It can “only” compute up to Fibonacci(1,200,000) and it does that in 3.4 seconds. The result is 250,785 decimal digits long. While not as large as the fastest code results, it is still a fairly large number (requires over 833,000 bits). This program is only 5.5K bytes long . This is x170 smaller than the fastest code above. This program (executable) is available [HERE].

For comparison, the executable size of the empty program “int main(){} ” on the same system dynamically linked and stripped is 6.2K bytes long. This is over x6 larger than the smallest code above, and over x4 time larger than the lookup table version, it is not self-contained, and it does nothing at all.

Some online Fibonacci calculators:

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibCalcX.html

https://www.tools4noobs.com/online_tools/fibonacci/

http://www.numberempire.com/fibonaccinumbers.php