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.

Solution 1

There is lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resources to find (quickly if possible) what you need.

Write Fib sequence formula to infinite

In math, it's given in a recursive form:

In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:

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

Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

Go on on the sites I linked to you and will see this (on wolfram):

This one is pretty easy to implement and very, very fast to compute, in Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

An other way to do it is following the definition (from wikipedia):

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.

If your language supports iterators you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P Good luck and have fun!

Solution 2

Efficient Pythonic generator of the Fibonacci sequence

I found this question while trying to get the shortest Pythonic generation of this sequence (later realizing I had seen a similar one in a Python Enhancement Proposal), and I haven't noticed anyone else coming up with my specific solution (although the top answer gets close, but still less elegant), so here it is, with comments describing the first iteration, because I think that may help readers understand:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

and usage:

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

prints:

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

(For attribution purposes, I recently noticed a similar implementation in the Python documentation on modules, even using the variables a and b, which I now recall having seen before writing this answer. But I think this answer demonstrates better usage of the language.)

Recursively defined implementation

The Online Encyclopedia of Integer Sequences defines the Fibonacci Sequence recursively as

F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1

Succinctly defining this recursively in Python can be done as follows:

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

But this exact representation of the mathematical definition is incredibly inefficient for numbers much greater than 30, because each number being calculated must also calculate for every number below it. You can demonstrate how slow it is by using the following:

for i in range(40):
    print(i, rec_fib(i))

Memoized recursion for efficiency

It can be memoized to improve speed (this example takes advantage of the fact that a default keyword argument is the same object every time the function is called, but normally you wouldn't use a mutable default argument for exactly this reason):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

You'll find the memoized version is much faster, and will quickly exceed your maximum recursion depth before you can even think to get up for coffee. You can see how much faster it is visually by doing this:

for i in range(40):
    print(i, mem_fib(i))

(It may seem like we can just do the below, but it actually doesn't let us take advantage of the cache, because it calls itself before setdefault is called.)

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Recursively defined generator:

As I have been learning Haskell, I came across this implementation in Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

The closest I think I can get to this in Python at the moment is:

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

This demonstrates it:

[f for _, f in zip(range(999), fib())]

It can only go up to the recursion limit, though. Usually, 1000, whereas the Haskell version can go up to the 100s of millions, although it uses all 8 GB of my laptop's memory to do so:

> length $ take 100000000 fib 
100000000

Consuming the iterator to get the nth fibonacci number

A commenter asks:

Question for the Fib() function which is based on iterator: what if you want to get the nth, for instance 10th fib number?

The itertools documentation has a recipe for this:

from itertools import islice

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

and now:

>>> nth(fib(), 10)
55

Solution 3

Why not simply do the following?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))

Solution 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.

Solution 5

Time complexity :

The caching feature reduces the normal way of calculating Fibonacci series from O(2^n) to O(n) by eliminating the repeats in the recursive tree of Fibonacci series :

Code :

import sys

table = [0]*1000

def FastFib(n):
    if n<=1:
        return n
    else:
        if(table[n-1]==0):
            table[n-1] = FastFib(n-1)
        if(table[n-2]==0):
            table[n-2] = FastFib(n-2)
        table[n] = table[n-1] + table[n-2]
        return table[n]

def main():
    print('Enter a number : ')
    num = int(sys.stdin.readline())
    print(FastFib(num))

if __name__=='__main__':
    main()

View more solutions

Comments

[SD.]

This is not a homework problem but wow thank you for the answer! I understand what I need to do but starting it and implementing is what I am stuck on now (especially with implementing user input values). Can you provide some insight into this? I keep getting a <function fib at 0x0141FAF0> error.

[James Thompson]

I understand that you're trying very hard to implement a program that may be beyond your current ability. Having me write more code will not help you. You should try to hack around with my code until it works, and read more Python tutorials. Whitespace may be a problem, but I don't know that error.

[SD.]

I understand. Is there any other idea that you think I may be missing? I understand if you cannot help however. I thank you for your time.

[Kiv]

Your <function fib at 0x0141FAF0> error may be the result of saying "fib" (which refers to the function itself) instead of "fib()" which will call the function. Best of luck.

[David Thornley]

Bear in mind that this naive recursive method of calculating Fibonacci numbers can get into stack overflow (not the site) real fast. For practical purposes, generate iteratively or use some sort of memoization or something.

[Andrea Ambu]

You need to use a while loop, not map. Try to figure it out on your own, then come back with the code if you can't do it. I'm not lazy (the code is shorter than this comment). I'm doing that for you, try it out with the "while" hint ;) If you have problem with that come back again ;)

[SD.]

