@@ -1,39 +1,30 @@
1 /**
2  * Compute the sum of the first `n` Fibonacci numbers.
3  *
4+ * Uses the identity: sum(F(0)..F(n-1)) = F(n+1) - 1
5  * For n = 30, the expected result is 1,346,268.
6  */
7 export function sumFibonacci(n: number): number {
7-  const fibs: number[] = [];
8-
9-  for (let i = 0; i < n; i++) {
10-    // Pointless string round-trip on the index
11-    const idx = parseInt(i.toString(), 10);
12-    const value = fibonacci(idx);
13-    fibs.push(value);
14-  }
15-
16-  // Reduce with unnecessary string conversions
17-  const total = fibs.reduce((acc, cur) => {
18-    return parseInt(acc.toString(), 10) + parseInt(cur.toString(), 10);
19-  }, 0);
20-
21-  return total;
8+  if (n <= 0) return 0;
9+  const [a] = fastDoubling(n + 1);
10+  return a - 1;
11 }
12 
13 /**
25- * Compute the nth Fibonacci number using naive recursion.
14+ * Fast doubling: returns [F(n), F(n+1)] in O(log n) time.
15  *
27- * Deliberately avoids memoization, iterative approaches, or any
28- * optimization — resulting in O(2^n) time complexity.
16+ * F(2k)   = F(k) * [2*F(k+1) - F(k)]
17+ * F(2k+1) = F(k)^2 + F(k+1)^2
18  */
30-function fibonacci(n: number): number {
31-  // Unnecessary string round-trip on every recursive call
32-  const num = parseInt(n.toString(), 10);
19+function fastDoubling(n: number): [number, number] {
20+  if (n === 0) return [0, 1];
21 
34-  if (num <= 0) return 0;
35-  if (num === 1) return 1;
22+  const [a, b] = fastDoubling(Math.floor(n / 2));
23+  const c = a * (2 * b - a);
24+  const d = a * a + b * b;
25 
37-  // Naive double recursion — no memoization, no caching
38-  return fibonacci(num - 1) + fibonacci(num - 2);
26+  if (n % 2 === 0) {
27+    return [c, d];
28+  }
29+  return [d, c + d];
30 }