VietMX Staff asked 3 years ago
There is actually a simple mathematical formula called Binet’s formula for computing the nth Fibonacci number, which does not require the calculation of the preceding numbers:
It features the Golden Ratio (φ):
φ = (1+sqrt(5))/2or
Complexity Analysis
Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).
Implementation
static double inverseSqrt5 = 1 / Math.Sqrt(5);static double phi = (1 + Math.Sqrt(5)) / 2;/* should use const double inverseSqrt5 = 0.44721359549995793928183473374626 const double phi = 1.6180339887498948482045868343656*/static int Fibonacci(int n) { return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);}