I'm back, lol. I got rid of the map(range) function and am using only a range(startNumber, endNumber) function. Now the problem I have is where to use the while statement. I try at the beginning of the function but of course there is a billin an done lines of error. Where should I be putting it? Thx

[Andrea Ambu]

Try to do, by hand, an example of input-output of your program (with a short range). Try then to figure out where your program is wrong. Try to convert the "by-hand method" in code. This is for exercise, to learn. I could put down two lines of code but I don't think you'll learn anything from them.

[SD.]

I wrote out a psuedocode and wrote it out but I still cannot get it to work :(. I either get an error that says fib function at randomnumbershere or it doesn't compute it the way I want (will only compute by displaying nth Fibonacci numbers not between a range. Hmmm.

[Andrea Ambu]

... did you read my post? I mean, what's wrong with the SubFib function?

[SD.]

I'm not using your code, see my code posted above. I'm going to give this one more go tonight, I'll reply with anoter comment. Thank you for keeping up with this bro - I really appreciate it.

[Andrea Ambu]

You welcome :) I don't really understand now what you really want to be your output :O

[SD.]

I still can't get it bro. :(. Do you have an Instant Messenger? www2.bakersfieldcollege.edu/cs/pwhitney/privdocs/coms_b10/… Here is a link to the assignment. I think I need to approach it entirely differently.

[Andrea Ambu]

In my post there is all you need. Give me your skype if you want.

[SD.]

Hey bro - just wanted to let you know that I figured out a way to do it without yields, returns or even defining my own function. Let me know if you'd like to see the code.

[Hans]

Dynamic programming FTW! fibonacci(10000000000000000000000000000000000000000000000000‌​00000000000000000000‌​00000000) responds almost instantly

[GingerPlusPlus]

eval(input()) isn't needed here; I think int(input()) in the case is better.

[lord63. j]

We should use int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))), any ideas? @AndreaAmbu

[noobninja]

Once a recursive script (looping) exceeds maximum recursion depth, the script will crash with a RuntimeError due to Python's finite stack size. The dreaded stack overflow.

[xgqfrms]

a easy way to realize Fibonacci series just using iterator, without any complex Recursion data structure!

[Asclepius]

The first and third techniques are good. The second technique is off by 1; it effectively needs n -= 1 to work correctly, and it also doesn't work with n = 0. In any case, it would really help me if a lot of context was added to explain how these are working, especially the first technique. I see you have a post at paulhankin.github.io/Fibonacci

[binithb]

About the last '''don't do this''' option, I don't understand why it would call itself before setdefault. Isn't setdefault supposed to return the value if n is a valid key ? Doc says "If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to None." What am I missing ?

[Russia Must Remove Putin]

@binithb the expression inside the setdefault call is evaluated before setdefault is.

[cdlane]

@lord63.j, you should only use that formula if you're aware that it starts deviating from the actual value when n is above 70 and blows up with an OverflowError when n is slightly above 600. Other approaches can handle an n of 1000 or more without blowing up or losing precision.

[cdlane]

It should be noted (in the documention string?) that this solution starts to lose precision starting around fib(70) and above since Python's math.sqrt(5) is only approximate.

[noobninja]

Python: Internal Integer Object Array Python's internal integer object array runs out at 256.

[Aaron3468]

@cdlane The formula may be converted to use the decimal.Decimal type. After getcontext().prec = ___, Binet's formula works fine for ~400,000 digits. mpmath allows greater precision.

[SeF]

What about starting the list as [0, 1] (i.e. List.append(0); List.append(1)) to avoid the remove command after the else? ... and the fibonacci number should be better indexed as fibonacci(10) returns the fibonacci numbers below 10, not the 10-th one.

[Andronicus]

Still the same (I didn't downvote). You have just mixed some snippets from most voted answer.

[ρяσѕρєя K]

Add some explanation with answer for how this answer help OP in fixing current issue

[Nathan Pierson]

How does the memoized version pass the _cache variable to the recursive invocations? I don't understand why you don't need to call setdefault(n, mem_fib(n-1, _cache) + mem_fib(n-2, _cache).

[Russia Must Remove Putin]

@NathanPierson the keyword argument is the default argument, and it's that same instance of the dictionary that is used every call, therefore we don't need to pass it explicitly.

[Nathan Pierson]

Oh! So it's not working like "The default value of this parameter is the empty dict {} (and each invocation that doesn't specify an argument gets their own, separate {})", it's "There is a single dict which acts as the default value of this parameter, and it starts as {}". Makes sense, thank you

[Russia Must Remove Putin]

@NathanPierson right - it's a mutable default argument, and it's always the same dict on future calls as well. Here's an answer I wrote that fully examines the matter: stackoverflow.com/a/36968932/541136

[Milovan Tomašević]

autopep8 automatically formats Python code to conform to the PEP 8 style guide.