19663


大きな自然数nに対しても、  
フィボナッチ数列f(n)の下20桁を高速に求める  
にはどうすればよろしいでしょうか？

なお、私は以下のように  
f(n)を高速に求め（※）、mod をとりました。

[code]

    # (a + b√x)^nの計算
    def power(a, b, x, n)
      return [1, 0] if n == 0
      c, d = power(a, b, x, n >> 1)
      c, d =
      c * c + x * d * d,
      2 * c * d
      return [c, d] if n & 1 == 0
      c, d =
      a * c + x * b * d,
      a * d + b * c
      return [c, d]
    end
    
    # (1 + √5)^n = an + bn√5とすると、f(n) = bn / 2^(n - 1)
    def f(n)
      power(1, 1, 5, n)[1] >> n - 1
    end
    
    Mod = 10 ** 20
    (0..8).each{|i| p f(9 ** i) % Mod}
    
[/code]

実行結果  
1  
34  
37889062373143906  
77515304438631163554  
85142957433431151586  
55029990705407376674  
70162980353113645666  
33971075843592127394  
27265106508993618146

※次のように「f(n)を行列の累乗計算を使って求める方法」があるが、  
上記の方が少し速い。

[code]

    require 'matrix'
    
    def f(n)
      v = Vector[1, 0]
      a = Matrix[[1, 1], [1, 0]]
      ((a ** n) * v)[1]
    end
    
    Mod = 10 ** 20
    (0..8).each{|i| p f(9 ** i) % Mod}
    
[/code]


CC BY-SA 3.0
2015-12-05T11:16:08.780
19661
2015-12-05T17:41:03.337
2015-12-05T17:41:03.337
5363
5363
question
ruby アルゴリズム
フィボナッチ数列の下20桁を高速に求めるには？


行列計算をライブラリを使わないで書いて、  
その中でmod をとると速くなった。  
（プログラミングコンテストチャレンジブック [第2版]  
の行列累乗、フィボナッチ数列のコード  
を見ながら書いてみました。）

[code]

    def mul(a, b, mod)
      m = []
      m[0] = (a[0] * b[0] + a[1] * b[2]) % mod
      m[1] = (a[0] * b[1] + a[1] * b[3]) % mod
      m[2] = (a[2] * b[0] + a[3] * b[2]) % mod
      m[3] = (a[2] * b[1] + a[3] * b[3]) % mod
      m
    end
    
    def power(a, n, mod)
      return [1, 0, 0, 1] if n == 0
      m = power(a, n >> 1, mod)
      m = mul(m, m, mod)
      return m if n & 1 == 0
      mul(a, m, mod)
    end
    
    def f(n, mod)
      a = [1, 1, 1, 0]
      power(a, n, mod)[2]
    end
    
    Mod = 10 ** 20
    (0..20).each{|i| p f(9 ** i, Mod)}
    
[/code]

実行結果  
1  
34  
37889062373143906  
77515304438631163554  
85142957433431151586  
55029990705407376674  
70162980353113645666  
33971075843592127394  
27265106508993618146  
41382305497188743714  
23511410999846621026  
81491824040399593634  
69160106970543566306  
93325772114701285154  
18660727633887525986  
58459602442015866274  
852482831714532066  
22973503028858024994  
85584756745178376546  
80398123954738289314  
88145204909739411426


CC BY-SA 3.0
2015-12-05T14:06:49.853
19663
2015-12-05T14:36:19.787
2015-12-05T14:36:19.787
5363
5363
19661
answer