Fibonacci
Speed Race
How large can F(n) get in exactly one second?
O(log n) ring exponentiation meets FFT-accelerated arithmetic. F(1,000,000) in 85ms. Sequential computation from F(1) until time runs out. A benchmark of algorithmic elegance on Apple Silicon.
Fibonacci numbers grow fast
F(100) has 21 digits. F(1,000) has 209 digits. F(10,000) has 2,090 digits. The naive recursive algorithm? O(2ⁿ) operations. Even the iterative approach requires O(n) additions of increasingly massive numbers.
The question isn't whether we can compute large Fibonacci numbers. It's how large we can go in exactly one second, computing each F(n) from scratch, no memoization.
Computing in ℤ[√5]
The golden ratio φ = (1 + √5)/2 connects directly to Fibonacci: F(n) is the nearest integer to φⁿ/√5. But we can do better than floating point approximation.
By working in the ring ℤ[√5] = {a + b√5 | a, b ∈ ℤ}, we get exact integer arithmetic. Binary exponentiation gives us φⁿ in O(log n) multiplications, and F(n) is simply the √5 coefficient.
F(1,000,000) in ~20 multiplications, not a million additions.
When numbers get huge
Standard multiplication is O(n²) where n is digit count. At 200,000+ digits, that's 40 billion operations per multiply. The FFT transforms this into O(n log n).
The key insight: converting BigInts to FFT format via division was O(n²). Bit extraction makes it O(n), giving a 500× speedup for F(1,000,000).
F(1,000,000) has 209,000 digits. FFT + O(n) conversion makes this tractable.
Built for Apple Silicon
Swift concurrency, vectorized DSP, and glassmorphic SwiftUI
O(log n) Exponentiation
Binary powering in ℤ[√5] ring reduces millions of operations to just ~20 multiplications. F(1,000,000) in 85ms.
FFT Multiplication
Accelerate framework's vDSP FFT enables O(n log n) multiplication with O(n) digit conversion. 500x faster than naive.
Caching & Pooling
FFT setup caching and buffer pooling eliminate allocation overhead. 3x constant factor improvement.
Real-time Visualization
Live logarithmic graph shows computation time growth, making the exponential complexity visible.
Tech Stack
Native performance meets mathematical elegance
Interested in high-performance computing?
We build software that pushes hardware to its limits. Let's talk about your next challenge.