Discussion on: Let's Get Clever #1: Fibonacci Sequence

View post

// better space complexity
function fancyFib(n) {
  const computed = [0,1];
  if(n <= 1) return computed[n];
  for(i = 2; i <= n; i++)
    computed[i%2] = computed[0] + computed[1];
  return computed[n%2];
}

// maintains fidelity
function fibdelity(n) {
  const computed = [0,1];
  for(i = 2; i <= n; i++)
    computed.push(computed[i-1] + computed[i-2]);
  console.log(computed);
  return computed[n];
}

Here is the DP solution in javascript.
O(n) runtime complexity
O(1) space complexity

some loss in the fidelity of the computation since computations used to build upto fib(n) are lost.

maintaining fidelity would probably be better in practical use since saving the pre-computed values would lead to O(1) complexity for values already computed.

In compiled languages you could do this step in compile time and then cache them for O(1) runtime, but you would sacrifice some space O(n) space complexity

Jarod Smith • Aug 14 '19

for some reason I started on a mission to calculate fib of 1 million, so I edited the above code to include an execution time, and use big ints from javascript this let me calculate fib(1,000,000) in 88s

function bigFib(n)
{
  let start = process.hrtime();
  const computed = [0n,1n];
  for(i = 2; i <= n; i++) computed[i%2] = (computed[0] + computed[1]);
  hrend = process.hrtime(start);
  console.info('Execution time: %ds %dms', hrend[0], hrend[1] / 1e6);
  return computed[n%2];
}

Jason C. McDonald • Aug 14 '19 • Edited

+1 for one-upping yourself, mate! ;)

I wonder how long n=(2^63)−1 would take. It may not even be achievable. My own code won't even manage it.

...I should tweak the spec to limit it to (2^16)-1 ;)

Jarod Smith • Aug 15 '19

given 1e6 is 88s, and 2e63/1e6 = 9.223e12, I would guess 8.116e14 seconds or 25,737,466.3636 years

Jason C. McDonald • Aug 15 '19

So, not long at all. ;)

Jarod Smith • Aug 15 '19 • Edited

though JavaScript's Big Int library should allow for a number as big as your memory can hold. I think 4GB = 16gb = 16e+9 bits or digits, so theoretically if I could get absolute precision working with the closed form solution mentioned by edA‑qa mort‑ora‑y. Then the largest theoretical number I can handle would be 9.99999...e+16,000,000,000.