バイナリ―オプション取引

整数の公式でフィボナッチ数列を求める

整数の公式でフィボナッチ数列を求める
整数 n に対して n 番目(および n+1 番目)のフィボナッチ数 \((F_n,F_)\) を対応させる写像は、整数の加法に関するモノイドから、FibPairへのモノイド準同型だとみなせる。

フィボナッチ数列のプログラム

★アドバイス ・フィボナッチ数列の再帰関数は出来ましたね。 >0,1,1,2,3,5,8・・・と表示できるのかがわかりません。 ↑ こんなにきれいには表示できないと思います。 何も printf() を入れなくてもよいのでは。 ・ちょっと試行錯誤してみましたが意外に難しいですね。 下のサンプルで我慢して。 サンプル: #include // フィボナッチ数列 int fib( int n ) < if ( n == 0 ) return 0; if ( n == 1 )n = fib(n - 1) + fib(n - 2); printf( " + %d", n ); return n; > // メイン関数 int main( void ) < // フィボナッチ数列 printf( "\nfib = %d\n", fib(9) ); return 0; >

  • 2007/06/25 15:24 回答No.4
  • himajin100000
  • ベストアンサー率54% (1660/3060)
  • 2007/06/25 06:56 回答No.3

★アドバイス ・フィボナッチ数列の代わりに 1 ~ n 番目までの数を加算するサンプルを載せます。 もちろん再帰的に処理する関数です。 これを参考に『フィボナッチ数列』の関数 int fib(int n) を作成して下さい。 ・それでは下にサンプルを載せておきます。 サンプル: #include 整数の公式でフィボナッチ数列を求める // 1~n 番目までを再帰処理で加算する関数 int func_sum( int n ) < if ( n >0 ) < printf( "%d + ", n ); return n + func_sum( n - 1 ); >else < printf( "%d\n", n ); return 0; >> // メイン関数 int main( void ) < // 1~10 までを加算 printf( "sum = %d\n", func_sum(10) ); return 0; >その他 ・動作を分かりやすくするために func_sum() 関数に printf() 関数を使っています。 実際に実行してみて動作の確認をして下さい。 表示される内容から再帰動作で 1 ~ n 番目の数の加算が分かると思います。 これを参考にして『フィボナッチ数列』の再帰関数を作ってみて下さい。 ・以上。

質問者からの補足 2007/06/25 22:24

こんな感じで作ってみたんですけど、何処にprintf()を入れれば 整数の公式でフィボナッチ数列を求める 0,1,1,2,3,5,8・・・と表示できるのかがわかりません。 よろしくお願いいたします。 #include int fib(int); main() < printf("fib = %d\n", fib(10)); >int fib(int n)

  • 2007/06/24 21:13 回答No.2

> 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める int f(0) = 0,f(1) = 1; > > f(n) = f(n - 1) + fib(n - 2); fib関数以外にf関数も登場していますね。f関数は不要です。 数列の1番目:1(固定) 2番目:1(固定) 3番目:2(1番目+2番目) 4番目:3(2番目+3番目) 5番目:5(3番目+4番目) 6番目:8(4番目+5番目) 7番目:13(5番目+6番目) 8番目:21(6番目+7番目) 9番目:34(7番目+8番目) 10番目:55(8番目+9番目) という結果を得るために、fib関数では呼び出し元に どういう値を返す必要があるか、検討してみてください。

  • 2007/06/24 18:59 回答No.1

質問者からの補足 2007/06/24 20:04

関連するQ&A

「フィボナッチ数を次の手順で求めるプログラムfib2.cを作成。 再帰関数 int fib(int n)整数の公式でフィボナッチ数列を求める を定義し,再帰呼出しによりfib(n)の値を求める。n=30までのフィボナッチ数を求めて表示せよ。 またどのnの値まで求めるか?」という問題です。 で下記のように作りましたが再帰関数をつかわなかったので再提出になってしまいました。 再帰関数はどうやって使うのでしょうか。 今回の場合はどの部分が再帰関数になるのでしょうか? おねがいします。 #include main() < int fib[100], i; fib[0] = 0; fib[1] = 1; printf("F0=0\nF1=1\n"); for(i=2; i>

