@@ -3,25 +3,37 @@
3  *
4  * For n = 30, the expected result is 1,346,268.
5  *
6- * Uses iterative O(n) approach with running sum — no recursion,
7- * no string conversions, single pass.
6+ * Uses the identity: sum(F(0)..F(n-1)) = F(n+1) - 1
7+ * F(n+1) computed via fast doubling in O(log n).
8  */
9 export function sumFibonacci(n: number): number {
10   if (n <= 0) return 0;
11+  // sum(F(0)..F(n-1)) = F(n+1) - 1
12+  return fibFast(n + 1) - 1;
13+}
14 
12-  let sum = 0;
13-  let prev = 0;
14-  let curr = 1;
15-
16-  // F(0) = 0
17-  sum += prev;
18-
19-  for (let i = 1; i < n; i++) {
20-    sum += curr;
21-    const next = prev + curr;
22-    prev = curr;
23-    curr = next;
15+/**
16+ * Fast doubling: computes F(n) in O(log n) time.
17+ * Returns F(n) using the identities:
18+ *   F(2k)   = F(k) * (2*F(k+1) - F(k))
19+ *   F(2k+1) = F(k)^2 + F(k+1)^2
20+ */
21+function fibFast(n: number): number {
22+  let a = 0; // F(0)
23+  let b = 1; // F(1)
24+  let bit = 1 << (31 - Math.clz32(n));
25+  while (bit > 0) {
26+    // doubling step
27+    const d = a * (2 * b - a);
28+    const e = a * a + b * b;
29+    a = d;
30+    b = e;
31+    if (n & bit) {
32+      const c = a + b;
33+      a = b;
34+      b = c;
35+    }
36+    bit >>>= 1;
37   }
25-
26-  return sum;
38+  return a;
39 }