# [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 重點整理

$\left \{ \begin{array}{**lr**} F_{2n}=F_n\cdot(2\cdot F_{n+1}-F_n) \\ F_{2n+1}=F_{n+1}^2+F_{n}^2\end{array} \right.$

* If n is even, we need to find $F_k$, where $k=\dfrac{n}{2}$ since $n=2k$. Then we can use $[F_k, F_{k+1}]=[F_{n/2}, F_{n/2+1}]$ to calculate $[F_{2k}, F_{2k+1}]=[F_{n}, F_{n+1}]$
* If n is odd, we need to find $F_k$, where $k=\dfrac{n-1}{2}$ since $n=2k+1$. Then we can use $[F_k, F_{k+1}]=[F_{(n-1)/2}, F_{(n-1)/2+1}]$ to calculate $[F_{2k}, F_{2k+1}]=[F_{n-1}, F_{n}]$ and then get $[F_n, F_{n+1}]$ by $[F_{n}, F_{n-1} + F_n]$