更新日から1年以上経過しています。情報が古い可能性がございます。

社内勉強会ネタその2

今回はプログラマならみんな大好きフィボナッチ数列です。
簡単に説明すると、
1, 1, 2, 3, 5, 8, 13, 21, …
と、連続する2つの和を取ったものが次の項になるという数列で、
an = an-1 + an-2
と表せる数列です。
n-1項、n-2項を使わないで一般項を表せるのですが、
今回の話ではないので触れません。
使用バージョンは前回同様。
・PYthon 3.6.2
・numpy 1.13.1

行列を用いて算出

numpyでは行列が扱えます。
np.matrixというやつです。
では早速コードを。

import numpy as np
def fib(n):
    A = np.matrix([[0, 1],
                   [1, 1]], dtype=np.int64)
    R = np.matrix([[0],
                   [1]], dtype=np.int64)
    
    R = A ** (n - 1) * R
    
    return R[1, 0]

こんな感じで。
試しにこの関数を呼んでみて、あっているか確認します。

for i in range(1, 40):
    print('{:,}'.format(fib(i)))

出力は

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1,597
2,584
4,181
6,765
10,946
17,711
28,657
46,368
75,025
121,393
196,418
317,811
514,229
832,040
1,346,269
2,178,309
3,524,578
5,702,887
9,227,465
14,930,352
24,157,817
39,088,169
63,245,986

と、正しそうです。
あ、因みに型としてnp.int64を指定していますので64bit整数が上限値です。

numpyの配列への対応

上ではループで回していましたが、折角numpyを使っているのだからまとめて渡してまとめて返してほしいですよね。
という訳で、numpyの配列を渡して、numpyの配列を返して貰うように変更します。

def arrayfib(n):
    A = np.matrix([[0, 1],
                   [1, 1]], dtype=np.int64)
    R = np.matrix([[0],
                   [1]], dtype=np.int64)
    
    R = np.array(list(map(lambda x: int((A ** (x - 1) * R)[1, 0]), n)))
    
    return R

mapをlistにしてnp.arrayで囲むの、もっと美しい書き方無いかしら……

では使ってみましょう。

arrayfib(np.arange(1, 40))

出力は

array([       1,        1,        2,        3,        5,        8,
             13,       21,       34,       55,       89,      144,
            233,      377,      610,      987,     1597,     2584,
           4181,     6765,    10946,    17711,    28657,    46368,
          75025,   121393,   196418,   317811,   514229,   832040,
        1346269,  2178309,  3524578,  5702887,  9227465, 14930352,
       24157817, 39088169, 63245986], dtype=int64)

と、期待した結果が得られました。

おまけ

フィボナッチ数列は負に拡張できるのですが、それにも対応しております。

numfib(np.array(list(reversed(range(-40, 1)))))

とすると、出力は

array([         0,          1,         -1,          2,         -3,
                5,         -8,         13,        -21,         34,
              -55,         89,       -144,        233,       -377,
              610,       -987,       1597,      -2584,       4181,
            -6765,      10946,     -17711,      28657,     -46368,
            75025,    -121393,     196418,    -317811,     514229,
          -832040,    1346269,   -2178309,    3524578,   -5702887,
          9227465,  -14930352,   24157817,  -39088169,   63245986,
       -102334155])

あってそうですね。

以上、社内勉強会ネタ第二弾フィボナッチ数列でした。