CODEWITHSUNDEEP
pythonalgorithmfibonacci
Ris
Ris

Reputation: 1912

An iterative algorithm for Fibonacci numbers

I am interested in an iterative algorithm for Fibonacci numbers, so I found the formula on wiki...it looks straight forward so I tried it in Python...it doesn't have a problem compiling and formula looks right...not sure why its giving the wrong output...did I not implement it right ? 

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

output

0
None
1
1
1
1
1
1

Upvotes: 21

Views: 121200

Answers (13)

KebertX
KebertX

Reputation: 304

You are returning a value within a loop, so the function is exiting before the value of y ever gets to be any more than 1.

If I may suggest something shorter, and much more pythonful:

def fibs(n):
    fibs = [0, 1, 1]
    for f in range(2, n):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs[n]

This will do exactly the same thing as your algorithm, but instead of creating three temporary variables, it just adds them into a list, and returns the nth fibonacci number by index.

Upvotes: 5

Loki
Loki

Reputation: 33

Possible solution:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=0
while len(d)<n:
    temp=a+b
    d.append(temp)
    a=temp
    b=d[i+1]
    i+=1
print("Fibonacci series of {} is {}".format(n,d))

Upvotes: -1

Loki
Loki

Reputation: 33

Another possible approach:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=2
while i<n:
    e=d[-1]+d[-2]
    d.append(e)
    i+=1
print("Fibonacci series of {} is {}".format(n,d))

Upvotes: 0

karuna
karuna

Reputation: 59

Non recursive Fibonacci sequence in python

def fibs(n):
    f = []
    a = 0
    b = 1
    if n == 0 or n == 1:
        print n
    else:
        f.append(a)
        f.append(b)
        while len(f) != n:
            temp = a + b
            f.append(temp)
            a = b
            b = temp

    print f

fibs(10)

Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Upvotes: 0

Jedi_Jezzi
Jedi_Jezzi

Reputation: 1

fcount = 0 #a count recording the number of Fibonacci numbers generated
prev = 0
current = 0
next = 1
ll = 0 #lower limit
ul = 999 #upper limit

while ul < 100000:
    print("The following Fibonacci numbers make up the chunk between %d and %d." % (ll, ul))
    while next <= ul:
        print(next)
        prev = current
        current = next
        next = prev + current
        fcount += 1 #increments count

    print("Number of Fibonacci numbers between %d and %d is %d. \n" % (ll, ul, fcount))        
    ll = ul + 1 #current upper limit, plus 1, becomes new lower limit
    ul += 1000 #add 1000 for the new upper limit
    fcount = 0 #set count to zero for a new batch of 1000 numbers

Upvotes: 0

digitect38
digitect38

Reputation: 1

How about this simple but fastest way... (I just discovered!)

def fib(n):
    x = [0,1]
    for i in range(n >> 1):
        x[0] += x[1]
        x[1] += x[0]
    return x[n % 2]

Note! as a result, this simple algorithm only uses 1 assignment and 1 addition, since loop length is shorten as 1/2 and each loop includes 2 assignment and 2 additions.

Upvotes: 0

tony
tony

Reputation: 1

import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

Disclaimer: I am currently on a mobile device and this may not be totally correct

This algorithm utilizes a gap in some other peoples' and now it is literally twice as fast. Instead of just setting b equal to a or vice versa and then setting a to a+b, I do it twice with only 2 more characters. I also added speed testing, based off of how my other iterative algorithm went. This should be able to go to about the 200,000th Fibonacci number in a second. It also returns the length of the number instead of the whole number, which would take forever.

My other one could go to the second Fibonacci number, as indicated by the built in clock: in 10^-6 seconds. This one can do it in about 5^-6. I'm going to get some more advanced algorithms soon and refine them for utmost speed.

Upvotes: -3

MsO
MsO

Reputation: 87

This work (intuitively)

def fib(n):
    if n < 2:
        return n
    o,i = 0,1
    while n > 1:
        g = i
        i = o + i
        o = g
        n -= 1
    return i

Upvotes: 0

user3464678
user3464678

Reputation: 23

I came across this on another thread and it is significantly faster than anything else I have tried and wont time out on large numbers. Here is a link to the math.

def fib(n):
    v1, v2, v3 = 1, 1, 0  
    for rec in bin(n)[3:]: 
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

Upvotes: 0

Andrei Volokitin
Andrei Volokitin

Reputation: 21

def fibiter(n):
    f1=1
    f2=1
    tmp=int()
    for i in range(1,int(n)-1):
        tmp = f1+f2
        f1=f2
        f2=tmp
    return f2

or with parallel assignment:

def fibiter(n):
    f1=1
    f2=1
    for i in range(1,int(n)-1):
        f1,f2=f2,f1+f2
    return f2

print fibiter(4)

Upvotes: 0

yadriel
yadriel

Reputation: 49

Assuming these values for the fibonacci sequence:

F(0) = 0;

F(1) = 1;

F(2) = 1;

F(3) = 2

For values of N > 2 we'll calculate the fibonacci value with this formula:

F(N) = F(N-1) + F(N-2)

One iterative approach we can take on this is calculating fibonacci from N = 0 to N = Target_N, as we do so we can keep track of the previous results of fibonacci for N-1 and N-2

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}

Upvotes: -1

poke
poke

Reputation: 387607

The problem is that your return y is within the loop of your function. So after the first iteration, it will already stop and return the first value: 1. Except when n is 0, in which case the function is made to return 0 itself, and in case n is 1, when the for loop will not iterate even once, and no return is being execute (hence the None return value).

To fix this, just move the return y outside of the loop.

Alternative implementation

Following KebertX’s example, here is a solution I would personally make in Python. Of course, if you were to process many Fibonacci values, you might even want to combine those two solutions and create a cache for the numbers.

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

Upvotes: 74

John Hornsby
John Hornsby

Reputation: 321

On fib(0), you're returning 0 because:

if (n == 0) {
    return 0;
}

On fib(1), you're returning 1 because:

y = 1
return y

On fig(2), you're returning 1 because:

y = 1
return y

...and so on. As long as return y is inside your loop, the function is ending on the first iteration of your for loop every time.

Here's a good solution that another user came up with: How to write the Fibonacci Sequence in Python

Upvotes: 1

Related Questions