前に、
http://blog.livedoor.jp/dankogai/archives/50958771.html
を見て、フィボナッチ数の計算がO(1)なのはちょっと気持ち悪いがいいんじゃない?と思ったが、この続きのような記事を見て、ハッとした。
http://blog.livedoor.jp/dankogai/archives/50962361.html
こういうところでは、ランダウのビッグ・オーを使ってはいけないのだ。
例えば、ある計算のためのアルゴリズムが2つあったとして、それぞれ計算量(計算時間のほうがわかりやすいか)が、
A1 : 1000
A2 : n
だったとする。
ランダウの記法を使うと、
A1 : O(1)
A2 : O(n)
A2のほうがnが小さいときは速いが、nが1000より大きくなればA1のほうが速くなる。実際の計算時間の式を見なくても、ランダウの記法を使った式を見れば、nが十分大きければA1のほうが速くなることがわかる。nは整数だとすると、ふつうは231-1まであるので、そこまでO(1)のアルゴリズムがO(n)のアルゴリズムより速くならないことはまずありえない。
しかし、今話題のフィボナッチ数の場合は、nは80ビット浮動小数点数を使っても、nは84までなのだ。これだとビッグ・オーを見ただけではなんともいえない。nは十分に大きくならないのかもしれないのだから。
この先はどうでもいいことなのだが、
うちでDで計算させてみたら、ふつうに足し算するO(n)のほうは、だいたいそのグラフにあるような感じだったけど、公式を使うほうはそんなに最適化が効かなくて、むしろ足し算のO(n)より遅いくらいなんだけど(第2項無視すれば逆転する)。
そもそも、expってそんなに速かったっけ?
import std.cstream;
import std.math;import std.date;
import std.process;void main(char[][] args) {
d_time starttime = getUTCtime();
real sum = 0;
for(int k = 0; k < cast(int)1e6; k++) {
for(int i = 80; i < 85; i++) {
sum += fib1(i);
}
}
dout.writefln("%.3fs %e",
cast(double)(getUTCtime() - starttime) / TicksPerSecond, sum);
d_time starttime2 = getUTCtime();
real sum2 = 0;
for(int k = 0; k < cast(int)1e6; k++) {
for(int i = 80; i < 85; i++) {
sum2 += fib2(i);
}
}
dout.writefln("%.3fs %e",
cast(double)(getUTCtime() - starttime2) / TicksPerSecond, sum2);
}real fib1(int n) {
return (pow( (1.0L + sqrt(5.0L)) / 2, n)
- pow( (1.0L - sqrt(5.0L)) / 2, n)) / sqrt(5.0L);
}ulong fib2(int n) {
ulong a = 1L;
ulong b = 1L;
ulong tmp;
for(int i = 3; i <= n; i++) {
tmp = a + b;
a = b;
b = tmp;
}
return b;
}