プログラミングでexcel vbaを勉強しています。 excel vbaのプログラムでフィボナッチ数列のプログラムを作れという問題なんですけど、正直全くわかりません。誰かこのプログラミングを教えてください。お願いします。 フィボナッチ数列は次のように帰納的に定義される。 fib(1) 整数の公式でフィボナッチ数列を求める = fib(2) = 1 fib(n) = fib(n - 1) + fib(n - 2) (ただしn >= 3) この関数fib(n)を定義せよ。ただし引数nはInteger型、fib関数の返す値はLong型とする。 またfib関数を呼び出す適当なメインプロシージャを定義し、A1セルからA20セルまでに fib数列の1~20番目の値を書き出すようにせよ。 という問題です。ほんとに困ってますお願いします

c言語でフィボナッチ数列を求めるプログラムを再帰関数をつくり作れという問題でしたのように作りました。 windowsでcygwinというものを使ってコンパイルしています #include int fib(int); main() < int n,i; printf(\"第何項までのフィボナッチ数? n=\"); scanf(\"%d\",&n); fib(0)=0; fib(1)=1; for(i=2;i<=n;i++)< print(\"f(%d)=%d\",n, fib(n));>> 整数の公式でフィボナッチ数列を求める エラーは $ gcc fib2.c fib2.c: In function `main\': fib2.c:10: error: invalid lvalue in assignment fib2.c:10: error: invalid lvalue in assignment とでました。 どこかちがいますか?

フィボナッチ数列X(n+1)= X(n+1)+X(n) (X(整数の公式でフィボナッチ数列を求める 1)=X(2)=1) の1項X(1)からX(30)までの値を表示するプログラムを再帰関数を使って作る方法を教えてください。 再帰関数がよくわかりません。

ちょうど学校でフィボナッチ数列の話題になったので、思いつきで作ってみました。 そこで、配列を使ったものと再帰呼び出しを使ったものを作りました。 //再帰呼び出し unsigned long Fibonacci(int n) < if(n==1)< return 1;>//初項 else if(n==2) < return 1;>//第2項 return Fibonacci(n-1) + Fibonacci(n-2); > //配列 unsigned long Fibonacci(整数の公式でフィボナッチ数列を求める int n) < unsigned long long f[101]; int i; f[1] = 1; f[2] = 1; for( i=3; ireturn f[n]; > この二つを比較すると明らかに配列の方が早いです。 ということは再帰呼び出しはあまり使わない方がよいってことですよね? この場合は配列も似たような感じで見ることができますし。 それとも自分の再帰の書き方が悪いのでしょうか。

Fnをn番目のフィボナッチ数として F2n=(Fn+1)^2-(Fn-1)^2 (2n番目=n+1番目の二じょうとn-1番目の二条の差) というのと リュカ数列との関係式 Fn+1 + 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める Fn-1 =Ln+1 n+1とn-1番目のフィボナッチ数の差はn+1番目のリュカ数 の2つの式の説明お願いできますか?

フィボナッチ数列とルーカス数列(リュカ数列)使った証明です。 L(n)をルーカス数列のn番目の数字、F(n)をフィボナッチ数列のn番目の数字として、 L(0) = 2, L(1) = 1 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める F(0) = 0, F(1) = 1 の場合、 L(n) = F(n-1) + F(整数の公式でフィボナッチ数列を求める n+1) になることを証明しようと思ってます。 ビネの公式を使って証明しようと思ったんですが、うまく行きませんでした。それに、もっと簡単な方法があると思うんですが、どなたかわかりませんか?

フィボナッチ数列の性質についてです。 ・左から数えて5番目ごとの数字は5で割り切れる。 ・(初項+第2項+第3項・・・・・+第n項) =第n項×(第n項+1) ・フィボナッチ奇数番目のフィボナッチ数をじゅんにたすと、最後の次の数になる。 ・フィボナッチ偶数番目のフィボナッチ数をじゅんにたすと、最後の次の数から1ひいたものになる。 ・フィボナッチ3つ続いたフィボナッチ数の、外2つをかけたものから中の2乗をひくと、(かわりばんこに)1か-1になる。 上のような性質があるのですが、これを数学的(記号などを使って)に表すとどのように書けますか?

