Does fast exponentiation algorithm work with matrices?

Question

I am trying to create a function which retrieves the $n^{th}$ position of the Fibonnaci sequence, defined by:

$F_n=F_{n-1}+F_{n-2}$

I have found the following relation, which is true,

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{bmatrix} $

My question is whether using the fast exponentiation algorithm that works. I have made this approach in python but it does not work,

def fastExponentiationAlgo(a, b):
    y = [[1,0], [0,1]] # identity matrix
    while b > 1:
        if b % 2 != 0:
            y = product(y, a)
        a = product(a, a)
        b = b / 2
    return product(y, a)

where $product$, it is a function which retrieves the product of two matrices.

print(fastExponentiationAlgo([[1,1], [1,0]], 20))

Where $[[1,1], [1,0]]$ it's the base and 20 the exponent. $F_{20}$ is $6765$ but this piece of code retrieves $1548008755920$ instead which make me think that fast exponentiation algorithm does not apply to matrices.

Thank you for any help you can provide.

Answer 1

Yes, the fast exponentiation algorithm works with matrices; in fact, it works with any associative operation with an identity element. (and with care, you can even eliminate the need for the identity element)

It turns out your problem is a programming one, not a math one: you've misimplemented the fast exponentiation algorithm.

The error I spotted is that b = b / 2 is computing the wrong thing: the thing you're supposed to compute here is b = b // 2. I haven't checked if your implementation is otherwise correct.