Calculate the nth Fibonacci number, mod m

Question

I was trying to output F(n) mod m to find the remainder of Fibonacci number, where F(n) could be a very big number:

# Uses python3
n, m = [int(x) for x in input().split()]
def fib(n):
 a = [0, 1]
 if (n <=1):
 return n
 else:
 for i in range(1, n):
 a.append((a[-1] + a[-2])%m)
 return a[i+1]
print (fib(n))

As I typed in 239 1000, it returns 161 as the remainder, which is correct. But with bigger inputs eg. 2816213588 239, it seems to exceed time limits, what can I do to improve the code?

• Oscar Smith: Think about using this formulation for F(n) in log time codereview.stackexchange.com/questions/51864/…

Answer 1

Sorry, I am giving no code (I am on a phone and I don't know Python), but be aware that if m^2 is way lower than n, you could use the fact that your function gets periodical with a period maximally m^2 (as both a[-1] and a[-2] can gain m different values).

You could test in your for loop if/when you reached your period (if a[-2]==0 and a[-1]==1) and if so, variable i would indicate your period. Then you could simply grab a[n%(i-2)] as the answer, if I am not mistaken.

By the way, shouldn't the for loop range begin with 2?

• SylvainD: Interesting point! Out of curiosity, is it known that the repeated pattern does contain the initial values (0, 1) or can we reach another loop ? (like A -> B -> C -> D -> E -> C -> D -> E -> C -> D -> E -> C -> D -> E)
• Peter Taylor: The for loop range is irrelevant because the loop variable isn't used. range(1, n) contains as many elements as range(2, n+1). Note that the sequence returned by range does not include the second argument.
• Pavol Adam: @Josay I am pretty sure such C->D->E->C patterns cannot occur. I think, modulo addition (i.e. in a group) like this should divide the group (0 .. n-1) into congruent groups of the same size, each with a period equal to their size. But it is more an intuition now :). I do not remember most of my College Algebra now ... but I am sure Peter Taylor would know better (and I upvoted his answer, as he seems to remember more math than me :)).
• Peter Taylor: Pavol (cc @Josay), what I remembered was the phrase "Pisano period", which I used to look up information in Wikipedia and OEIS. L. Edson Jeffery states in OEIS that it does always repeat the initial values, and gives a reference. If I were to try to prove it independently I think I'd tackle it using Binet's formula in a suitable field extension of \$\mathbb{Z}/n\mathbb{Z}\$.

Answer 2

# Uses python3

I don't see much to argue against documenting this instead with a hashbang:

#!/usr/bin/python3

Sure, on Windows that path won't work, but on many other platforms it will.

---

n, m = [int(x) for x in input().split()]
...
print (fib(n))

It is generally considered best practice to use

if __name__ == "__main__":
 ...

as a guard around "immediate" code. This makes the file reusable as a library.

I don't understand the inconsistency in making m a global but n an argument to the function.

---

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

There are two PEP8 violations in this code: the missing space after <= on line 3, and the missing space around % on line 7. As a matter of style I would also drop the parentheses around the condition on line 3.

Other answers have addressed saving memory by keeping only the two most recent values, or saving time by exploiting the periodicity modulo m. Depending on your priorities for optimisation and expected values of n and m there are a couple of other things you could consider:

• Using the identities \$F(2n) = 2 F(n+1) F(n) - F(n)^2\$ and \$F(2n+1) = F(n+1)^2 + F(n)^2\$ you can calculate \$F(n)\$ in \$O(\lg n)\$ arithmetic operations. I describe this in much more detail, with SML code, on my personal website.
• If you prefer to attack the running time via periodicity (perhaps because \$\lg n > 6m\$), there are some tricks you can use to try to optimise it. The Pisano period is multiplicative, so if you can factor m that can reduce the number of steps you have to take to find the period. And there are number-theoretical theorems you can apply to reduce the search space.

Answer 3

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