# Fibonacci Sequence

Anything larger than 1 million are approximations.

## Nth Fibonacci Number Algorithm

This tool can compute large Fibonacci numbers because it uses the fast doubling algorithm, which is O(logn).

The standard Fibonacci algorithm can be converted to O(logn) time by taking advantage of exponentiation by squaring. To do this, we use matrices. A matrix can be thought of as operations on data. For example, \begin{bmatrix} 1 \\ 1 \end{bmatrix} is a function summing 2 columns and \begin{bmatrix} 1 \\ 0 \end{bmatrix} is a function that copies the first column and ignores the second column. Similarly, the matrix \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} adds 2 columns and stores the result in the first column. It also moves the original first column to the new second column. Repeat this function n times to get the nth Fibonacci number. \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^n can be computed in O(logn) time using exponentiation by squaring.

We can simplify the exponents of matrices to the equations fib(2n) = fib(n) * (2fib(n + 1) - fib(n)) and fib(2n + 1) = fib(n + 1)^2 + fib(n)^2. These are the equations used for this tool.

There's also a closed form formula: fib(n) = \dfrac{ (\dfrac{1+\sqrt{5}}{2})^n - (\dfrac{1-\sqrt{5}}{2})^n }{\sqrt{5}}. Since most people assume arithmetic operations are O(1), this is considered O(1). However, for large numbers, this is actually slower than the O(logn) solution because it's expensive to keep track of so many decimal digits.

For numbers larger than the 1 millionth Fibonacci number, I used an approximation that only calculates the first few digits.