fibonacci sequence going from point a to point b?

Question

m = 2
n =20
a,b = m,0
fib = [m]
while a <= n:
   fib.append(a)
   a,b = a+b, a

So given two variables from m to n (and m < n), I need to create a list containing all the numbers of the Fibonacci sequence between m and n inclusive (but cannot exceed) ex: if m = 2 and n = 20 then fib should be [2,3,5,8,13].

Answer 1

Using Generator :

import os,sys

def fib(num):
    a=0
    b=1
    while 1:
        a,b =b, b+a
        yield a

low=2
high=200
for i in fib(range(1)):
    if i <= high and i >= low :
        print i
    elif i > high:
        break

O/P 2 3 5 8 13 21 34 55 89 144

Answer 2

There are a few subproblems to consider for getting a log order solution, assuming (n-m) is relatively small. If (n-m) can be relatively large its best to precompute all reults and simply do a binary search.

1. Can we find i th fibonacci number in log time?
2. Can we find the number j such that fib(j) >= m ?

For first problem we can find i th fibonacci using (http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form).

And the second problem can be solved using a binary search and uses first method to find the fibonacci number >= m. Once we know j we can find j+1 th fibonacci number in log time, and simply generate all other numbers <=n using these.

Answer 3

You could do something like:

def fibs(low,high):
    a, b = 0, 1
    while 1:
        a, b = b, a+b
        if low <= a:
            if a <= high:
                yield a
            else:
                break

you can use it like

>>> for num in fibs(2,15):
...     print num
... 
2
3
5
8
13

But without resorting to the formula for the nth Fibonacci number and relying on proper rounding there isn't a way of getting the nth number without computing the first n-1 numbers.

So, if you don't want to use the formula it would probably be best to just keep a list of the Fibonacci numbers around and use that, if it turns out you need numbers between low and high where high > fib_nums[-1] then you can always use fib_nums[-1] and fib_nums[-2] as b and a to compute the values you're missing.

Answer 4

I googled and find the n-th term formula of fibonacci here

so the codes could be:

def fibn(n):
     Phi = (1+math.sqrt(5))/2
     phi = (1-math.sqrt(5))/2
     return round((math.pow(Phi, n) - math.pow(phi, n))/math.sqrt(5))

>>> fibn(0)
0.0
>>> fibn(1)
1.0
>>> fibn(2)
1.0
>>> fibn(3)
2.0
>>> fibn(4)
3.0
>>> fibn(5)
5.0
>>> fibn(6)
8.0
>>> fibn(7)
13.0
>>> fibn(8)
21.0
>>> fibn(9)
34.0
>>> fibn(10)
55.0

Answer 5

def fib(m,n):
    a,b = 1,1
    while a < m:
        a,b = b, a+b

    answer = [a]
    while b < n:
        a,b = b, a+b
        answer.append(a)
    return answer

In [2040]: fib(2,20)
Out[2040]: [2, 3, 5, 8, 13]

Answer 6

I thanks it's simple and clear to calculate the Fibonacci number recursively or by put all the number in a list. But if the number is too large, it not a good idea. Here is code ,BTW

def main():
    print fibo(100,600)
def fibo(m,n):
    f0=2
    f1=3
    while f1<m:
        tmp=f1
        f1=f0+f1
        f0=tmp
    res=[f0]
    while f1<n:
        res.append(f1)
        f1=res[-2]+res[-1]
    return res[1:];

if __name__ == '__main__':
    main()

Answer 7

m  = int(raw_input("Enter the start number : "))
n = int(raw_input("Enter the end number : "))
def fib(i):
if i == 0: return 0
elif i == 1: return 1
else: return f(i-1)+f(i-2)
print map(fib, range(m, n))

I hope this is what you need.

Answer 8

I do not know how to start the fibonnaci sequence midway, so the best I can think of is to filter the results afterwards.

def f(low, high):
    fib = [0]
    a, b = 1, 0
    while a <= n:
       fib.append(a)
       a,b = a+b, a
    return filter(lambda x: x >= low and x =< high, fib)

The fibonacci code is trivial, the new thing you might be seeing here is filter, which takes a function f and an iterable x, and returns a new iterable with all of the elements from x such that f(x) is true.