トップページ -> Pythonで数学をしてみよう! -> Pythonでフィボナッチ数列を実装してみよう!

Pythonでフィボナッチ数列を実装してみよう!

今回はフィボナッチ数列の実装をしてみたいと思います. フィボナッチ数列とは以下のように定義されます.

フィボナッチ数列の定義

具体的に数列を見てしまったほうが分かりやすいかもしれませんね. 0,1,1,2,3,5,8,13,21,34,55,89, ?, … と続いていく数列です. ?にあてはまるのは1個前の87と2個前の54を足した144になるというわけです. 今回はこのフィボナッチ数列を4通りの方法で実装していきたいと思います.

1.再帰関数を利用した方法

まず1つ目は再帰関数を使った実装です. 再帰関数とは処理の中で自身を呼び出す関数のことです. フィボナッチ数列の定義通りにフィボナッチ数列の第n項(n番目の数字)を求める関数を書いてみます.


def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
簡単に書くことができますね. 試しに30まで求めてみましょう.繰り返し回数は変えてもいいですが,35程度で留めておいたほうがいいと思います.

for i in range(30):
    print(fibonacci(i))
35以上で試してしまった方は雲行きの怪しさを感じられたかもしれませんが,問題なく求められていますね. それでは,再帰関数を利用してフィボナッチ数列を求める場合の計算量について考えてみましょう. 6行程度で記述できてしまう可愛らしい関数ですが,恐ろしい性質を秘めています. 先ほどの関数を少し改良して関数が何回呼び出されたかを記録できるようにしましょう.

counter = 0
def fibonacci_count(n):
    global counter
    count += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_count(n-1) + fibonacci_count(n-2)
グローバル変数counterを利用して関数が呼び出されるたびにcounterに1を足すようにしました. この関数を使って,n=35までの計算量を求めてみます.

count_list = [] 
for i in range(36):
    counter = 0
    fibonacci_count(i)
    count_list.append(counter)
    print(i,counter)
そうなんです.この関数はnを大きくすればするほど爆発的に計算量が増えていく怖ろしい関数なんです. 第39項までの計算量をグラフにしてみました.
フィボナッチ数列の計算量
先ほど求めた計算量の結果を見てみると,n=2以降の計算量は1個前と2個前の計算量の和に1を足したものになっています. そこでフィボナッチ数列の一般項を用いて計算量を表すことができます. 導出は割愛しますが,「フィボナッチ数列 一般項」などと調べると求め方が出てきます. 数Ⅱ・Bまでの内容で求められます.
フィボナッチ数列の一般項
実際にn=2やn=3などを代入してみると先ほどの結果と一致することが確かめられます. フィボナッチ数列の一般項自体も黄金数が現れることや,根号が入っているにも関わらず整数になることなど, 興味深い性質を持っているのですが,大きく脱線してしまうのでこれについてはまたの機会にするとします. この一般項と同じように計算量が増えていくのですから,{(1-√5)/2}^nはnの増加に伴い減少してことを考慮すれば, 計算量はO({(1+√5)/2}^n)となります. 計算量が指数函数的に増加していくのですから,再帰関数は計算コストが高いことがわかります.

2.一般項を使った計算

ところでフィボナッチ数列の一般項が出てきたときに,最初からこれを使って計算すればいいじゃないかと思った方はいませんか? 私もそう思います.一般項を使ってフィボナッチ数列を求める関数を作りました.


def fib_general(n):
    fib = (1/(5**0.5)) * (((1+(5**0.5))/2)**n - ((1-(5**0.5))/2)**n)
    return int(fib)
一般項をそのままプログラムにしたものです. 1回の計算に2n回の掛け算をしていますね. O(n)の計算量です. 試しに第100項まで求めてみましょう.

for i in range(101):
    print(i,fib_general(i))
先ほどは40まで計算するのすら大変だったのが嘘のように早く終わりましたね. しかし,第98項と第99項を足した結果が第100項と一致するか確かめてみましょう.すると…

一致しませんね. 無限小数を考えるとコンピュータで表現できる小数の桁数には限りがあるため,コンピュータは誤差なく無限小数を表現することができません. 無限と言わずともある程度の桁数を持つ小数は誤差なく表現することができません. ここでは√5を誤差なく表現することができず,√5に関する計算を行う度にわずかですが誤差が生じます. コンピュータと誤差について詳しく知りたい方は「浮動小数点数」や「丸め誤差」などで検索されるといいかもしれません. そのためn=71以降では実際の結果とは異なる出力がされています. このため大きなnに対しては一般項を使っての計算を行うことはできません. コンピュータを使って精密な数値計算を行う場合には誤差に関しても注意を払わなくてはいけないのです.

3.リストを使っての計算

気を取り直して次の解決策を探りましょう. 再帰関数の抱える問題はnが増えるにつれて関数を呼び出す回数が増えていくことが問題でした. より詳しく関数が何回呼び出されているのか調べてみましょう.


