Module fibonacci (February 29, 2016)

Several implementation of Fibonacci numbers computation.

Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...
\(F_0 = 0\)
\(F_1 = 1\)
\(F_{n+2} = F_{n+1} + F_n \qquad\forall n\) integer

https://oeis.org/A000045

Lucas numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843...
\(L_0 = 2\)
\(L_1 = 1\)
\(L_{n+2} = L_{n+1} + L_n \qquad\forall n\) integer

https://oeis.org/A000032

See

Mathematical relations: Fibonacci numbers — several relations to implement good algorithms .pdf
Complete C++ and Python sources on Bitbucket
This C++ HTML online documentation

Warning: Complexity informations in each function considers that operations on large numbers are in constant time and constant space (which is obviously false).

Implementations                                | Time O(n)     | Space O(n) | Implementation using GMP
-----------------------------------------------+---------------+------------+--------------------------------------------
fibonacci_uint64_pair__iter_lg_table           | lg(n)         | "1"        | fibonacci_mpz_pair__iter_lg_table
fibonacci_uint64_pair__iter_lg                 | lg(n)         | 1          | fibonacci_mpz_pair__iter_lg
fibonacci_uint64_pair__rec_lg_table            | lg(n)         | lg(n)      | fibonacci_mpz_pair__rec_lg_table
fibonacci_uint64_pair__rec_lg                  | lg(n)         | lg(n)      | fibonacci_mpz_pair__rec_lg
fibonacci_uint64__iter_lg_optimized_table      | lg(n)         | "1"        | fibonacci_mpz__iter_lg_optimized_table
fibonacci_uint64__iter_lg_optimized            | lg(n)         | 1          | fibonacci_mpz__iter_lg_optimized
fibonacci_uint64__iter_lg_table                | lg(n)         | "1"        | fibonacci_mpz__iter_lg_table
fibonacci_uint64__iter_lg                      | lg(n)         | 1          | fibonacci_mpz__iter_lg
fibonacci_uint64__iter_n                       | n             | 1          | fibonacci_mpz__iter_n
fibonacci_uint64_pair__rec_n                   | n             | n          | fibonacci_mpz_pair__rec_n
fibonacci_uint64__rec_exp                      | 2^n           | n          | fibonacci_mpz__rec_exp
-----------------------------------------------+---------------+------------+--------------------------------------------
fibonacci_uint64_pow2__iter_lucas_n_table      | n             | "1"        | fibonacci_mpz_pow2__iter_lucas_n_table
fibonacci_uint64_pow2__iter_lucas_n            | n             | 1          | fibonacci_mpz_pow2__iter_lucas_n
                                               | n             | 1          | fibonacci_mpz_pow2__iter_takahashi_n
fibonacci_uint64_pow2_pair__iter_lucas_n_table | n             | "1"        | fibonacci_mpz_pow2_pair__iter_lucas_n_table
fibonacci_uint64_pow2_pair__iter_lucas_n       | n             | 1          | fibonacci_mpz_pow2_pair__iter_lucas_n
fibonacci_uint64_pow2_pair__iter_n_table       | n             | "1"        | fibonacci_mpz_pow2_pair__iter_n_table
fibonacci_uint64_pow2_pair__iter_n             | n             | 1          | fibonacci_mpz_pow2_pair__iter_n

Benchmark with Debian Wheezy - GCC 4.7.2 64 bits (uint64 and GMP) :
Benchmark GCC Fibonacci Benchmark GCC Fibonacci GMP
Benchmark GCC Fibonacci pow2 Benchmark GCC Fibonacci pow2 GMP

Benchmark with Debian Wheezy - Clang 3.3 64 bits (but GMP compiled with GCC)
Benchmark Clang Fibonacci Benchmark Clang Fibonacci GMP

Piece of severalgos. https://bitbucket.org/OPiMedia/severalgos