高速化フィボナッチの計算量の理想と現実

前回書いた高速化フィボナッチでは、計算量をと見積もった。
今回はこの見積もりの妥当性を検討する。

まず、

>>> from my import fib
>>> from timeit import timeit
>>> from matplotlib import pyplot as plt
>>> x = range(2**7)
>>> y = [ timeit('fib({} * 2**18)'.format(n),
...           number=1, globals=globals()) for n in x ]
>>> plt.plot(x,y, '.')
>>> plt.show()

とやって、実際にfib(x)を計算するのに要した時間を可視化してみる。
（もちろん、私の環境固有の値である。またコード中のmyはfib関数を実装した自作モジュールの名前だ）。

計測時間の総計はだいたい1時間半くらい。

ここで、x軸の単位は、y軸の単位は秒である。

グラフを観察してみると、xが23から24に変わるときと、47から48に変わるとき、94から96に変わるときでギャップがあるのに気が付く。
これはこれで気になるが、今回検討するのはそこではない。
今回は、グラフが下に凸であることに着目したい。

もし、計算量が前回の理想的な見積もり、であるなら、グラフは上に凸であるはずだ。
しかし、実際にはグラフは下に凸になっている。
これはなぜだろう？

ちょっと考えれば当然だが、これは巨大な整数を扱っていることに起因している。
フィボナッチ数はnが大きくなるにしたがって、指数関数的に大きくなる。
扱う整数の値が大きくなれば、それに伴って四則演算の計算コストもそれに伴い増加するのは当然だ。
前回の見積もりでは、「任意の桁数の四則演算は同じ計算コストを持つ」という非現実的な仮定を置いていた。
今回はこれを修正して、多倍長整数の計算コストも考慮して、評価してみよう。

しかし、残念ながら、この評価をするには（もちろん）、pythonの多倍長整数演算の実装を知らなければならない。
今回は標準的なpythonの実装の一つであるCPythonを考えてみる。

CPythonのソースをgithubからゲットしよう。
github.com

これを少し読むと、Karatsuba法を用いた実装のようであることが分かる。

/* Karatsuba multiplication.  Ignores the input signs, and returns the
 * absolute value of the product (or NULL if error).
 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
 */
static PyLongObject *
k_mul(PyLongObject *a, PyLongObject *b)

(cpython/Objects/longobject.c)

Karatsuba法なら、乗算の計算コストは桁数をkとして、だ。

フィボナッチ数列ではnが大きくなるにしたがって、数そのものは指数関数的に大きくなるから、桁数はnに対して線形に増加する。
（これは前に、フィボナッチ数をたくさん出力すると放物線が現れる件 - studiesでみたことだ）。

高速化したフィボナッチ数列の計算では多倍長整数の演算（特に乗算）がボトルネックとなり、その計算量は

となる。