1 一般解で、nが無限大なれば Fn/Fn-1は、如何なる値に近づくか。またnが、マイナス無限大になればいかなる値にちかづくか。 2 フィボナッチ数列の一般解は、nが整数でなく実数値の場合、複 素数が現れる。nが1/2の場合の解の値を、代入して求めよ。 回答と解説お願いします

整数の公式でフィボナッチ数列を求める

フィボナッチ数列{1,1,2,3,5,8,13,21,34・・・}と黄金比 Φ 整数の公式でフィボナッチ数列を求める には、いろいろな関係がありそうです。
フィボナッチ数列 < Fn > の定義式は F1=1、F2=2、 FnFn-1Fn-2 (n≧3)(以下、この関係式を漸化式とよぶ。)でした。定義式からフィボナッチ数列の各項はすべて整数であることは明らかですね。このとき、n番目の数をいちいち足していかなくても求められると便利ですよね。つまり第n項を直接求められる式がほしいわけです。数学では、数列の隣接3項間漸化式から一般項を求める問題を解いた人にはお馴染みですが、ちょっと考えてみましょう。
フィボナッチ数列の漸化式 FnFn-1Fn-2 ・・・①に準じて r n = r n-1 + r n-2 ・・・②を満たす(ゼロでない)r の累乗 r n の数列が存在するか調べてみましょう。②の両辺を r n-2 で割ると、 r 2 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める = r + 1 つまり r 2 - r - = 0

とすると r = Φ または r = Φ’ のとき、累乗 r n はフィボナッチ数列の漸化式①を満たすということです。このことから、
問1 A と B を定数とするとき、任意の数列 Kn = A Φ n +B Φ’ n ・・・③も①の漸化式を満たしていることを確かめてください。
問2 ここで K1K2 を 1として、A と B を求めてください。

フィボナッチ数列の等式

(1) $F_k+F_ = F_$ $(1 \leqq k \leqq n)$ の辺々を加えると \[\sum _^nF_k+\sum _^nF_ = \sum _^nF_\] となるから, \[\sum _^nF_k+\sum _^F_k = \sum _^F_k = F_+\sum _^F_k-F_2\] が成り立つ. 両辺から $\displaystyle\sum _^F_k$ を引くと, 求める等式が得られる. (2) (i) $F_1 = F_2 = 1$ から, $n = 1$ のとき等式が成り立つ. (ii) $n = m$ ($m$: 正の整数)のとき等式が成り立つとすると, \[\begin\sum 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める _^mF_+F_ &= F_+F_ \\ &= F_ = F_ \end\] となり, $n = m+1$ のとき等式が成り立つ. (i), (ii) から, 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める すべての正の整数 $n$ に対して, 等式が成り立つ. (3) (i) $F_2 = F_3-1 = 1$ から, $n = 1$ のとき等式が成り立つ. (整数の公式でフィボナッチ数列を求める ii) $n = m$ ($m$: 正の整数)のとき等式が成り立つとすると, \[\begin \sum _^mF_+F_ &= F_-1+F_ \\ &= F_-1 = F_-1 \end\] となり, $n = m+1$ のとき等式が成り立つ. (i), (ii) から, すべての正の整数 $n$ に対して, 等式が成り立つ.

ゼッケンドルフの定理

定理《ゼッケンドルフの定理, ゼッケンドルフ, $1939$ 年》

定義《ゼッケンドルフ表現》

定理の証明

    整数の公式でフィボナッチ数列を求める
  • $i_1 = 2$ のとき. \[ n-1 = F_+\cdots +F_\] は $n-1$ のゼッケンドルフ表現である.
  • $i_1 > 2,$ $i_1$ が奇数のとき. $F_-1 = F_2+\cdots +F_$ であるから, \[ n-1 = F_2+\cdots +F_+F_+\cdots +F_\] であり, これは $n-1$ 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める のゼッケンドルフ表現である.
  • $i_1 > 2,$ $i_1$ が偶数のとき. $F_-1 = F_3+\cdots +F_$ であるから, \[ n-1 = F_2+\cdots +F_+F_+\cdots +F_\] であり, これは $n-1$ のゼッケンドルフ表現である.

