• Interactive
  • Programmable
  • Open-source

Try it: change the matrix. See chapter 3 for why it works.

M = [[2, 1],
     [0, 1]]  

pie.scalar(M, out='M')

Try it: Fibonacci numbers from powers of a matrix. See chapter 18 for why it works.

def matmul(A, B):
    return [[sum(a * b for a, b in zip(row, col)) for col in zip(*B)] for row in A]

M = [[1, 1],
     [1, 0]]

# The top-right entry of M^n is the nth Fibonacci number.
P = M
for n in range(1, 11):   # try range(1, 101)
    print(n, P[0][1])
    P = matmul(P, M)

# Squaring jumps ahead: M^2, M^4, M^8, ... so M^n takes about log2(n) steps, not n.
def matpow(M, n):
    result = [[1, 0], [0, 1]]
    while n:
        if n & 1:
            result = matmul(result, M)
        M = matmul(M, M)
        n >>= 1
    return result

f = matpow(M, 10_000)[0][1]
print(f'The 10,000th Fibonacci number has {len(str(f))} digits:')
print(f)

Made with by Vinay Sisodia. Logos designed by Jo Hsu.