Fibonacci Sequence: The Binet Formula
In 1843, Jacques Philippe Marie Binet developed a mathematical formula expressing Fibonacci numbers in closed form. However, the same formula was derived by Abraham de Moivre a century earlier and was also known by Euler and Bernoulli.
Binet's formula is the following (phi corresponds to the golden ration, that is, 1.618):
Note that Binet's formula runs in linear time, that is, it grows linearly with the size of the input. This is considered to be a slow method, since it's performance is similar to the Dynamic Programming method.
My implementation of Binet's formula to compute the nth Fibonacci sequence number corresponds to: