The computation Binet's formula is bottlenecked by computing ϕn\phi^n. This requires the same number of multiplications as MnM^n, if both use repeated squaring. Computing a matrix product requires at least three integer multiplications, however.

The win for the matrix method is that you don't need all of those digits at the very start. The very first multiplication requires however many bits of precision we use for the last one in Binet's formula, but with integers the first values are small and very fast.

Which will be faster? Let's test them and find out. But there's one thing we should do first...

The computation Binet's formula is bottlenecked by computing ϕn\phi^n. This requires the same number of multiplications as MnM^n, if both use repeated squaring. Computing a matrix product requires at least three integer multiplications, however.

The win for the matrix method is that you don't need all of those digits at the very start. The very first multiplication requires however many bits of precision we use for the last one in Binet's formula, but with integers the first values are small and very fast.

Which will be faster? Let's test them and find out. But there's one thing we should do first...