フィボナッってみた

なにも新しい事はやってない。

再帰を使わなければ簡単に書ける。

function fib(n) {
  if (n < 1)  return 1;

  var [a, b] = [0, 1];
  for (var i = 1; i < n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

再帰を使ったものだと、↓とか参考になる。

最も簡単に fib を高速化する方法 - ドレッシングのような

この方法は、再帰を使わないコードと比べても可読性が落ちずに書けてていいな。

function fib(n) {
  function _fib(n) {
    if (n <= 1) return [1, 0];
    var [a, b] = _fib(n-1);
    return [a + b, a]; 
  }
  return _fib(n)[0];
}

テストしてみる。
コードは、
Re: 斜め上 - JavaScriptで遊ぶよ - g:javascript
から借用。

function test(n) {
  var t = new Date;
  for (var i = 0; i < 1000; i++) {
    var res = fib(n);
  }
  t = new Date - t;
  console.log('| ' + n + ' | ' + res + ' | ' + t + ' | ' + (t/n).toFixed(2) + ' |'); // はてな記法
}

for (var i = 1; i < 79; i++) {
  test(i);
}


はえ

i 番目 フィボナッチ数 所要時間 (ms / 1000回) 時間 / i
1 1 2 2.00
2 1 3 1.50
3 2 4 1.33
4 3 5 1.25
5 5 5 1.00
6 8 5 0.83
7 13 7 1.00
8 21 8 1.00
9 34 8 0.89
10 55 9 0.90
11 89 10 0.91
12 144 10 0.83
13 233 11 0.85
14 377 13 0.93
15 610 13 0.87
16 987 14 0.88
17 1597 15 0.88
18 2584 16 0.89
19 4181 17 0.89
20 6765 18 0.90
21 10946 18 0.86
22 17711 20 0.91
23 28657 20 0.87
24 46368 20 0.83
25 75025 22 0.88
26 121393 25 0.96
27 196418 30 1.11
28 317811 35 1.25
29 514229 31 1.07
30 832040 29 0.97
31 1346269 26 0.84
32 2178309 28 0.88
33 3524578 28 0.85
34 5702887 28 0.82
35 9227465 31 0.89
36 14930352 32 0.89
37 24157817 186 5.03
38 39088169 44 1.16
39 63245986 37 0.95
40 102334155 30 0.75
41 165580141 30 0.73
42 267914296 32 0.76
43 433494437 32 0.74
44 701408733 33 0.75
45 1134903170 34 0.76
46 1836311903 35 0.76
47 2971215073 36 0.77
48 4807526976 37 0.77
49 7778742049 38 0.78
50 12586269025 39 0.78
51 20365011074 39 0.76
52 32951280099 40 0.77
53 53316291173 40 0.75
54 86267571272 42 0.78
55 139583862445 45 0.82
56 225851433717 48 0.86
57 365435296162 49 0.86
58 591286729879 51 0.88
59 956722026041 193 3.27
60 1548008755920 64 1.07
61 2504730781961 76 1.25
62 4052739537881 45 0.73
63 6557470319842 46 0.73
64 10610209857723 47 0.73
65 17167680177565 49 0.75
66 27777890035288 49 0.74
67 44945570212853 54 0.81
68 72723460248141 63 0.93
69 117669030460994 72 1.04
70 190392490709135 58 0.83
71 308061521170129 56 0.79
72 498454011879264 57 0.79
73 806515533049393 57 0.78
74 1304969544928657 202 2.73
75 2111485077978050 68 0.91
76 3416454622906707 79 1.04
77 5527939700884757 57 0.74
78 8944394323791464 57 0.73