O(lon n)のフィボナッチ数のコード

Question

n番目のフィボナッチ数の下五桁を出力するプログラムを作成したいです。
A=
(1 1
1 0）
の行列を(見づらいですが...)ｎ上した時にA[0][1]とA[1][0]がフィボナッチ数になっているのはわかったのですがそのまま累乗を実装すると単純にO(log n)にはなりませんよね？

調べたところシフト演算とかが出たのですが、よくわかりませんでした。それをどのように利用するのでしょうか？

javaで実装しようとしているのですがやり方がわかればいいです。

Answer 1

実数の累乗で考えてみましょう。
実数aを50乗する場合、そのままaを50回掛けたのではO(n)です。
ところで、50は2進表記で110010なので、
50=2^5+2^4+2^1
です。つまり
a^50=a^(2^5+2^4+2^1)=a^(2^5)*a^(2^4)*a^(2^1)
となります。ここでa^(2^n)は
a^(2^2)=a^4=(a^2)^2
a^(2^3)=a^8=(a^4)^2
という具合に、2乗の繰り返しで求まるので、O(logn)で求められます。
これと全く同じ理屈で行列の累乗も可能です。

Answer 2

これでO(log n)になるはず。いちおうシフト演算も入れておきました:-)

double power(double x, int n) {
    if (n == 0) return 1.0;
    if (n & 1) return x * power(x, n - 1);
    return power(x * x, n >> 1);
}

使うときは、doubleの部分を行列の型に置き換えて下さい。

Comments

[Zuishin]

確かにそれでできるんですが、フィボナッチは再帰を使って簡単に書くことができます。行列の累乗で求めるということは再帰を避けたのではないでしょうか？

[swordone]

Javaでn&1という「数」をif文に入れることはできません。
if((n & 1) != 0)
でないといけません。