@@ -2,22 +2,33 @@
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- * Combined with iterative O(n) fibonacci computation.
5+ * Computes F(n+1) via O(log n) fast doubling:
6+ *   F(2k) = F(k) * (2*F(k+1) - F(k))
7+ *   F(2k+1) = F(k)^2 + F(k+1)^2
8  *
9  * For n = 30, the expected result is 1,346,268.
10  */
11 export function sumFibonacci(n: number): number {
12   if (n <= 0) return 0;
11-  if (n === 1) return 0; // F(0) = 0
13+  if (n === 1) return 0;
14 
13-  // Compute F(n+1) iteratively — sum of first n fibs = F(n+1) - 1
15+  return fastFib(n + 1) - 1;
16+}
17+
18+function fastFib(n: number): number {
19+  if (n <= 0) return 0;
20   let a = 0;
21   let b = 1;
16-  for (let i = 2; i <= n + 1; i++) {
17-    const next = a + b;
18-    a = b;
19-    b = next;
22+  for (let bit = 1 << (31 - Math.clz32(n)); bit > 0; bit >>>= 1) {
23+    const d = a * (2 * b - a);
24+    const e = a * a + b * b;
25+    if (n & bit) {
26+      a = e;
27+      b = d + e;
28+    } else {
29+      a = d;
30+      b = e;
31+    }
32   }
21-
22-  return b - 1;
33+  return a;
34 }