Return to Revisions

Code organisation

Le's write your function in such a way that it is easier to test. First step is to provide m as a parameter. Also, we can take this chance to write a proper docstring for the function. We get something like:

def fib(n, m):
    """Compute Fibonnaci(n) % m."""
    a = [0, 1]
    if (n <=1):
        ret = n
    else:
        for i in range(1, n):
            a.append((a[-1] + a[-2])%m)
        ret = a[i+1]
    # print(ret)
    return ret

(The single return and print statements are added to make the next step easier).

Now, we can add tests and add a computation of the time consumed. That benchmark will help ensuring our optimisations actually make things faster:

def test():
    start = time.time()
    assert fib(9, 32) == 2
    assert fib(9, 100) == 34
    assert fib(239, 1000) == 161
    assert fib(239, 100000000) == 88152161
    assert fib(239643, 100) == 62
    assert fib(2396434, 100) == 87
    end = time.time()
    print(end - start)

Removing the array based logic

We define an array of value but we never really care about more than 2 values (the values at the end). We could rewrite this using 2 variables (and use the tuple unpacking that Python provides):

def fib(n, m):
    """Compute Fibonnaci(n) % m."""
    a, b = 0, 1
    if n <= 1:
        ret = n
    else:
        for i in range(1, n):
            a, b = b, (a + b) % m
        ret = b
    print(ret)
    return ret

At this stage, the code is twice as fast.

Bug / weird edge case

The logic when n <= 1 does not take into account the m argument. This gives a wrong result for the following input:

assert fib(1, 1) == 0

This is a pretty degenerate case but it is easy to fix it.

We can do:

    ret = n % m

And add the following test cases:

assert fib(0, 1) == 0
assert fib(1, 1) == 0
assert fib(1, 10) == 1
assert fib(1, 10) == 1
assert fib(2, 10) == 1
assert fib(3, 10) == 2
assert fib(4, 10) == 3
assert fib(5, 10) == 5

At this stage, we have:

def fib(n, m):
    """Compute Fibonnaci(n) % m."""
    if n <= 1:
        return n % m
    else:
        a, b = 0, 1
        for i in range(1, n):
            a, b = b, (a + b) % m
        return b

def test():
    start = time.time()
    assert fib(0, 1) == 0
    assert fib(1, 1) == 0
    assert fib(1, 10) == 1
    assert fib(1, 10) == 1
    assert fib(2, 10) == 1
    assert fib(3, 10) == 2
    assert fib(4, 10) == 3
    assert fib(5, 10) == 5
    assert fib(9, 32) == 2
    assert fib(9, 100) == 34
    assert fib(239, 1000) == 161
    assert fib(239, 100000000) == 88152161
    assert fib(239643, 100) == 62
    assert fib(2396434, 100) == 87
    end = time.time()
    print(end - start)

Using maths

A different algorithm could be written using mathematical properties. I have yet to find something interesting to provide... I may update this answer in the future.