(gmp.info.gz) Fibonacci Numbers Algorithm

Info Catalog

(gmp.info.gz) Binomial Coefficients Algorithm

(gmp.info.gz) Other Algorithms

(gmp.info.gz) Lucas Numbers Algorithm

 
 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.
 

Info Catalog

(gmp.info.gz) Binomial Coefficients Algorithm

(gmp.info.gz) Other Algorithms

(gmp.info.gz) Lucas Numbers Algorithm