例《ゼッケンドルフ表現》

$1$ から $12$ までの整数は, \[\begin 1 &= F_2, & 7 &= F_5+F_3, \\ 2 &= F_3, & 8 &= F_6, \\ 3 &= F_4, & 9 &= 整数の公式でフィボナッチ数列を求める F_6+F_2, \\ 4 &= F_4+F_2, & 10 &= F_6+F_3, \\ 5 &= F_5, & 11 &= F_6+F_4, \\ 6 &= F_5+F_2, & 12 &= F_6+F_4+F_2 \end\] と表される.

カッシーニの公式

定理《カッシーニの公式, $1680$ 年》

シューブの公式

定理《シューブの公式, $1950$ 年》

(i) 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める $5F_0<>^2+4 = 4 = L_0<>^2$ から, $n = 0$ のとき等式が成り立つ. (ii) $n > 0$ のとき. フィボナッチ数列とリュカ数列の相互関係, カッシーニの公式により, \[\begin L_n<>^2-4\< F_n<>^2+(-1)^n\> &= (F_+F_)^2-4F_F_ \\ &= (F_-F_)^2 = F_n<>^2 \end\] となるから, $5F_n<>^2+4(整数の公式でフィボナッチ数列を求める -1)^n = L_n<>^2$ が成り立つ. (i), (ii) から, すべての非負整数 $n$ に対して等式が成り立つ.

フィボナッチ数の判定法

定理《フィボナッチ数の判定法, ゲッセル, $1972$ 年》

証明: $(\Longleftarrow )$ の証明は $2$ 次体の整数論を用いると簡潔に記述できる(高校数学の範囲で証明できる, 後述).

$(\Longrightarrow )$ は, シューブの公式から従う.
$(\Longleftarrow )$ を示す. $5\cdot 0+4 = 2^2$ は平方数であり, $0 = F_0$ はフィボナッチ数であるから, $\nu > 0$ とする. $5\nu ^2\pm 4$ が平方数であるとする. このとき, 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める ある非負整数 $\mu$ を用いて \[ 5\nu ^2\pm 4 = \mu ^2 \quad \cdots [1]\] と書ける. $\mu ^2-5\nu ^2 = \pm 4$ であるから, \[\frac<\mu +\nu\sqrt 5>\cdot\frac<\mu -\nu\sqrt 5> = \pm 1 \quad \cdots [2]\] が成り立つ. $[1]$ から $\mu ^2 \equiv \nu ^2 \pmod 2$ であるので, $\mu$ と $\nu$ の偶奇は一致する. よって, $\varepsilon = \dfrac<\mu +\nu\sqrt 5>$ は $2$ 次体 $K = \mathbb Q(\sqrt 5)$ の整数環 $O_K$ に属する. さらに, $[2]$ から $\varepsilon$ のノルムは $\pm 1$ であるので, $\varepsilon$ は $O_K$ の単数である. $\varphi = \dfrac,$ $\tilde\varphi = \dfrac$ とおく. $O_K$ の単数は $\pm\varphi ^n$ ($n$: 整数) の形に表されるが, $\nu > 0$ から $\varepsilon > 1$ であり, $\varphi > 1$ であるので, ある正の整数 $n$ について $\varepsilon = \varphi ^n$ となる. よって, ビネの公式により, \[\varepsilon = \frac<(\varphi ^n+\tilde\varphi ^n)+(\varphi ^n-\tilde\varphi ^n)> = \frac\] が成り立つ. $1,$ $\sqrt 5$ は $\mathbb Q$ 上線形独立であるから, 両辺の $\sqrt 5$ の係数を比較すると, $\nu = F_n$ が得られる.

  • $d$ 整数の公式でフィボナッチ数列を求める を $4$ で割った余りが $1$ であるとし, 偶奇の等しい整数 $a_1,$ $a_2$ を用いて $\dfrac$ の形に表される実数全体の集合を $O_K$ とおく($K$ の整数環(ring of integers)と呼ぶ). このとき, $O_K$ のすべての要素 $\varepsilon$ に対して, \[\varepsilon ^ \in O_K \iff N(\varepsilon ) = \pm 整数の公式でフィボナッチ数列を求める 1\] が成り立つ(この条件を満たす $O_K$ の要素 $\varepsilon$ を $K$ の単数(unit), その全体を $K$ の単数群(unit group)と呼ぶ). さらに, $\varepsilon _0<>^ \in O_K,$ $\varepsilon _0 > 1$ を満たす $O_K$ の要素 $\varepsilon _0$ で, 次の条件を満たすものが存在する($\varepsilon _0$ を $K$ の基本単数(fundamental unit)と呼ぶ): $\varepsilon ^ \in O_K$ を満たす $O_K$ のすべての要素 $\varepsilon$ は 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める $\varepsilon = \pm\varepsilon _0<>^n$ ($n$: 整数)の形に表される. $d = 5$ のとき, $\varepsilon _0 = \dfrac$ である.
  • 有理数 $a_1,$ $a_2,$ $b_1,$ $b_2$ に対して, \[ a_1+a_2\sqrt d = b_1+b_2\sqrt d \Longrightarrow (整数の公式でフィボナッチ数列を求める a_1,a_2) = (b_1,b_2)\] が成り立つ($1,$ $\sqrt d$ は有理数体 $\mathbb Q$ 上線形独立(linearly independent)であるという).

