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.