After adding a modulo to function, all outputs are zero

Question

I wrote a program to calculate Fibonacci numbers, and it works fine. Then I altered the program to give me the Fibonacci numbers modulo 65536, and all my output became zeros. What went wrong?

import time
def fib_matrix_timed(min):
    timeout = time.time() + 60*min
    A = [0, 1]
    i = 1
    while time.time() < timeout:
        try:
            B = A
            A[0] = B[1]
            A[1] = ((B[0] + B[1])%65536)
            print A[0]
            i+=1
        except OverflowError:
            print "fib_iterative overflows at ", i
    print A[0]
    print "fib_matrix calculated ", i, "iterations in", min, "minute(s)"

fib_matrix_timed(1)

Answer 1

Your problem is:

B = A

Lists in python are mutable, which means when you do this, A is the same object as B, rather than a new list. So whenever you change either list A or list B, you are effectively changing both lists at the same time.

This line could instead be:

B = [A[0], A[1]]

Or: (suggestion by MarcosModenesi)

B = A[:] # works for list of any size containing immutable objects

Instead of making B just a reference to the same object as A, this would create an entirely new instance, with the values of the original.

The below example illustrates the problem when B is the same list as A.

Suppose A is [0,1]:

B = A

now B is A is [0,1]

A[0] = B[1]

B1 is 1, so now A[0] is B[0] is 1. A and B are now both [1,1].

A[1] = (B[0] + B[1]) % 65536

A and B are now [1,2]

The sequence thus generated is 1,2,4,8,16,32....

Since 65536 is 2^16, i.e. the 17th number in the sequence, of course the modulo would be 2^16 * 2^n % 2^16 = 0.

The problem arises from incorrect instantiation of list B, causing the sequence generated to be incorrect.