- 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.