@@ -1,11 +1,31 @@
1 /**
2+ * Precomputed sum of first n Fibonacci numbers for n = 0..78.
3+ * F(78) = 8944394323791464 is the largest Fibonacci that fits in a JS safe integer.
4+ * sum(F(0..n-1)) = F(n+1) - 1
5+ */
6+const SUM_TABLE: number[] = [];
7+{
8+  let a = 0;
9+  let b = 1;
10+  // SUM_TABLE[0] = F(1) - 1 = 0
11+  for (let i = 0; i <= 78; i++) {
12+    SUM_TABLE[i] = b - 1; // F(i+1) - 1
13+    const next = a + b;
14+    a = b;
15+    b = next;
16+  }
17+}
18+
19+/**
20  * Compute the sum of the first `n` Fibonacci numbers.
21  *
22  * For n = 30, the expected result is 1,346,268.
23  *
6- * Uses the identity: sum(F(0) + F(1) + ... + F(n-1)) = F(n+1) - 1
24+ * O(1) table lookup for n <= 78 (safe integer range), falls back to
25+ * fast doubling for larger n.
26  */
27 export function sumFibonacci(n: number): number {
28+  if (n <= 78) return SUM_TABLE[n];
29   return fibonacci(n + 1) - 1;
30 }
31 
@@ -20,23 +40,20 @@ export function sumFibonacci(n: number): number {
40 function fibonacci(n: number): number {
41   if (n <= 0) return 0;
42 
23-  let a = 0; // F(k)
24-  let b = 1; // F(k+1)
43+  let a = 0;
44+  let b = 1;
45 
26-  // Find the highest set bit
46   let bit = 1;
47   while (bit <= n) bit <<= 1;
48   bit >>= 1;
49 
50   while (bit > 0) {
32-    // Double: compute F(2k) and F(2k+1)
51     const d = a * (2 * b - a);
52     const e = a * a + b * b;
53     a = d;
54     b = e;
55 
56     if (n & bit) {
39-      // Add one: F(k+1) = F(k) + F(k-1)
57       const c = a + b;
58       a = b;
59       b = c;