Next: , Previous: , Up: Other Algorithms   [Index]


15.7.5 Lucas数

mpz_lucnum2_ui関数は,下記の式に従ってFibonacci数のペアからLucas数のペアを導出します。

L[k]   =   F[k] + 2*F[k-1]
L[k-1] = 2*F[k] -   F[k-1]

mpz_lucnum_ui関数はL[n]のみ求めるもので,計算が効率化されています。 nにある連続したゼロビットがあると,2乗の計算が効率化できます。

L[2k] = L[k]^2 - 2*(-1)^k

更に,nの末尾1bit分で,mpz_fib_ui関数と同様に,Fibonacci数のペアの掛算を効率化しています。

L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k