動的計画法でフィボナッチ数列の計算を速くする。

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブックを読んでます。
このブログ書いているときに気づいたけど、第二版出るのね。
第一版は図書館で借りているだけなので、第二版が出たら買わなきゃ。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

動的計画法

Node.jsのウィークポイントの一つはフィボナッチ数列計算に代表されるCPUプリエンプティブな処理であると言われています。
そのウィークポイントも今回リリースのIsolatesという機能で改善されていますが、今回はその話ではなく、プログラミングコンテストチャレンジブックで記載されていた動的計画法でフィボナッチ数列計算がどの位高速になるのかを確かめてみたいと思います。

その前に動的計画法をおさらい。

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。分割統治法がトップダウン的な手法であるのに対し、動的計画法はボトムアップ的な手法といえる。
「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンによって最初に使われた。 動的計画法の応用としては、最短経路の問題やナップサック問題、行列の積の計算に対する応用が挙げられる。多項式時間での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似多項式時間では最適解を得ることができる。ネットワーク、近似アルゴリズムの分野で研究されている。
by Wikipedia

まぁ正直フィボナッチ数列をJavascriptで効率的に計算する方法はamachangさんやdanさんなんかの著名人がたくさんやっているんですが。

最初に思いつく方法

function fibonacci(n) {
  if (n<=2) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

var result = fibonacci(40);
console.log(result);

いわゆる、O(2^n)で実現されている方法ですね。
これはかなり遅いです。40番目の数列(fib(40) = 165580141)を出すのにNode.js v0.7.0でも以下の時間がかかります。
■実行時間

real 0m1.953s
user 0m1.883s
sys 0m0.024s

なんで遅いかというと、fibonacci(40)の値を出力するのにfibonacci(39)とfibonacci(38)を呼びださなきゃいけなくなり、
fibonacci(39)がfibonacci(38)とfibonacci(37)を呼び出し、fibonacci(38)は・・・
と、このように呼び出し回数が指数的に増えるから遅くなってしまうんですね。

動的計画法でのやり方(その1)

function fibonacci(n) {
  var num1 = 1,
      num2 = 1,
      tmp = 1;
  for (var i = 1; i<n; i++) {
    tmp = num1 + num2;
    num1 = num2;
    num2 = tmp;
  }
  return tmp;
}

var result = fibonacci(40);
console.log(result);

これが動的計画法で解いた場合の方法ですね。
といっても特に難しいことはなく、3つの変数を使って足しあわせを行っているだけですね。
でもこれでO(2^n)の処理がO(n)で実現できます。

■実行時間(動的計画法その1)

n = 40
real 0m0.072s
user 0m0.062s
sys 0m0.008s

かなり高速なことがわかります。

ただこれでもO(n)なので、数が多くなると不安です。
自分が検証した感じでは、10^10以上になるとかなりレスポンスが遅くなります。

■実行時間(動的計画法その1)

n = 10000000000
real 0m42.578s
user 0m42.620s
sys 0m0.344s

動的計画法でのやり方(その2)
プログラミングコンテストチャレンジブックに書いてある方法で実施すると、
繰り返し二乗法を使って O(log n)で求める方法が紹介されていました。

これならさらに短時間で処理できます。

function mul(a, b) {
  var c = initialize(c, a.length, b[0].length);
  for (var i=0; i<a.length; i++) {
    for (var k=0; k<b.length; k++) {
      for (var j=0; j<b[0].length; j++) {
        c[i][j] = (c[i][j] + a[i][k] * b[k][j]);
      }
    }
  }
  return c;
}

function pow(a, n) {
  var b = initialize(b, a.length, a.length);
  for (var i=0; i<a.length; i++) {
    b[i][i] = 1;
  }
  while (n>0) {
    if (n & 1) b = mul(a, b);
    a = mul(a,a);
    n >>= 1;
  }
  return b;
}

function initialize(m, xlen, ylen) {
  m = new Array(xlen);
  for (var i=0; i<m.length; i++) {
    m[i] = new Array(ylen);
    for (var j=0; j<m[i].length; j++) {
      m[i][j] = 0;
  }}
  return m;
}

function fibonacci(n) {
  var a = new Array(2);
  a[0] = new Array(2);
  a[1] = new Array(2);
  a[0][0] = 1; a[0][1] = 1;
  a[1][0] = 1; a[1][1] = 0;
  a = pow(a, n+1);
  return a[1][0];
}


var result = fibonacci(10000000000);
console.log(result);

プログラムとしては一気に分かりにくくなりましたが、
行列演算を思い出してもらうと分かりやすくなります。

フィボナッチ数列の漸化式は以下のようになっています。

このを

としておくと、、、、
とべき乗すれば行列の左下の要素がフィボナッチ数列になっていることがわかります。

つまり、フィボナッチ数列の漸化式は

となり、を求めればフィボナッチ数列を求めることができます。

はであれば以下のように2乗をk回繰り返せば求まります。

これの延長で2乗と掛け算を繰り返せば全ての整数を表現でき、
のように表すことができます。
例：
これを使って
となり、べき乗を効率的にO(log n)で解くことができます。

べき乗の計算を効率的にしている箇所が以下のコードです。

 while (n>0) {
    if (n & 1) b = mul(a, b);
    a = mul(a,a);
    n >>= 1;
  }

一見すると何をしているかよくわかりませんが、
毎回1ビットずつずらしていき、最下位ビットが1だったら掛け算a×b。
それ以外だったら2乗をしていますa^2。

■実行時間(動的計画法その2)

n = 10000000000
real 0m0.067s
user 0m0.057s
sys 0m0.007s

O(log n)なので、10^10の数字でも高速に解けるようになりました。
シングルスレッドNode.jsでもこの時間なら使えるよね、って事でやっぱり
アルゴリズムは重要ですな。

もう少しで読み終わるので、読み終わったらまたレビューを書きます。

ちなみにdanさんのやり方も面白いので、ぜひ見てみてください。
公式を使ったやり方やメモ化を利用して高速化しています。
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