fibonacci.py

import math

SQRT_5 = math.sqrt(5)
PHI1 = (0.5, 0.5)
PHI2 = (0.5, -0.5)

def s5n_sub(s5n_1, s5n_2):
	(a, b) = s5n_1
	(c, d) = s5n_2
	return (a - c, b - d)

# Compute (a + bsqrt(5))(c + dsqrt(5))
def s5n_mul(s5n_1, s5n_2):
	(a, b) = s5n_1
	(c, d) = s5n_2
	return (a * c + 5 * b * d, a * d + b * c)

# Compute (a + bsqrt(5))^2
def s5n_square(s5n):
	(a, b) = s5n
	return (a * a + 5 * b * b, 2 * a * b)

# Compute (a + bsqrt(5))^n
def s5n_powi(s5n, n):
	if n == 0: return (1, 0)
	elif n == 1: return s5n
	elif n & 1 == 0: return s5n_powi(s5n_square(s5n), n >> 1)
	elif n & 1 == 1: return s5n_mul(s5n, s5n_powi(s5n_square(s5n), (n - 1) >> 1))

def s5n_pretty(s5n):
	(a, b) = s5n
	return f"{a} + {b}sqrt(5)"

def s5n_eval(s5n):
	(a, b) = s5n
	return a + b * SQRT_5

def fib(n):
	(a, b) = s5n_sub(s5n_powi(PHI1, n), s5n_powi(PHI2, n))
	return b

for i in range(0, 50):
	print(fib(i))