Copyright (C) 2000-2012 |
GNU Info (gmp.info)Lucas Numbers AlgorithmLucas 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 automatically generated by info2www version 1.2.2.9 |