Fibonacci matrix

2×2 matrix power — Fib.

Try this in Python

def mat_mul(a, b):
    return [
        [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
        [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
    ]

base = [[1, 1], [1, 0]]
print(mat_mul(base, base))

Key takeaways

• Fast pow on matrix.
• Mod multiply.
• Fast doubling shortcut.