2 ms·
Factoring into powers of 2 seems to me like an unnecessary complication. It's possible to calculate an arbitrary power in O(log N) time without memoization.
by isani 12y ago
Factoring into powers of 2 seems to me like an unnecessary complication. It's possible to calculate an arbitrary power in O(log N) time without memoization.
def __get_matrix_power(self, M, p):
if p == 1:
return M
if p % 2 == 1: # odd power
return self.__multiply_matrices(M, self.__get_matrix_power(M, p - 1))
else: # even power
K = self.__get_matrix_power(M, int(p/2))
return self.__multiply_matrices(K, K)
- nabb 12y agoAlso working on pairs of consecutive fibonacci numbers (f_n, f_(n+1)) instead of the matrix [[f_(n+1) f_n] [f_n f_(n-1)]] makes this much simpler. def fib(n): def fib2(n): # returns (f_n, f_(n+1)) if n == 0: return 0, 1 if n % 2: a, b = fib2(n-1) return b, a+b a, b = fib2(n//2) return b*a + a*(b-a), a*a + b*b return fib2(n)[0]