Node:Fibonacci Numbers Algorithm, Next:, Previous:Binomial Coefficients Algorithm, Up:Other Algorithms


Fibonacci Numbers

The Fibonacci functions mpz_fib_ui and mpz_fib2_ui are designed for calculating isolated F[n] or F[n],F[n-1] values efficiently.

For small n, a table of single limb values in __gmp_fib_table is used. On a 32-bit limb this goes up to F[47], or on a 64-bit limb up to F[93]. For convenience the table starts at F[-1].

Beyond the table, values are generated with a binary powering algorithm, calculating a pair F[n] and F[n-1] working from high to low across the bits of n. The formulas used are 

F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
F[2k-1] =   F[k]^2 + F[k-1]^2

F[2k] = F[2k+1] - F[2k-1]

At each step, k is the high b bits of n. If the next bit of n is 0 then F[2k],F[2k-1] is used, or if it's a 1 then F[2k+1],F[2k] is used, and the process repeated until all bits of n are incorporated. Notice these formulas require just two squares per bit of n.

It'd be possible to handle the first few n above the single limb table with simple additions, using the defining Fibonacci recurrence F[k+1]=F[k]+F[k-1], but this is not done since it usually turns out to be faster for only about 10 or 20 values of n, and including a block of code for just those doesn't seem worthwhile. If they really mattered it'd be better to extend the data table.

Using a table avoids lots of calculations on small numbers, and makes small n go fast. A bigger table would make more small n go fast, it's just a question of balancing size against desired speed. For GMP the code is kept compact, with the emphasis primarily on a good powering algorithm.

mpz_fib2_ui returns both F[n] and F[n-1], but mpz_fib_ui is only interested in F[n]. In this case the last step of the algorithm can become one multiply instead of two squares. One of the following two formulas is used, according as n is odd or even. 

F[2k]   = F[k]*(F[k]+2F[k-1])

F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + 2*(-1)^k

F[2k+1] here is the same as above, just rearranged to be a multiply. For interest, the 2*(-1)^k term both here and above can be applied just to the low limb of the calculation, without a carry or borrow into further limbs, which saves some code size. See comments with mpz_fib_ui and the internal mpn_fib2_ui for how this is done.