セキュリティ的に正しいフィボナッチ数列を求めるプログラム

fibonacci.rb

def fibonacci(n)
  1.step(n, 2)
   .map{|i| 2 * ((n - i + 1)..n).inject(:*) / (1..i).inject(:*) * 5 ** (i / 2)}
   .sum / 2 ** n
end

著作権は放棄するので自由に使ってください！「フィボナッチ数を求めるプログラムを書け」という課題を与えられたらこれをコピペで提出するといいですよ！

この記事を書いた理由

まずはじめに一応書いておくと、フィボナッチ数列とは以下で定義される数列 $F_n$ ですね。

\begin{align}
& F_0 = 0 \\
& F_1 = 1 \\
& F_{n} = F_{n-2} + F_{n-1} (n \geqq 2)
\end{align}

さて、フィボナッチ数列を求めるプログラムなんて「フィボナッチ数列 （何らかのプログラミング言語）」などと検索すれば山ほどプログラム例が出てきます。（Qiita 上だけでも 600 件以上。）下に挙げたような、再帰を用いたものがよく見られますね。

def fibonacci(n)
  return 0 if n == 0
  return 1 if n == 1
  return fibonacci(n - 2) + fibonacci(n - 1)
end

しかし、そうした巷にあふれる「フィボナッチ数列を求めるプログラム」には重大なセキュリティ上の問題があるように思われます。そこでこの記事ではその問題点を取り上げた上で、上記のプログラムであればその問題点を回避できることを説明したいと思います。

一般的な「フィボナッチ数列を求めるプログラム」の問題点

さて皆様も一度は、日曜の昼下がりにアフタヌーンティーを嗜んでいたときに、スコーンにクロテッドクリームを塗りたくりながら、ふと

「そういえば、フィボナッチ数列の $F_{100}$ っていくつなんだろう…？」

と疑問に思ったことがあるのではないかと思います。¹

そうしたとき、多くの人は自分でプログラムを書くなり、検索してどこかから拾ったプログラムを実行するなりして

「ああ、3垓5422京4848兆1792億6191万5075か」

と答えを得て安心し、再び紅茶を啜りだすことでしょう。

しかし、ここで気をつけるべきは「我々が求めたかったのは $F_{100}$ であって、$F_{98}$ や $F_{99}$ ではない」ということです。ですが先に挙げたような一般的なプログラムの場合、$F_{100}$ を求める過程で $F_{98}$ や $F_{99}$ も求めてしまっています。

不正指令電磁的記録に関する罪、いわゆるウイルス作成罪は、以下のようなプログラムの作成や提供を禁じています。

人が電子計算機を使用するに際してその意図に沿うべき動作をさせず、又はその意図に反する動作をさせるべき不正な指令を与える電磁的記録

$F_{100}$ を求めたいだけなのに、その意図に反して $F_{98}$ や $F_{99}$ まで求めてしまう…これはまさしく不正指令電磁的記録であると言えます。² このようなプログラムを書いてしまっては、いつ神奈川県警や兵庫県警がやってきてもおかしくないでしょう。

逮捕されないためのフィボナッチ数列の求め方

というわけで、「$F_{n-1}$ を求めることなく $F_n$ を求める」必要があるわけです。そうした場合に役立つのが「一般項」。

フィボナッチ数列の一般項は、次の式で表されます。³

F_n
= \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\}

この一般項を用いれば $F_{n-1}$ を求めることなく $F_n$ を求めることができるはずです。

単純な実装

しかし以下のように先程の数式をそのままプログラムに落としても、小数点の奥深くの僅かな誤差が原因で、大きな n に対して正しく値を求めることができません。⁴

