1】

F(2n-1)=F(n-1)^2 + F(n)^2

2】

F(2n)=F(n)*[F(n+1)+F(n-1)]

这里

F(n)、F(n+1)、F(n-1)、F(2n)和F(2n-1)分别表示第n个、第n+1个、第n-1个、第2n个和第2n-1个Fibonacci数。

证明了这两个公式，就可以快速计算第m个Fibonacci数。

例如计算F(1000)。

原来根据定义，需先计算F(998）和F(999)。

现在可利用公式2】，折半计算F(500)和F(499)。

而F(500)又可先折半计算F(250)和F(249)，同时据公式1】也得出了F(499)。

故可以把原先计算F(1000)所需计算999个F数，减少为仅需计算22个F数。