Calculate nth term of Fibonacci sequence in Python

Question

The following code is to calculate nth term og fibonacci sequence in python using matrix exponentiation for various test cases t.But the program gives absurd output.Please tell me where i am wrong.when i ran the code in C++ it runs perfectly.

class matrix:
    def __init__(self):
        self.a=self.b=self.c=1
        self.d=0

    def mul(self,e,f):
        ret = matrix()
        ret.a=(e.a*f.a)+(e.b+f.c)
        ret.b=(e.a*f.b)+(e.b+f.d)
        ret.c=(e.c*f.a)+(e.d+f.c)
        ret.d=(e.c*f.b)+(e.d+f.d)
        return ret

    def exp(self,a,p):
        if(p==0):
            temp=matrix()
            temp.a=temp.b=temp.c=temp.d=1
            return temp
        if(p==1):
            return a
        if(p%2==0):
            return self.exp(self.mul(a,a),p/2)
        else:
            return self.mul(a,self.exp(self.mul(a,a),(p-1)/2))

    def fib(self,n):
        if (n==0):
            return 0
        if (n==1):
            return 1
        s=matrix()
        s=self.exp(s,n)
        return s.d

t=int(raw_input())
while(t>0):
    v=matrix()
    n=int(raw_input())
    print v.fib(n)
    t=t-1

related: [nth fibonacci number in sublinear time](http://stackoverflow.com/q/1525521/4279). Here's an [implementation of algorithm from SICP](https://github.com/zed/txfib/blob/master/fibonacci.py#L139) (ignore the decorator and `yield None`, replace the last `yield` by `return`) — jfs, May 27 '13 at 08:41

score 1 · Answer 1 · answered May 27 '13 at 07:36

1

The problem lies in your __init__ function. In python the so-called variables are just 'tags' to data in the memory. To compare with C/C++, these can be thought of as pointers. when you assign self.a = self.b = self.c, you are basically assigning three different names to the same data in the memory. Any change you make in a will be reflected back in b and c and so on.

For your problem where you need three separate variables, one way to change the __init__ function is like:

self.a, self.b, self.c = 1, 1, 1

or you can use copy. copy() tells python to assign a new memory location and then assign the tag on the right hand side to that location. For more read the official documentation on this http://docs.python.org/2/library/copy.html. You can also read a short walk-through on this in Python Tutorial: Shallow and Deep-copy

answered May 27 '13 at 07:36

goofd

2,028
2
21
33

once you have the idea that in python the variable are simply names, you can notice that the following statements: `self.b = 1` `self.a = self.b` will assign two different 'variables' as `self.b` has now been determined by python to be an `int` and while assigning `int` objects a new object is created. Again refer to the python doc ref to understand when a new variable is created and when another name to the same variable is created on assignment. – goofd May 27 '13 at 07:41
1

You are right in principle, but wrong in this particular case: `int` values are immutable in Python, so `a = b = 1` and `a, b = 1, 1` won't have any different behavior. A different thing would be with mutable objects: `a = b = []`... – rodrigo May 27 '13 at 07:49
Thank you sir.But after making the above changes the program is still giving the same output. – Kartik Khare May 27 '13 at 07:53
refer to my comment above for clarification. In the first case `self.a = self.b = self.c` the object type has not been determined and hence the name will refer to the same variable as that is the default behavior. in the second case where `self.b = 1` is followed by `self.a = self.b`, the type has been determined and hence `self.a` will be a new variable. you can verify this by using the command `id()` – goofd May 27 '13 at 07:55
@KartikKhare there are other instances of that behavior in your code. for example in your `exp()` function you again have an assignment `temp.a = temp.b = temp.c = 1`. As I mentioned in the above comment `print id()` to cross check what you are doing. It may also be worthwhile to run your code in [http://www.pythontutor.com/]. It lets you visualize your code – goofd May 27 '13 at 07:56
thank you sir.Actually after making the above changes there was a slight mistake in logic when i made it correct it ran perfectly.. – Kartik Khare May 27 '13 at 08:17

score 0 · Accepted Answer · answered May 27 '13 at 08:27

There are several issues, in order of importance:

1) Your multiplication is wrong. Note the multiplications at the right where you have sums):

def mul(self,e,f):
    ret = matrix()
    ret.a=(e.a*f.a)+(e.b*f.c)
    ret.b=(e.a*f.b)+(e.b*f.d)
    ret.c=(e.c*f.a)+(e.d*f.c)
    ret.d=(e.c*f.b)+(e.d*f.d)
    return ret

2) In the last line, you do return s.d but you should return s.b or s.c or you will get one less fibonacci.

3) The line temp.a=temp.b=temp.c=temp.d=1 is not necessary because the constructor does the work. Besides it is wrong, because d should be 0.

4) Why are mul and exp class functions if they don't use self. It does no harm but they should be @staticmethod

5) Again, it does no harm but your second recursive call is unnecessarily complex. Just write:

    return matrix.mul(a,matrix.exp(a, p-1))

Sir can you suggest where i should use modulo (%) so that it calculates fibonacci for large numbers (>10^7) in very less time — Kartik Khare, May 28 '13 at 06:42
@KartikKhare: Please, don't call me "sir"... About your question, your modulo operation is well placed, my suggestion was just to change the `else:` part, because it is simpler this way (although equivalent). Anyway if you want to be extra fast you can calculate it in constant time using the __Binet's formula__. — rodrigo, May 28 '13 at 16:27

score 0 · Answer 3 · answered Aug 01 '13 at 21:43

I'm not sure if it is required for you to use matrix exponentiation for this problem. Unfortunately, I do not know much about Python classes quite yet. However, the following code does what the question heading wants: to find the n-th Fibonacci number. Below I describe this as F_n. Note the initial conditions for low values of n.

def fibN( n ):
"""
fibonacci: int -> int
Returns F_n.
Note: F_1 = 0, F_2 = 1, F_3 = 1, F_4 = 2
"""
n = abs( int( n ))
if n == 0:
    fib = 0
elif n == 1:
    fib = 1
else:
    counter = 2  
    f0 = 0
    f1 = 1
    fib = f0 + f1
    while counter <= n:
        fib = f0 + f1
        f0 = f1
        f1 = fib
        counter += 1
return fib

Calculate nth term of Fibonacci sequence in Python

3 Answers3