Next: Lucas Numbers Algorithm, Previous: Binomial Coefficients Algorithm, Up: Other Algorithms [Index]

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.