How to write the Fibonacci Sequence?

Question

I had originally coded the program wrongly. Instead of returning the Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 should = only those numbers between 1 & 20), I have written for the program to display all Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 displays = First 20 Fibonacci numbers). I thought I had a sure-fire code. I also do not see why this is happening.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

print map(fib, range(startNumber, endNumber))

Someone pointed out in my Part II (which was closed for being a duplicate - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) that I need to pass the startNumber and endNumber through a generator using a while loop. Can someone please point me in the direction on how to do this? Any help is welcome.

---

I'm a learning programmer and I've run into a bit of a jumble. I am asked to write a program that will compute and display Fibonacci's Sequence by a user inputted start number and end number (ie. startNumber = 20 endNumber = 100 and it will display only the numbers between that range). The trick is to use it inclusively (which I do not know how to do in Python? - I'm assuming this means to use an inclusive range?).

What I have so far is no actual coding but rather:

• Write Fib sequence formula to infinite
• Display startNumber to endNumber only from Fib sequence.

I have no idea where to start and I am asking for ideas or insight into how to write this. I also have tried to write the Fib sequence forumla but I get lost on that as well.

Answer 1

We know that

And that The n-th power of that matrix gives us:

So we can implement a function that simply computes the power of that matrix to the n-th -1 power.

as all we know the power a^n is equal to

So at the end the fibonacci function would be O( n )... nothing really different than an easier implementation if it wasn't for the fact that we also know that x^n * x^n = x^2n and the evaluation of x^n can therefore be done with complexity O( log n )

Here is my fibonacci implementation using swift programming language:

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

This has complexity O( log n ). We compute the oìpower of Q with exponent n-1 and then we take the element m00 which is Fn+1 that at the power exponent n-1 is exactly the n-th Fibonacci number we wanted.

Once you have the fast fibonacci function you can iterate from start number and end number to get the part of the Fibonacci sequence you are interested in.

let sequence = (start...end).map(fibonacciFast)

of course first perform some check on start and end to make sure they can form a valid range.

I know the question is 8 years old, but I had fun answering anyway. :)

Answer 2

Basically translated from Ruby:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print c
            a = b
            b = c

...

Answer 3

def fib(x, y, n):
    if n < 1: 
        return x, y, n
    else: 
        return fib(y, x + y, n - 1)

print fib(0, 1, 4)
(3, 5, 0)

#
def fib(x, y, n):
    if n > 1:
        for item in fib(y, x + y, n - 1):
            yield item
    yield x, y, n

f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55

Answer 4

The idea behind the Fibonacci sequence is shown in the following Python code:

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)         

This means that fib is a function that can do one of three things. It defines fib(1) == 1, fib(0) == 0, and fib(n) to be:

fib(n-1) + fib(n-2)

Where n is an arbitrary integer. This means that fib(2) for example, expands out to the following arithmetic:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

We can calculate fib(3) the same way with the arithmetic shown below:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

The important thing to realize here is that fib(3) can't be calculated without calculating fib(2), which is calculated by knowing the definitions of fib(1) and fib(0). Having a function call itself like the fibonacci function does is called recursion, and it's an important topic in programming.

This sounds like a homework assignment so I'm not going to do the start/end part for you. Python is a wonderfully expressive language for this though, so this should make sense if you understand math, and will hopefully teach you about recursion. Good luck!

Edit: One potential criticism of my code is that it doesn't use the super-handy Python function yield, which makes the fib(n) function a lot shorter. My example is a little bit more generic though, since not a lot of languages outside Python actually have yield.

Answer 5

Go find out how to convert a recursive problem into an iterative one. Should be able to calculate from there.

That's might be the principles that they're trying to get you to learn, especially if this is an Algorithms course.

Answer 6

def fib(lowerbound, upperbound):
    x = 0
    y = 1
    while x <= upperbound:
        if (x >= lowerbound):
            yield x
        x, y = y, x + y

startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
    print "And the next number is... %d!" % fib_sequence