Journal Archive

2022

function fib(n, memo = {}) {
  let bigN = BigInt(n);
  if (bigN in memo) return memo[bigN];
  if (bigN === 0n) return 0n;
  else if (bigN === 1n || bigN === -1n) return 1n;
  if (bigN > 0n) {
    memo[bigN] = fib(bigN - 2n, memo) + fib(bigN - 1n, memo)
    return memo[bigN];
  } else {
    memo[bigN] = fib(bigN + 2n, memo) - fib(bigN + 1n, memo)
    return memo[bigN];
  }
 }

Day 11: Solving one of the Kata on CodeWars

The Millionth Fibonacci Kata 3 kyu

In this kata you will have to calculate fib(n) where:

fib(0) := 0
fib(1) := 1
fin(n + 2) := fib(n + 1) + fib(n)

Write an algorithm that can handle n up to 2000000.
Your algorithm must output the exact integer answer, to full precision. Also, it must correctly handle negative numbers as input.

HINT I: Can you rearrange the equation fib(n + 2) = fib(n + 1) + fib(n) to find fib(n) if you already know fib(n + 1) and fib(n + 2)? Use this to reason what value fib has to have for negative values.