GNU Info

(gmp.info)Fibonacci Numbers Algorithm

---

Next: Lucas Numbers Algorithm Prev: Binomial Coefficients Algorithm Up: Other Algorithms

---

Enter node , (file) or (file)node

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.