1

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;
  }
}
yun_jay
  • 1,050
  • 6
  • 20
Eugene Lau
  • 11
  • 1
  • 4
    Is there anything not working with the given script? If you are solely looking for improvements, https://codereview.stackexchange.com/ might be better suited for your request – Nico Haase Jun 29 '21 at 10:05
  • Is this helpful - https://stackoverflow.com/questions/7944239/generating-fibonacci-sequence ? Please put the language tag. – Daniel Hao Jun 29 '21 at 10:41
  • pre-allocate the `array` to size of `n` prior to `array.push` usage ... – Spektre Jun 30 '21 at 07:13

2 Answers2

1

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;
  }
}
Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
1

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

urmat abdykerimov
  • 427
  • 1
  • 7
  • 17
  • OP clearly wants the entire sequence up to n and all fast algorithms will get only few numbers not all of them ... – Spektre Jul 01 '21 at 06:13
  • 1
    From the link "As you can see from the chart, the matrix algorithm leaves the iterative algorithm behind starting from n = 300 (its worth noting that F_(94) will not fit into unsigned 64 bits)." For N > ~300 this is really neat. – Louis Ricci Jul 02 '21 at 22:46