We can see that, practically, there's not actually much of a difference here. For small nn matrix multiplication is faster, as noted above, but Binet's formula doesn't manage to save much by multiplying one number instead of several each iteration. One thing I haven't mentioned is that computing 5\sqrt{5} to the number of digits required, and computing the division and rounding, is a nontrivial part of the final runtime—for these sizes, it seems to cancel out any benefit of doing fewer multiplications.

Surely there are still ways to improve. Perhaps there's some way to meld these approaches and do better still?

plot

We can see that, practically, there's not actually much of a difference here. For small nn matrix multiplication is faster, as noted above, but Binet's formula doesn't manage to save much by multiplying one number instead of several each iteration. One thing I haven't mentioned is that computing 5\sqrt{5} to the number of digits required, and computing the division and rounding, is a nontrivial part of the final runtime—for these sizes, it seems to cancel out any benefit of doing fewer multiplications.

Surely there are still ways to improve. Perhaps there's some way to meld these approaches and do better still?

plot