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?

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?

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