I've never notice that there's actually a formula for Fibonacci series. The only time I've ever written a program to calculate F(n) for Fibonacci was when I was learning how to use dynamic programming to reduce runtime.
A tutorial of this kind will typically start with something like this:
function f(n) {
if (n <= 1) return n;
return f(n - 1) + f(n - 2);
}This method is bad because it calculates the same results multiple times which we only need to calculate each Fibonacci number once. As result, this method uses exponential time to finish. We can make it faster by memoization. To do this, we can create an array to store each Fibonacci number we've calculated. It looks something like this:
int fib[max];
function f(n) {
if (n <= 1) {
fib[n] = n;
return n;
}
if (fib[n] != 0) return fib[n];
fib[n] = f(n - 1) + f(n - 2);
return fib[n];
}This way, we can reduce runtime to O(n) where each number is only calculated once. However, this can be further reduced with the formula f(a + b + 1) = f(a + 1) * f(b + 1) + f(a) * f(b). By picking a and b near n/2, we can reduce the run by half each time which gives the runtime log(n).
int fib[max];
function f(n) {
if (n <= 1) {
fib[n] = n;
return n;
}
// if n is 2, f(a + 1) will also be 2 which
// will cause a infinite loop
if (n == 2) return 1;
if (fib[n] != 0) return fib[n];
int a, b;
if (n % 2 == 1) {
a = (n - 1) / 2;
b = a;
} else {
a = n / 2;
b = a - 1;
}
fib[n] = f(a + 1) * f(b + 1) + f(a) * f(b);
return fib[n];
}However, all of this is not necessary because there is actually a formula so that we can computer any Fibonacci number in constant time.
To find a formula, we first need to know that Fibonacci like series satisfy the following two properties:
A Fibonacci like series is any series that satisfies \( F(n) = F(n - 1) + F(n - 2) \).
- Any Fibonacci like series times a constant is still a Fibonacci like series
- The addition of two Fibonacci like series is still a Fibonacci like series
So, if we can find 2 Fibonacci like series that we already know what the formulas are. Then, we can find a way so that the linear combination of the two satisfy \( F(0) = 0 \) and \( F(1) = 1 \). To find a Fibonacci like series that we know how to solve, we can start with power series as we already know that the equation of a power series is \( F(n) = ax^n \).
Assuming there is a power series that is also a Fibonacci like series. That is:
\[ F(n) = F(n - 1) + F(n - 2) \] \[ ax^n = ax^{n - 1} + ax^{n - 2} \] \[ x^2 = x + 1 \] \[ x = \frac{1 + \sqrt{5}}{2} or \frac{1 - \sqrt{5}}{2} \]
From here, we can pick \( x = \frac{1 + \sqrt{5}}{2} \) and try to find a by matching \(F(0) = 0\) and \(F(1) = 1\). However, you will soon find that there is no such a that matches. But since we know that any linear combination of two Fibonacci like series are also Fibonacci like, we can use both x to satisfy:
\[ F(0) = a \cdot (\frac{1 + \sqrt{5})}{2})^0 + b \cdot (\frac{1 - \sqrt{5}}{2})^0 = 0 \] \[ F(1) = a \cdot (\frac{1 + \sqrt{5})}{2})^1 + b \cdot (\frac{1 - \sqrt{5}}{2})^1 = 1 \]
From here, we can finally solve a and b such that \( a = \frac{1}{\sqrt{5}} \) and \( b = \frac{-1}{\sqrt{5}} \). Thus, the final formula is \( F(n) = \frac{(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n}{\sqrt{5}} \). That gives us the final constant runtime code as the following:
function f(n) {
return (pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n)) / sqrt(5);
}This this how we can calculate Fibonacci in constant time.