```python
from sympy import *
```

Consider Fibonacci numbers $F_n$: $F_0 = 0, F_1 = 1, F_{n+2} = F_n + F_{n+1}$.


```python
def F(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return F(n-1) + F(n-2)

[F(n) for n in range(11)]
```




    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]



Denote $\Phi_{n+1} := \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}$

Then $\Phi_{n+2} = \begin{bmatrix} F_{n+2} \\ F_{n+1} \end{bmatrix} = \begin{bmatrix} F_{n+1} + F_n \\ F_{n+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \Phi_{n+1}$

So $\Phi_{n+1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \Phi_n$

Denote $A := \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

Then $\Phi_{n+1} = A \cdot \Phi_n = A^n \cdot \Phi_1 = A^n \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

Notice, that $A^n$ has form $\begin{bmatrix} p + q & q \\ q & p \end{bmatrix}$ for all natural $n$

Let's check it by induction


```python
p = IndexedBase('p')
q = IndexedBase('q')
m, n = symbols('m, n')
```


```python
def A(n):
    return Matrix([[p[n] + q[n], q[n]], [q[n], p[n]]])
```


```python
A(n)
```




$\displaystyle \left[\begin{matrix}{p}_{n} + {q}_{n} & {q}_{n}\\{q}_{n} & {p}_{n}\end{matrix}\right]$



Base case:


```python
A1 = A(1).subs({p[1]: 0, q[1]: 1}); A1
```




$\displaystyle \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]$



Induction step: 

If $A^n = \begin{bmatrix} p_i + q_i & q_i \\ q_i & p_i \end{bmatrix}$ for all natural $i \leqslant n$ \
then $A^n \cdot A = A^{n+1}$ with substitution $p_{n+1} = q_n, q_{n+1} = p_n + q_n$


```python
A(n) * A1
```




$\displaystyle \left[\begin{matrix}{p}_{n} + 2 {q}_{n} & {p}_{n} + {q}_{n}\\{p}_{n} + {q}_{n} & {q}_{n}\end{matrix}\right]$




```python
A(n+1).subs({p[n+1]: q[n], q[n+1]: p[n] + q[n]})
```




$\displaystyle \left[\begin{matrix}{p}_{n} + 2 {q}_{n} & {p}_{n} + {q}_{n}\\{p}_{n} + {q}_{n} & {q}_{n}\end{matrix}\right]$



Now we can get $\Phi_{n+1} = \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = A^n \cdot \Phi_1 = A^n \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} p_n + q_n & q_n \\ q_n & p_n \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ 

So $F_n = q_n = p_{n+1}, \quad F_{n+1} = p_n + q_n = q_{n+1}$

Let's compute $A^{m+n}$ by coefficients of $A^m$ and $A^n$


```python
Amn = A(n) * A(m); Amn
```




$\displaystyle \left[\begin{matrix}\left({p}_{m} + {q}_{m}\right) \left({p}_{n} + {q}_{n}\right) + {q}_{m} {q}_{n} & \left({p}_{n} + {q}_{n}\right) {q}_{m} + {p}_{m} {q}_{n}\\\left({p}_{m} + {q}_{m}\right) {q}_{n} + {p}_{n} {q}_{m} & {p}_{m} {p}_{n} + {q}_{m} {q}_{n}\end{matrix}\right]$




```python
p_mn = Amn[1, 1]; p_mn
```




$\displaystyle {p}_{m} {p}_{n} + {q}_{m} {q}_{n}$




```python
q_mn = Amn[0, 1]; q_mn
```




$\displaystyle \left({p}_{n} + {q}_{n}\right) {q}_{m} + {p}_{m} {q}_{n}$



Now we can use these formulas to fast compute of Fibonacci numbers (see **pmtests.lesson1.Fibonacci.fast()** method):

$\begin{cases}
p_{m+n} = p_m p_n + q_m q_n \\
q_{m+n} = \left( p_n + q_n \right) q_m + p_m q_n
\end{cases}$

Let's check its


```python
pn = [0] # pn[i] = p_mn[i+1]
qn = [1] # qn[i] = q_mn[i+1]

for i in range(1, 10):
    pn.append(p_mn.subs({m: i, n: 1}))
    qn.append(q_mn.subs({m: i, n: 1}))
    for j in range(i):
        pn[i] = pn[i].subs({p[j+1]: pn[j], q[j+1]: qn[j]})
        qn[i] = qn[i].subs({p[j+1]: pn[j], q[j+1]: qn[j]})

pn, qn
```




    ([0, 1, 1, 2, 3, 5, 8, 13, 21, 34], [1, 1, 2, 3, 5, 8, 13, 21, 34, 55])




```python
display(A1**2)
Amn.subs({m: 1, n: 1, p[1]: pn[0], q[1]: qn[0]})
```


$\displaystyle \left[\begin{matrix}2 & 1\\1 & 1\end{matrix}\right]$





$\displaystyle \left[\begin{matrix}2 & 1\\1 & 1\end{matrix}\right]$




```python
display(A1**3)
Amn.subs({m: 2, n: 1, 
          p[1]: pn[0], q[1]: qn[0],
          p[2]: pn[1], q[2]: qn[1]})
```


$\displaystyle \left[\begin{matrix}3 & 2\\2 & 1\end{matrix}\right]$





$\displaystyle \left[\begin{matrix}3 & 2\\2 & 1\end{matrix}\right]$




```python
display(A1**4)
Amn.subs({m: 2, n: 2, 
          p[1]: pn[0], q[1]: qn[0],
          p[2]: pn[1], q[2]: qn[1]})
```


$\displaystyle \left[\begin{matrix}5 & 3\\3 & 2\end{matrix}\right]$





$\displaystyle \left[\begin{matrix}5 & 3\\3 & 2\end{matrix}\right]$



a297115334a49cbf022ba560cb72b652a1661fda
ipynb
Jupyter Notebook
lesson1/fast_fibonacci.ipynb
anton0xf/progmsk_tests
00b65ef1f32c0c37baa24050d6e3003bb0ff2503
MIT
lesson1/fast_fibonacci.ipynb
anton0xf/progmsk_tests
00b65ef1f32c0c37baa24050d6e3003bb0ff2503
MIT
lesson1/fast_fibonacci.ipynb
anton0xf/progmsk_tests
00b65ef1f32c0c37baa24050d6e3003bb0ff2503
MIT
Qwen/Qwen-72B
1. YES
2. YES