Matrix nth-term Fibonacci calculator benchmark

fib.py

import time


def time_me(func):
	def wrap(*arg):
		start = time.monotonic_ns()
		r = func(*arg)
		end = time.monotonic_ns()
		print(f"{func.__name__} ({(end - start) / 1000000} ms)")
		return r
	return wrap


def i_fib(n):
	if n < 3:
		return 1
	else:
		a, b, i = 1, 1, 2
		while i < n:
			a, b, i = b, a + b, i + 1
		return b


# from https://stackoverflow.com/a/23462371/4688876
# breaking n into bits reduces big O to O(log n)
def matrix_fib(n):
	v1, v2, v3 = 1, 1, 0  # initialise a matrix [[1,1],[1,0]]
	# perform fast exponentiation of the matrix (quickly raise it to the nth power)
	# starts from the 2nd most significant bit
	for rec in bin(n)[3:]:
		calc = v2 * v2
		v1, v2, v3 = v1 * v1 + calc, (v1 + v3) * v2, calc + v3 * v3
		if rec == '1':
			v1, v2, v3 = v1 + v2, v1, v2
	return v2


start, limit = 10, 1_000_000

if __name__ == "__main__":
	funcs = [i_fib, matrix_fib]
	i = start
	while i <= limit:
		l = [time_me(func)(i) for func in funcs]
		print(i, all(x == l[0] for x in l))
		i *= 10

Printout from a 6th gen i5 CPU:

i_fib (0.0 ms)
matrix_fib (0.0 ms)
10 True
i_fib (0.0 ms)
matrix_fib (0.0 ms)
100 True
i_fib (0.0 ms)
matrix_fib (0.0 ms)
1000 True
i_fib (0.0 ms)
matrix_fib (0.0 ms)
10000 True
i_fib (172.0 ms)
matrix_fib (0.0 ms)
100000 True
i_fib (11703.0 ms)
matrix_fib (125.0 ms)
1000000 True