def fibonacci_count2(n):
    global count_list
    count_list[n] += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_count(n-1) + fibonacci_count(n-2)
count_listというグローバル変数を使ってfib(n)がそれぞれのnに対して何回呼び出されるのかを数えてみます.

count_list = [0 for i in range(21)]
fibonacci_count2(20)
for i in range(21):
    print(i,count_list[i])
一度,呼び出した関数が何度も呼び出されていることがわかります.fib(1)に関しては6765回も呼び出されています. これでは無駄が多すぎます. この無駄を省くために一度求めた項をリストに記録し,それを次の項の計算に使うようにします.

def fibonacci_list(n):
    fib_list = [0 for i in range(n+1)]
    fib_list[0] = 0
    fib_list[1] = 1
    for i in range(2,n+1):
        fib_list[i] = fib_list[i-1] + fib_list[i-2]
        
    return fib_list[n] # [n]を外せばフィボナッチ数列のリストを返すようにもできます

fibonacci_list(100)
一つの項を求めるのに足し算を一回するだけなのでO(n)の計算量です. 100000くらいなら割とすぐに終わりますね. ですが,この関数も大きな問題を抱えています. 一度求めた項を記録しているため記憶容量をとてつもなく使うのです. nが増えれば桁数も増えていくので10^6なんて計算しようものならメモリが足りずにエラーを起こします.(絶対にやらないでくださいね) この方法も上の2つよりはだいぶマシですが,大きなnに対しては使えそうにありません.
数値計算に限らずコンピュータによる問題解決をする際には記憶容量にも気を配らなければなりません.

4.小さい項から計算する

リストを使う方法の敗因はリストを使い記憶容量を使い果たしてしまうからでした. 考え方として一度求めたものを計算せずに済ませるという方法は有効そうです. 何か他に手はないでしょうか? 小さいほうから順番に求めていけばわざわざリストで記憶せずとも計算ができます.


def fibonacci_step(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a_0 = 0
        a_1 = 1
        for i in range(n-1):
            a_2 = a_0 + a_1
            a_0 = a_1
            a_1 = a_2
        
        return a_2

fibonacci_step(1000000)
この方法ならリストではメモリ不足で計算できなかったn=1000000も計算することができます. n=10000000 くらいなら30分程度で終わります. 時間はかかりますが,どんなに頑張っても終わらせられなかった上の方法と比べれば終わるだけマシです. 途中までの計算を記憶することもできるので,リストを使った計算の上位互換になります.

今回は4通りの方法を使ってフィボナッチ数列の計算をしてみました. コンピュータを使った数値計算をする場合に誤差に気を付けなければいけないこと,記憶容量に気を配らなければいけないことが 実感していただけたと思います.

-----------------以下おまけ---------------------

5.繰り返し2乗法

数Ⅱ・Bまでの内容を超えます. 行列の計算ができる方向けに繰り返し2乗法をご紹介します. 2^8を計算することを考えます. 2*2*…*2 と2を8回かける計算をすると2^8の計算量は掛け算8回になります. 2^nはn回の掛け算が必要になります. しかし,((2^2)^2)^2のように繰り返し2乗をする計算方法を取ると3回の計算で済みます. この場合の2^nの計算量は掛け算log(n)回程度まで計算量が削減できます. このことを利用してフィボナッチ数列の第n項を高速で求めます. まずは,フィボナッチ数列を行列を用いて表現します.
行列を用いたフィボナッチ数列の表現
この書き換えと繰り返し2乗法によってフィボナッチ数列の第n項をO(log(n))の計算量で求めることができるようになります. 繰り返し2乗法を使ってフィボナッチ数列の実装をします. 行列計算はnumpyを使ってできるのですが,手元でよくわからない挙動を示したため,行列の積を関数として定義して使います.

# 行列の積の定義
def matrix_multi(A,B):
    C_00 = A[0][0]*B[0][0] + A[0][1]*B[1][0]
    C_01 = A[0][0]*B[0][1] + A[0][1]*B[1][1]
    C_10 = A[1][0]*B[0][0] + A[1][1]*B[1][0]
    C_11 = A[1][0]*B[0][1] + A[1][1]*B[1][1]
    C = [[C_00,C_01],[C_10,C_11]]
    return C

# 繰り返し2乗をする関数
def repeat_pow(A,n):
    if n == 1:
        return A
    elif n%2 == 1:
        B = repeat_pow(A,n-1) 
        return matrix_multi(A,B)
    else:
        A = repeat_pow(A,n/2)
        return matrix_multi(A,A)

A = [[1,1],[1,0]]
print(repeat_pow(A,100)[0][1])
nが大きくなるとフィボナッチ数列の桁数自体が大きくなるため計算に時間がかかるようになってきますが, 計算量を抑えてフィボナッチ数列を実装することができました.

<- 前へ戻る 【目次に戻る】