高校数学の問題

問題《$2$ 次体のノルムと単数》

有理数 $a_1,$ $a_2$ を用いて \[\alpha = a_1+a_2\sqrt 5\] の形に表される実数 $\alpha$ 全体の集合を $K$ とおき, この $\alpha$ に対して \[\tilde\alpha = a_1-a_2\sqrt 5, \quad N(\alpha ) = \alpha\tilde\alpha = a_1<>^2-5a_2<>^2\] と定める. (1) $K$ の要素 $\alpha,$ $\beta$ に対して, \[ N(\alpha\beta ) = N(\alpha )N(\beta )\] が成り立つことを示せ. また, 偶奇が等しい整数 $a_1,$ $a_2$ を用いて \[\alpha = \dfrac\] の形に表される実数 $\alpha$ 全体の集合を $O$ とおく. (2) $O$ の要素 $\alpha,整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める $ $\beta$ に対して, $\alpha\beta$ もまた $O$ の要素であることを示せ. (3) $O$ の要素 $\alpha$ に対して, $N(\alpha )$ は整数であることを示せ. (4) $O$ の要素 $\varepsilon$ に対して, \[\varepsilon ^ \in O \iff N(\varepsilon ) = \pm 1\] が成り立つことを示せ. (5) $O$ に属する, $\varepsilon _0<>^ \in O,$ $\varepsilon _0 > 1$ を満たす最小の正の数は $\varepsilon _0 = \dfrac$ であることが知られている. $\varepsilon ^ \in O$ を満たす $O$ の要素 $\varepsilon$ は, この $\varepsilon _0$ を用いて $\varepsilon = \pm\varepsilon _0<>^n$ ($n$: 整数)の形に表されることを示せ.

問題《ゼッケンドルフの定理》

$F_1 = F_2 = 1,$ $F_ = F_n+F_$ で定まる数列 $\< F_n\>$ を「フィボナッチ数列」と呼ぶ. すべての正の整数 $n$ に対して, $[*]$ $n$ は「フィボナッチ数列」の隣り合わない項の和として表せる が成り立つことを示せ. ただし,「フィボナッチ数列」の項そのものも項数が $1$ の和として考える.

問題《カッシーニの公式》

数列 $\< F_n\>$ について, 初期条件 $F_1 = F_2 = 1$ のもとで, $[1]$ $F_ = F_n+F_$ $[2]$ $F_<>^2-F_nF_ = (-1)^n$ は同値であることを示せ.

