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...
Pavol Adams' answer seems to work just fine:
def fib(n, m):
"""Compute Fibonnaci(n) % m."""
if n <= 1:
return n % m
else:
beg = (0, 1)
a, b = beg
cache = [a, b]
for i in range(1, n):
a, b = b, (a + b) % m
if (a, b) == beg:
return cache[n % i]
cache.append(b)
return b