TypeScript: Memoized Fibonacci with bigint

Fibonacci numbers grow past the safe range of number quickly. Compute them exactly with bigint, remembering every value already worked out.

What to build

A program that answers Fibonacci queries with a shared cache and reports how many new values each query computed.

Requirements

  • Write fib(n: number): bigint with F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2), caching results in a Map<number, bigint> shared by all queries.
  • For each query n, print fib(N) = VALUE (new: K), where K is how many values were computed and stored during that query.

Input

Line 1: q. Then q lines, each a whole number n.

Output

q lines.

Constraints

1 ≤ q ≤ 20; 0 ≤ n ≤ 300.

Example

Input:

3
10
5
12

Output:

fib(10) = 55 (new: 11)
fib(5) = 5 (new: 0)
fib(12) = 144 (new: 2)

Why it works

bigint keeps every digit, while a number loses precision after F(78); the cache turns an exponential recursion into one computation per value, and counting misses shows that later queries reuse earlier work.

Examples

Example 1 · Input
3
10
5
12
Expected output
fib(10) = 55 (new: 11)
fib(5) = 5 (new: 0)
fib(12) = 144 (new: 2)
Example 2 · Input
2
0
1
Expected output
fib(0) = 0 (new: 1)
fib(1) = 1 (new: 1)

Hints

Hint 1

Keep a Map<number, bigint> as the cache, and count how often a value is not found in it.

Hint 2

String(value) prints a bigint without the trailing n that console.log adds.

Solution

Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";
const cache = new Map<number, bigint>();
let computed = 0;

function fib(n: number): bigint {
  const known = cache.get(n);
  if (known !== undefined) return known;
  const value = n < 2 ? BigInt(n) : fib(n - 1) + fib(n - 2);
  cache.set(n, value);
  computed++;
  return value;
}

const q = Number(read());
for (let i = 0; i < q; i++) {
  const n = Number(read());
  const before = computed;
  const value = fib(n);
  console.log("fib(" + n + ") = " + String(value) + " (new: " + (computed - before) + ")");
}

Lesson: Typed functions →