厳選!フィボナッチ・フルコース~フィボナッチ数のマニアックな世界へ~

ただし、\(F_1=F_2=1\)とします。これは漸化式といって、前の番号の数の情報によって新たな数が構成されていく仕組みになっています。こうして得られる数列をフィボナッチ数列、そしてフィボナッチ数列に現れる数をフィボナッチ数と呼びます。
フィボナッチ数は前2つの数を足すことによって構成していきます。例えば、1番目と2番目は\(1\)であることから3番目は\(1+1=2\)。4番目は\(1+2=3\)、5番目は\(2+3=5\)となります。最初のいくつかのフィボナッチ数を求めてみましょう。

2.フィボナッチ・フルコース

①.フィボナッチ数の整除性(オードブル)

\(p\) を\(5\)で割って\(1\)または\(4\)余る素数とする(たとえば\(11\), \(19\)など)。このとき\(p-1\)離れたフィボナッチ数たちの差は必ず\(p\)の倍数になる。つまり、以下が成り立つ。

これは中々エキゾチック。ちょっと確かめてみましょう!
\(p=11\) とします。適当に8番目のフィボナッチ数\(F_8=21\)をとってきましょう。定理によると\(p-1=10\)個進んだ18番目のフィボナッチ数\(F_\)を見てみます。すると\(整数の公式でフィボナッチ数列を求める F_=2584\)。結構大きい数になりますね。果たして差は\(11\)の倍数になるのでしょうか?さっそく計算してみましょう。

$$F_-F_9=4181-34=4147=11 \times 377$$

②.Lameの定理(スープ)

なんと、Euclidの互除法の回数は\(5n\)回で評価できるのです。しかも、隣り合うフィボナッチ数のペアの場合、最も作業回数が多い(めんどくさい)とのこと!
例えば、\(144\)と\(89\)のペアを考えて互除法を行いましょう。このとき小さい方の\(89\)の桁は\(2\)桁なので、定理によると\(5\times 2=10\)回も互除法を行わなければならないようです。実際に

最速のフィボナッチ数計算を考える

さらに、フィボナッチ数列の漸化式が \(F_=F_n+F_\) だったことを思い出せば、\begin
F_&=F_mF_+F_F_n-F_mF_n,\\
F_&=F_mF_n+F_F_
\endという2本の式が得られる。つまり、行列の乗算の代わりに\[(F_m,F_)\cdot(F_n,F_)\mapsto(F_mF_+F_F_n-F_mF_n,F_mF_n+F_F_)\]という演算を使って計算できる。

\((F_n,F_)\) の形の組を FibPair と呼ぶことにすれば、 FibPair には\[(a,b)\cdot(a’,b’)\mapsto(a b’+ba’-aa’,aa’+bb’)\]によるモノイド演算(単位元は \((F_0,F_1)=(0,1)\))が定まる(結合法則の確認は読者の演習問題とする)。Haskellでの実装例は次のようになる:

ここで、 stimesMonoid は、モノイドの \(n\) 乗を \(n\) の二進展開を利用して高速に(O(log n)で)計算してくれる関数である(同様のアルゴリズムは、行列の \(n\) 乗の計算にも利用していた)。

このFibPairを使って 123456789 ( およそいちおく ) 番目のフィボナッチ数を計算した場合と、一般の2×2行列の方法 (MatFib) での計算時間を比較してみる。

整数 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める n に対して n 番目(および n+1 番目)のフィボナッチ数 \((F_n,F_)\) を対応させる写像は、整数の加法に関するモノイドから、FibPairへのモノイド準同型だとみなせる。

Fast doubling

Haskellのべき乗 (^) やモノイドのn倍 stimesMonoid では、nを二進展開したものを「右から左に」辿って計算する、ということをやっている。

