Finding Fibonacci

Finding Fibonacci

Problem: Finding Fibonacci

Finding Fibonacci is a classic problem with a lot of solutions. It's easy to figure out recursive method and iterative solution. Linear time recursive method is a little tricky since it use an array to store calculated value which shows some dynamic-programming idea.

The fastest way to do this, however, is to use matrix multiplication. As we can see we can generate an Fibonacci number from the previous two by matrix multiplication, which means if we need to find nth Fibonacci number, we will do matrix multiplication for n-1 times. Thus, we transformed continuous matrix multiplication into matrix power, which will only take O(logn) running time by doing matrix power boldly.

Code in Python:

def matrix_mul(A, B):
    return ([A[0][0] * B[0][0] + A[0][1] * B[1][0],
             A[0][0] * B[0][1] + A[0][1] * B[1][1]],
            [A[1][0] * B[0][0] + A[1][1] * B[1][0],
            A[1][0] * B[0][1] + A[1][1] * B[1][1]])

def matrix_pow(A, e):
    if not e:
        return [[1,0],[0,1]]
    elif e % 2:
        return matrix_mul(A, matrix_pow(A, e-1))
    else:
        sq= matrix_pow(A, e//2)
        return matrix_mul(sq, sq)

ntest = int(raw_input())
for i in xrange(ntest):
    params = raw_input().split(' ')
    f0, f1, n = int(params[0]), int(params[1]),     int(params[2])
if n == 0:
    print f0
else:       
    M = [[1, 1], [1, 0]]
    power = matrix_pow(M, n-1)
    print power[0][0] * f1 + power[0][1] * f0

However, my code didn't pass the test. If you have any idea on modify my code to pass the test, feel free to contact me in this book's discussion area.