1

大きな自然数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}
6
  • 9 ** iしているのはどうしてですか? 2015年12月5日 15:50
  • mod をとることで周期性がうまれます。例えば、5を法にすると、f(5 * k) = 0となります。 Mod = 10 ** 20 = (2 ** 20) * (5 ** 20) なので、f(10 ** i)を考えるよりも、f(9 ** i)の方がいいかなと思いました。
    – TOM
    2015年12月5日 16:18
  • この計算はf(1), f(9), f(81), f(729)...の下位20桁を求めていますが、f(1), f(2), f(3)...というようにnを連続した整数にしなくていいのはなぜですか?というのが質問です。実行結果は1,34, 37889062373143906, ...となっていますけれども、nが連続した整数なら1,1,2,3,5,...とならないとおかしいのでは?と思いました。 2015年12月5日 17:02
  • どれくらい大きなnでf(n) % Modの計算ができるか気になり、i = 0, 1, 2, … に対し、f(10 ** i)を計算しようとしたのですが、前のコメントの理由でf(9 ** i)を計算することにしました。n が連続していないのはそのためです。
    – TOM
    2015年12月5日 17:22
  • なるほど。本文にそう書いてあると、追試する人の助けになると思います。 2015年12月5日 17:37

1 件の回答 1

0

行列計算をライブラリを使わないで書いて、
その中で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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。