例えば、 a の19乗(二進法で10011)を計算したいというときは、アルゴリズム的には次のようなことを行なっている:

  1. Y := 1, Z := a とおく。
  2. n=19 の最下位ビット(1の位)は 1 なので、Y に Z をかける(Y := 整数の公式でフィボナッチ数列を求める Y * Z)。
  3. Z を自乗する(Z := Z * Z)。
  4. n=19 の下から2番目のビット(2の位)は 1 なので、 Y に Z をかける(Y :整数の公式でフィボナッチ数列を求める = Y * Z)。
  5. Z を自乗する(Z := Z * Z)。
  6. n=19 の下から3番目のビット(4の位)は 0 なので、 Y には何もしない。
  7. Z 整数の公式でフィボナッチ数列を求める を自乗する(Z := Z * Z)。
  8. n=19 の下から4番目のビット(8の位)は 0 なので、 Y には何もしない。
  9. Z を自乗する(Z := Z * 整数の公式でフィボナッチ数列を求める Z)。
  10. n=19 の下から5番目のビット(16の位)は 1 なので、 Y に Z をかける(Y := Y * Z)。
  11. n は二進法で5桁なので、これでアルゴリズムを終了する。 Y は a の19乗である。

一つの式で書けば、\[a^=a\cdot a^2\cdot (((a^2)^2)^2)^2\]と計算していることになるだろう。

  1. Y := 1 とおく。
  2. n=19 の最上位ビット(16の位)は 1 なので、 Y に 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める a をかける(Y := Y * a)。
  3. Y を自乗する(Y := Y * Y)。
  4. n=19 の上から2番目のビット(8の位)は 0 なので、 Y には何もしない。
  5. Y を自乗する(Y := Y * Y)。
  6. n=19 の上から3番目のビット(4の位)は 0 なので、 Y には何もしない。
  7. Y を自乗する(Y := 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める Y * Y)。
  8. n=19 の上から4番目のビット(2の位)は 1 なので、 Y に a をかける(Y := Y * a)。
  9. Y を自乗する(Y := Y * Y)。
  10. n=19 の上から5番目のビット(2の位)は 1 なので、 Y に a をかける(Y := Y * a)。
  11. 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める
  12. n は二進法で5桁なので、これでアルゴリズムを終了する。 Y は a の19乗である。

一つの式で書けば、\[a^=(((a^2)^2)^2\cdot a)^2\cdot a\]と計算していることになるだろう。

「右から左」と「左から右」の比較だが、計算機上では整数の二進表記を「右から左」に辿る方が実装しやすい(ひたすら2で割って、あまりを見れば良い)。そのため、「右から左」が使われることが多い。実際、Haskellのべき乗 (^) や stimesMonoid もそうなっている。

(二進表記の「右から左」と「左から右」のアルゴリズムについては、The Art 整数の公式でフィボナッチ数列を求める of Computer Programming Vol. 2 に記載がある)

さて、「左から右」には、「右から左」にはない特徴がある。それは、アルゴリズム中で使う乗算が「自乗」と「a をかける」の2種類だけ、ということだ。この特徴と、フィボナッチ数計算 (FibPair) の事情を組み合わせるとどうなるか。

n乗のアルゴリズムをフィボナッチ数計算に使う場合、 a としては組 \(\operatorname(1)=(F_1,整数の公式でフィボナッチ数列を求める F_2)=(1,1)\) を用いる。そして、「a をかける」という操作は、「次のフィボナッチ数を計算する」ということであり、足し算1回でできてしまう:\[(F_n,F_)\cdot (1,1)=(F_,F_n+F_)\]「右から左」の場合は(自乗のほかに) FibPair 整数の公式でフィボナッチ数列を求める の演算が3回必要だったところ、「左から右」なら多倍長整数の加算3回で済んでしまうのだから、「左から右」の方が有利である。

この「左から右」に辿る方法をフィボナッチ数に適用したものは、fast doubling と呼ばれているようだ。二進表記を「左から右」に辿るため、実装の際に末尾ではない再帰呼び出しを使うことになる。

Fast doubling をHaskellで実装すると次のようになる:

この時点ですでに FibPair + stimesMonoid よりも早くなっているが、いくつかの小細工を加えるとさらに早くなる。

