週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
フィボナッチ数列は、次の式で定義される数列です。
f(0) = 0
f(1) = 1
f(n+2) = f(n+1) + f(n)
この数列の特定の項、例えばf(55)とかを求めたいとします。

1.定義式をそのまま使う
これはやってはいけないとされています。やってもいいですが時間がかかります。
このアルゴリズムでは、f(55)を求めるのにf(54)を1回、f(53)を2回、f(52)を3回、f(51)を5回...
計算してしまいます。計算時間がf(n)の値そのものと同程度、おおよそO(1.6n)くらいかかります。

2.小さい数から順番に求める。
nの小さいときのf(n)の値を覚えておいて、その値を用いてf(n)の大きい方の値を順次求めていきます。計算時間はO(n)。

3.一般項
この漸化式には一般項が存在します。
α = (sqrt(5)-1)/2
β = -(sqrt(5)+1)/2
f(n) = (αn - βn)/sqrt(5)

これを代入すればすぐに求まります。


教科書には、1より2の方が速いですよ~と書いてあります。
実は3の方がO(1)で求まるので速いのでは。。

私は重要なことを忘れていました。桁数です。
3の一般項にある通り、この数列はべき乗で増えていきます。よって、桁数がO(N)のオーダー、具体的にはNが
log(10)/log(α) ~ 5
増えるごとに一桁増加します。
数が大きくなって、32bitや64bitといったコンピュータに扱いやすい数字を超えると、桁数に応じて計算時間がかかるようになります。

例えば、3をO(N)より速く求めるのには条件が必要です。
I. αnをO(N)より速く求めることができる
II.f(n)のすべての桁を正確に求めることが要求されない。
後者は、f(n)がO(N)桁になるので、すべての桁を表示するだけでO(N)かかるという話です。

しかしよく考えると、手順2すらO(N)の計算時間では計算できないことがわかります。f(n+2)をf(n+1)とf(n)の値から計算する場合、これらの項がO(N)の桁数を持っているので、足し算にO(N)の時間がかかります。よって、手順2の計算時間はO(N2)になります。

どちらが有利なのかわからなくなりました。手順3としても、もし問題がf(N)の値を正確に知りたいのだとすると、一般項から正確な値を出すのにどれだけの時間がかかるのかよくわかりません。

まとめ:
桁数が大きくなると、計算時間に桁数を考慮する必要があります。

感想:
3がO(1)で終わらないことに気づいたのに、同じ理論で2がO(N)で終わらないことには気づかず日記を書き始めました。そのため収拾がつかなくなっています。
スポンサーサイト
コメント
この記事へのコメント
並列計算ができるかどうかも考慮汁、とか言ってみる。
雰囲気的には3が速そう
2007/04/30(月) 17:06 | URL | 3d@ #-[ 編集]
2の方法はO(n)の計算回数かかりますが

フィボナッチ数列を
f(n+2) = 1 1 f(n+1)
f(n+1) = 1 0 f(n+0)
とベクトルの漸化式とみなせば、
行列の累乗した要素で一般項を表せます。

同時にこの累乗桁数を無視すればはO(log n)で計算できます。

よって、
手順2ではO(N^2) かかっていたものが、
行列乗算を使えば O(N log N) で計算できます。

さて一般項に関してですが
晩御飯食べてから考えますw
2007/04/30(月) 18:40 | URL | とし #-[ 編集]
> 行列乗算を使えば O(N log N) で計算できます。
行列乗算中の多倍長乗算忘れてた

FFTとかでがんばってO(N log N)で乗算して
O(N {log N}^2)かな?

さて晩飯食べていないけど3の方法について考察
α = (sqrt(5)+1)/2 = a + ε
とすると(a:αの近似値、ε:誤差項)
α^n = a^n + na^(n-1)ε + ...
となって
フィボナッチ数列の1桁目まで一致させるには
na^(n-1)ε < 1.0
が必要

というわけで
ε < 1/na^(n-1)
よって
αをO(n)位計算しておく必要がある

あとはαのn乗を計算するので
乗算1回にO(N log N)
乗算の回数がO(log N)

結局
O(N {log N}^2)
で行列の場合とかわらないっぽい
2007/04/30(月) 19:21 | URL | とし #-[ 編集]
3d@>
並列性を考慮するとさらに3が速そう..

とし>
追補どうも
3とかの正確な求め方とかなぜか全然思いつかなかった。
必要桁数求めて多倍長やって終わりなのね。

でも、
行列のn乗の一般項 と 漸化式の一般項は
計算式は全く同じです。


よく考えると、2と3はアルゴリズムの粒度が違う気がします
3だとアルゴリズムが「この式を精度よく求める何か」
でよいのに対し、2だと「この手順で求めてください」
になっていて自由が少なそうです。
2はちょっと改変すると到底2には見えない、
さらには3と同じものになってしまいます。
2007/05/01(火) 13:35 | URL | Gus #-[ 編集]
http://www004.upp.so-net.ne.jp/s_honma/fibonacci/fibonacci.htm
リンク先の性質5が使えないかと思いましたが、それではあまり ^n 計算と変わらなさそうですね。
2007/05/01(火) 14:49 | URL | 白のカピバラ #-[ 編集]
とし>
よく考えたら2の行列のn乗と3の一般項は、行列を対角化しているかどうかの違いがありました。同じものかと思ってしまった。ごめん。

しかし対角化しても計算時間がほとんど変わらないというのはちょっと面白いかも。

白のカピパラ>
この性質知りませんでした。<sub>2n</sub>C<sub>n</sub>を途中の式をすっ飛ばして計算できるのとにたように高速にできるかも。
しかし^n計算が既に途中の項をすっ飛ばしているので、やはり変わらないかもしれません。
2007/05/01(火) 23:55 | URL | Gus #-[ 編集]
むしろポイントは定数サイズの行列に対する演算はすべからく通常の数と同じオーダーになることではないか、と言ってみる。
2007/05/02(水) 10:27 | URL | chun #-[ 編集]
chun>
あ、うん、なるほど。
2×2行列の累乗は対角化すると考慮するスカラーが4つから2つに減るけど、それは定数倍の効果しかない。
さらにこれらはスカラーの累乗と計算時間が変わらない。

「複素数の演算の計算時間オーダーは実数と変わらない」と書くと当然に見える。行列の演算でもそれは変わらない。

こんな感じかな。
2007/05/02(水) 14:49 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/176-f00387c4
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。