フィボナッチ数列の計算法（3）

前に、

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は整数だとすると、ふつうは2³¹-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;

}