Fibonacci via Fast Doubling

What this is?

A self‑contained explainer that computes selected Fibonacci numbers exactly using the fast‑doubling identities. It shows the Answer (exact values and digit counts), the Reason why (the identities used), and a Check harness that verifies base cases, the recurrence, an addition identity, and cross‑checks against a simple linear iterator.

Time per Fn is O(log n); everything is integer‑exact with BigInt.

Answer

Reason why

Define Fibonacci by F0=0, F1=1, and Fn+2=Fn+1+Fn.

A standard addition identity (provable by induction) is:

(A)   Fm+n = Fm·Fn+1 + Fm−1·Fn   (for m,n ≥ 1)

Specializing (A) yields fast‑doubling from (Fk, Fk+1):

  • F2k = Fk ( 2Fk+1 − Fk )
  • F2k+1 = Fk+12 + Fk2

One recursive call on k=⌊n/2⌋ computes both F2k and F2k+1, then picks (Fn, Fn+1) by parity.

Check (harness)