(gmp.info.gz) Lucas Numbers Algorithm

Info Catalog

(gmp.info.gz) Fibonacci Numbers Algorithm

(gmp.info.gz) Other Algorithms

(gmp.info.gz) Random Number Algorithms

 
 Lucas Numbers
 -------------
 
 `mpz_lucnum2_ui' derives a pair of Lucas numbers from a pair of
 Fibonacci numbers with the following simple formulas.
 
      L[k]   =   F[k] + 2*F[k-1]
      L[k-1] = 2*F[k] -   F[k-1]
 
    `mpz_lucnum_ui' is only interested in L[n], and some work can be
 saved.  Trailing zero bits on n can be handled with a single square
 each.
 
      L[2k] = L[k]^2 - 2*(-1)^k
 
    And the lowest 1 bit can be handled with one multiply of a pair of
 Fibonacci numbers, similar to what `mpz_fib_ui' does.
 
      L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k
 

Info Catalog

(gmp.info.gz) Fibonacci Numbers Algorithm

(gmp.info.gz) Other Algorithms

(gmp.info.gz) Random Number Algorithms