• API
• FAQ
• Tools
• Archive
daily pastebin goal
21%
SHARE
TWEET

# Neo-Fibonacci (matrix multiplication solution)

a guest Feb 11th, 2015 277 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #returns A * B, where A and B are two matrices
2. def matrix_multiply(A, B):
4.     for i in range(len(A)):
5.         row = []
6.         for j in range(len(B[0])):
7.             value = 0
8.             for k in range(len(B)):
9.                 value += A[i][k] * B[k][j]
10.             row.append(value)
13.
14. #returns the nth Neo-Fibonacci number
15. def neo_fib(n):
16.     if n <= 3:
17.         return 1
18.     n -= 3
19.     #note A * (x1, x2, x3) = (x1+x2+x3, x1, x2), which is what we need
20.     matrix = [
21.         [1, 1, 1],
22.         [1, 0, 0],
23.         [0, 1, 0]
24.     ]
25.     result = [
26.         [1, 0, 0],
27.         [0, 1, 0],
28.         [0, 0, 1]
29.     ]
30.     while n > 0:
31.         if n % 2 == 1:
32.             result = matrix_multiply(matrix, result)
33.         matrix = matrix_multiply(matrix, matrix)
34.         n /= 2
35.     answer = matrix_multiply(result, [[1], [1], [1]])[0][0]