Hankin本記事は、原著者の許諾のもとに翻訳・掲載しております。(注:2017/6/10、いただいたフィードバックを元に翻訳を修正いたしました。)次のコードを用いると、なんとフィボナッチ数列が生成できます。この記事では、その導き方と振る舞いを説明しましょう。具体的な説明に入る前に、背景としてフィボナッチ数列の概要と計算方法を駆け足で紹介します。数学の専門知識がある方は、導入部分はほとんど飛ばして、「母関数」のセクションをざっと読んでから、「整数の公式」に進んでいただいて構いません。フィボナッチ数列とは、言わずと知れた以下の数列です。この数列の番目の値は、その直前の2つの値の和です。公式で表現すると、以下のような漸化式になります。ここでは数列の添え字を、一般的な1ではなく、0から始めています。フィボナッチ数列の計算この数列には、わりと有名な計算方法が何種類かあります。以下は明示的な再帰的呼び出しを行う方法で、この実装だと処理速度は遅くなります。]]></script>になります。]]></script>になります。m.item(0)最後の方法は、```fib_iter```内の```a```と```b```を数列として見なす方法で、以下のように表記できます。/></a>これから以下の式が得られます。]]></script>になります(Pythonと違って、行列の添え字は通常1が基準になることに注意してください)。]]></script>になります。漸化式を解くために、閉じた式を見つける方法もあります。]]></script>。]]></script>の値が小さければ問題はありません。任意の数列の母関数は、の無限和です。フィボナッチ数列の場合はになります。これは無限に続くべき級数であり、の係数は番目のフィボナッチ数に相当します。フィボナッチ数には以下の関係があります。この式にをかけて全体で和をとると、以下の式が得られます。母関数として、それをと定義すると、上の式は次のように簡略化できます。これは、さらに整理できます。これをについて解くと以下の式が得られます。驚くことに、全てのフィボナッチ数列を網羅する簡単でシンプルな公式を、なんとか導くことができました。この式の利用方法については、次のセクションで詳しく説明しましょう。今はひとまず技術的なことは置いておき、いくつかのの値についてを評価してみましょう。そのためには、べき級数が収束する必要があります。1なら等比級数は収束します。よって、<から、べき級数は収束することが分かります。整数の公式ここまでで、Pythonのコードを理解するための準備は整いました。この公式を直感的にとらえるため、で母関数を評価してみましょう。興味深いことに、小数展開した部分にと、フィボナッチ数列が現れています。魔法のような結果に驚いてしまいますが、その理由は次の式から分かります。この例では、フィボナッチ数列が次々と倍されて並んでいきます。その値が一旦1000を超えると、隣り合う数に影響を及ぼし始めるということです。この現象は、上記のの計算で988から確認できます。正しいフィボナッチ数は987ですが、数列の次の数から1だけオーバーフローが発生しています。その結果Off-by-oneエラーが発生し、以降はパターンが崩れてしまうのです。いかなるの値に対しても、10の負の指数を十分大きく取れば、たとえオーバーフローが発生したとしても、番目のフィボナッチ数に悪影響が出ることはありません。ここでは、あるという値についてが妥当な値になると仮定しましょう。この値は後ほど選定します。整数で計算をしたいので(その方がコーディングしやすいので)、全体を倍して番目のフィボナッチ数が整数の範囲にくるようにして、式を整理します。この結果をを法として見ると、番目のフィボナッチ数が得られます(先ほども書きましたが、には十分大きな値を選んだものと想定しています)。先に進む前に、底を10から2に変換しましょう。理由は単にプログラミングを楽にするためです。あとは<になるように、を十分大きく取るだけです。フィボナッチ数列はのように増大して、<なので、とすれば安全です。これらを統合すると以下の式が得られます。Pythonでは左シフトの表記法が使えるので、<<の場合は次のように書けます。<<の部分は、<<とのビット単位の論理積(&amp;)として表せるので、元のPythonプログラムは次のように書き直せます。非反復型で閉じた解が得られたのは興味深いですが、これは全く実用的な手法ではありません。ここではサイズがビットの整数を用いて、整数演算を実行しています。実際には、最終的にビット単位で論理積を取る前に、最初の個のフィボナッチ数が全て連結した整数値を取得しているのです。ツイート翻訳に対するフィードバックがございましたら、メールまたはGitHubのIssueよりお寄せください。Ltd.リクルートグループサイトへ。