def fibonacci(n)
  (1 / Math.sqrt(5) * (((1 + Math.sqrt(5)) / 2) ** n - (((1 - Math.sqrt(5)) / 2) ** n)).round
end

実際このプログラムを動かしてみたところ、わずか $F_{71}$ で実際の値と食い違ってしまいました。これでは $F_{100}$ を求めたいという要求に対応できません。

一般項を分析する

$\sqrt{5}$ のような非整数が出てくると、プログラミングによって正確な値を求めるのは難しくなります。そこで $\sqrt{5}$ を消すべく、一般項の公式をまずは下のように少しいじってみましょう。

F_n
= \left\{ \left(1+\sqrt{5} \right)^n - \left( 1-\sqrt{5} \right)^n \right\} \div \sqrt{5} \div 2^n

$(1 + \sqrt{5})^{n}$ , $(1 - \sqrt{5})^{n}$ は、二項定理より下のように展開できます。

(1 + \sqrt{5})^n = \sqrt{5}^0 \times {}_n \mathrm{C} _0 + \sqrt{5}^1 \times {}_n \mathrm{C} _1 + \sqrt{5}^2 \times {}_n \mathrm{C} _2 + \sqrt{5}^3 \times {}_n \mathrm{C} _3 + ...\\
(1 - \sqrt{5})^n = \sqrt{5}^0 \times {}_n \mathrm{C} _0 - \sqrt{5}^1 \times {}_n \mathrm{C} _1 + \sqrt{5}^2 \times {}_n \mathrm{C} _2 - \sqrt{5}^3 \times {}_n \mathrm{C} _3 + ...

前者から後者を引くことで $\sqrt{5}$ の指数部が奇数の項だけが残り、そしてそれが $\sqrt{5}$ で割られることによって平方根が消え、整数だけが残ることになります。

よって、フィボナッチ数列の一般項をこのように書き換えることができます。

F_n = ( \sum_{i \in n 以下の奇数} 2 \times {}_n \mathrm{C} _i \times 5^{\frac{i - 1}{2}}) \div 2^n

というわけで、あとはこれを ruby のプログラムに落とし込めばいいだけです。

$\sum$ と $\div 2^n$ の部分に相当するのが

  1.step(n, 2)
# 略
   .sum / 2 ** n

の部分です。

$5^{\frac{i - 1}{2}}$ は、ruby では Integer / Integer は切り捨てられるので、わざわざ i を - 1 しなくても

  5 ** (i / 2)

で大丈夫ですね。

{}_n \mathrm{C} _i = \frac{n!}{i! \times (n - i)!} = \frac{n \times (n - 1) \times (n - 2) \times ... \times (n - i + 1)}{i!}

より、inject を用いればこの部分を

((n - i + 1)..n).inject(:*) / (1..i).inject(:*)

と書けます。⁵

最後に

この記事を本気にする人はいないと思いますが念の為。普通に繰り返しを使って

def fibonacci(n)
  a, b = 0, 1
  n.times{a, b = b, a + b}
  a
end

などと書いたほうが遥かに高速なので、フィボナッチ数列を求めたいなら素直にそうしましょう。

とはいえ、最初の方で挙げた再帰を単純に用いたプログラムよりは高速です。（というより、大きな n になると再帰では SystemStackError になるはず。）⁶

1. 私はありません。 ↩

2. 言えません。 ↩

3. この一般項の導出は、結城浩先生の 数学ガール がオススメです。 ↩

4. 実を言うとこの記事は最初このプログラムでごまかすつもりだったんですが、思ったよりも小さな n で誤差が生じてしまいました。1000 くらいまでは耐えてくれると思ったのに… ↩

5. i が 0 の場合にはこのプログラムでは正しく求めることができない（どちらの inject も nil になってしまう）ので、一般的に nCr を求める場合は .inject(1, :*) と書く必要がありますが、今回のプログラムでは i は 0 にはなりえないので省略しました。

   また、i が大きくなるとこのままでは非常に計算が遅くなるので、効率を高めるなら i が n の半分よりも大きい場合は ${}_n \mathrm{C} _i = {}_n \mathrm{C} _{n - i}$ を利用した方がいいでしょう。 ↩

6. よく再帰についての例としてフィボナッチ数列計算プログラムが出てきますが、あまり良い例ではないと思います。繰り返しでも簡単に書け、しかもその方が効率が良いですから。だから再帰についての例としては「再帰で書いたほうが効率が良いような例」（具体例はちょっと思い浮かびません。）か、繰り返しでは書くのが難しい例（例えば、アッカーマン関数とか。）のほうが適切ではないかなーと思います。 ↩