Commit546ce11

authored

Merge pull request#1455 from cp-algorithms/fibmatrix

Fibonacci: restore matrix power form

2 parents51d3953 +59c3174 commit546ce11Copy full SHA for 546ce11

File tree

+14

-1

lines changed

+14

-1

lines changed

Lines changed: 14 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -159,7 +159,20 @@ F_{n}`
`159`	`159`	`\end{pmatrix}`
`160`	`160`	`$$`
`161`	`161`
`162`		`-where $F_1 = 1, F_0 = 0$.`
	`162`	`+where $F_1 = 1, F_0 = 0$.`
	`163`	`+In fact, since`
	`164`	`+`
	`165`	`+$$`
	`166`	`+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}`
	`167`	`+= \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}`
	`168`	`+$$`
	`169`	`+`
	`170`	`+we can use the matrix directly:`
	`171`	`+`
	`172`	`+$$`
	`173`	`+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n`
	`174`	`+= \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}`
	`175`	`+$$`
`163`	`176`
`164`	`177`	`Thus, in order to find $F_n$ in $O(\log n)$ time, we must raise the matrix to n. (See [Binary exponentiation](binary-exp.md))`
`165`	`178`

Comments

(0)