フィボナッチ数列の下20桁を高速に求めるには?

投稿者: Anonymous

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

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

# (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}

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

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

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}

解決

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

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)}

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

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *