That algorithm can be de-obfuscated (see my top level post for the intuition). The above is equivalent to calculating a power of a 2x2 matrix, and since matrix

That algorithm can be de-obfuscated (see my top level post for the intuition). The above is equivalent to calculating a power of a 2x2 matrix, and since matrix multiplication is associative, we can use the squaring trick. In python (I left out the code for matrix multiplication for brevity) this becomes def nth_power_assoc(comp, f, n): """Reduce n copies of f with associative operation comp (short for composition, not compare).""" if n < 1: raise ValueError if n == 1: return f if n % 2 == 1: return comp(nth_power_assoc(comp, f, n - 1), f) else: g = nth_power_assoc(comp, f, n / 2) return comp(g, g) def fib(n): M = ((1, 1), (1, 0)) M_n = nth_power_assoc(mmul, M, n) return M_n[0][0]