まず、ここまできたらもはや FibPair の汎用的なモノイド演算は必要ない。モノイドとしての自乗 p <> p さえ計算できれば十分で、これは\[(a,b)整数の公式でフィボナッチ数列を求める \cdot(a,b)=(2ab-a^2,a^2+b^2)=(a(2b-a),a^2+b^2)\]で計算できる。モノイド演算では多倍長整数の乗算が4回、加減算が3回だったのが、自乗であれば多倍長整数の乗算が4回、加減算が2回となる。

そして、「FibPair を自乗してから次のフィボナッチ数を計算する」部分はひとまとめにできる。つまり、コード上は p <> p と 整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める FibPair b (a + b) に分かれていたのを、

実験(実行時間の計測)

筆者の環境(MacBook Pro (Late 2013), GHC 8.6.3)では、行列を使った版で123456789番目のフィボナッチ数を計算したところ11秒程度、FibPairとstimesMonoidを使った版で同じ計算をしたところ5秒程度、fast doublingを使った版(最後に載せた、タプルを使ったコード)では1.7秒程度かかった。

なお、記事の最初の方で書いた、一般項を \(\mathbf(\sqrt)\) で計算するやつ(\(\left(\frac<1+\sqrt>\right)^n\) の計算だけで済ませる)は、5秒程度だった。こちらは有理数計算を伴うため、整数演算のみのFastDoublingには勝てないのだろう(推測)。

結論として、この記事で触れたアルゴリズムの中では fast doubling が一番早い。

おまけ:多倍長計算の特性を考慮する

演算回数でいうと、A, B どちらも乗算が4回、加減算が3回ずつである。では、どちらを使っても同じなのだろうか。この辺の話は、演算対象となる型によって変わってくる。

仮に、変数 a , a' , b , b' のいずれもn桁の整数だとしよう。すると、Aの方は

    整数の公式でフィボナッチ数列を求める 整数の公式でフィボナッチ数列を求める
  • n桁の整数同士の乗算が4回
  • 2n桁の整数同士の加減算が3回
  • n桁の整数同士の乗算が4回
  • 2n桁の整数同士の加減算が2回
  • n桁の整数同士の加減算が1回

余談:HaskellのSemigroup/Monoidには自乗するためのメソッドがない

モノイドの元のn乗を計算する際、「左から右」「右から左」のいずれも、モノイドの元の自乗 \(x^2\) の計算を利用した。Data.SemigroupやData.Monoidには積を計算するメソッド <> はあるが、自乗に特化されたメソッドはないので、自乗の計算には積演算 <> が使われることになる。

自乗に特化されたメソッドがあると何が嬉しいかというと、インスタンスによっては一般の積演算 <> よりも高速な実装を提供できる可能性があり、 整数の公式でフィボナッチ数列を求める stimesMonoid のような関数がそれを利用できるようになることである。 sconcat や stimes がクラス外の関数ではなくて Semigroup クラスの中で定義されているのと同じ理由である。もちろん「自乗するメソッド」のデフォルト実装は \x -> x <> x とする。

コードで書けば、 Semigroup クラスがこういう風に定義されていてほしい:

FibPairの場合に、この「自乗する」 twice 整数の公式でフィボナッチ数列を求める メソッドがあるとどの程度嬉しいか。FibPairのモノイド演算は次のように定義されていた:

(fast doublingの説明で同じことを書いたが)こちらは多倍長整数の乗算が4回、多倍長整数の加減算が2回で、加減算が1回減った上に乗算1回分が定数 2 の掛け算に変わっている。

先ほどリンクを貼った実験プログラムでは、 FibPair の自乗で特化したコードを使うようにしたものを FibPairX という名前(名付けが雑だ)で実装しており、それぞれ234567890番目のフィボナッチ数を計算させてみると

という風に FibPairX の方が若干早い。

(このことから、GHCの最適化器は \x -> x <> x というコードを式変形して上記の twice の実装に変えるようなことは行わない、ということがわかる。数学的に同値な式でも多倍長整数のコストを考えると優劣があるのは「おまけ:多倍長計算の特性を考慮する」で見た通りなので、コンパイラーが勝手にそういう式変形を行わないことはプログラマーにとっては生成コードを予測できるということであり、良いことなのだが。)

関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる