CODEWITHSUNDEEP
algorithm
Eugene Lau
Eugene Lau

Reputation: 11

How to improve my Fibonacci Generation JavaScript

How to make this fibonacci more clean and possibly performance increase?

function fibonacci(n) {
  var array = [];
  if (n === 1) {
    array.push(0);
    return array;
  } else if (n === 2) {
    array.push(0, 1);
    return array;
  } else {
    array = [0, 1];
    for (var i = 2; i < n; i++) {
      var sum = array[array.length - 2] + array[array.length - 1];
      array.push(sum);
    }
    return array;
  }
}

Upvotes: 1

Views: 115

Answers (2)

urmat abdykerimov
urmat abdykerimov

Reputation: 452

There is a way to get the N-th Fibonacci number in log(N).
All you need is to raise the matrix
| 0 1 |
| 1 1 |
to the power N using binary matrix exponentiation
This is really useful for really big N while a traditional algorithm is gonna be slow.

links to materials:
https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/
https://www.youtube.com/watch?v=eMXNWcbw75E

Upvotes: 1

Louis Ricci
Louis Ricci

Reputation: 21086

If you want to optimize your Fibonacci then pre-calculate a bunch of values (say up to 64 or even higher depending on your use-case) and have those pre-calculated values as a constant array that your function can use.

const precalcFibonacci = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842];
function fibonacci(n) {
  if(n <= 0) return [];
  if(n < 65) return precalcFibonacci.slice(0, n);
  else {
    let array = precalcFibonacci.slice();
    for(let i = 64, a = precalcFibonacci[62], b = precalcFibonacci[63]; i < n; i++) {
      array[i] = a + b;
      a = b;
      b = array[i];
    }
    return array;
  }
}

Upvotes: 1

Related Questions