Advanced Fibonacci Computations
The standard dynamic programming approach to compute the -th Fibonacci number takes time. However, for extremely large numbers, or when a quick mathematical approximation is needed, we can use Binet’s Formula and Fast Doubling .
Explanation
1. Binet’s Formula (The Approximation)
- The Fibonacci sequence is intimately connected to the Golden Ratio .
- Binet’s formula allows us to compute the -th Fibonacci number directly using floating-point math:
- Since becomes infinitesimally small as grows, we can safely drop it and just round the remaining term to the nearest integer:
- Limitation: Floating-point precision breaks down around . It is best used for competitive programming tricks when is small and time is strictly required.
2. Fast Doubling (The Exact Method)
- Fast Doubling is derived from Matrix Exponentiation but optimized to skip the matrix multiplication overhead.
- Given a pair , we can compute using the following formulas:
- By evaluating bits of from highest to lowest, we can compute exactly in steps, making it capable of calculating the millionth Fibonacci number in milliseconds.
Implementation
import math
# O(1) Binet's Formula (Accurate up to ~n=70 due to floating point precision)
def fibonacci_binet(n):
phi = (1 + math.sqrt(5)) / 2
return round((phi ** n) / math.sqrt(5))
# O(log N) Fast Doubling Algorithm (Accurate for any size n)
def fibonacci_fast_doubling(n):
def _fib(n):
if n == 0:
return (0, 1)
else:
a, b = _fib(n >> 1) # recursive divide by 2
c = a * (2 * b - a) # F(2k)
d = a * a + b * b # F(2k+1)
if n & 1: # if n is odd
return (d, c + d)
else: # if n is even
return (c, d)
return _fib(n)[0]
# Example Usage
print(f"Binet F(10): {fibonacci_binet(10)}")
print(f"Fast Doubling F(100): {fibonacci_fast_doubling(100)}")#include <iostream>
#include <cmath>
#include <utility>
// O(1) Binet's Formula
long long fibonacci_binet(int n) {
double phi = (1 + std::sqrt(5)) / 2;
return std::round(std::pow(phi, n) / std::sqrt(5));
}
// O(log N) Fast Doubling Algorithm
// Returns pair {F(n), F(n+1)}
std::pair<long long, long long> fibonacci_fast_doubling(int n) {
if (n == 0) return {0, 1};
auto p = fibonacci_fast_doubling(n >> 1);
long long a = p.first; // F(k)
long long b = p.second; // F(k+1)
long long c = a * (2 * b - a); // F(2k)
long long d = a * a + b * b; // F(2k+1)
if (n & 1) return {d, c + d}; // Odd
return {c, d}; // Even
}
int main() {
std::cout << "Binet F(10): " << fibonacci_binet(10) << "\n";
std::cout << "Fast Doubling F(90): " << fibonacci_fast_doubling(90).first << "\n";
return 0;
}
Key Takeaways
- Use Binet’s Formula for constant time calculations on small inputs where floating-point inaccuracies aren’t an issue.
- Use Fast Doubling for exact calculations for massive inputs, outperforming standard dynamic programming approaches.