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  amp  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  lt  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

User · Answer

def fib lowerbound  upperbound       x   0     y   1     while x  lt   upperbound          if  x  gt   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

User · Answer

def fib n        quot  quot  quot      n  gt   1  the number of elements in the Fibonacci sequence      quot  quot  quot      x  y   0  1     for i in range n           yield x         x  y   y  x   y

User · Answer

On the much shorter format   def fibbo range   a  b       if range   0           a  b   b  a b         print a          return fibbo range -1  a  b      return  fibbo 11  1  0

User · Answer

Simple def -- try this    def fib n       first   0     second   1     holder   0     array          for i in range 0  n         first   second       second   holder       holder   first   second       array append holder      return array  input - gt  10 output - gt   1  1  2  3  5  8  13  21  34  55

User · Answer

If you re a fan of recursion you can cache the results easily with the lru cache decorator  Least-recently-used cache decorator   from functools import lru cache    lru cache   def fib n       if n    0          return 0     elif n    1          return 1     else          return fib n-1    fib n-2    If you need to cache more than 128 values you can pass maxsize as an argument to the lru cache  e g  lru cache maxsize 500   If you set maxsize None the cache can grow without bound

User · Answer

Recursion adds time  To eliminate loops  first import math  Then use math sqrt and golden ratio in a function      usr bin env python3  import math  def fib n       gr    1   math sqrt 5     2     fib first    gr  n -  1 - gr   n    math sqrt 5      return int round fib first    fib final   fib 100   print fib final    ref  Fibonacci Numbers in Python

User · Answer

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 2n  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  lt   endNumber          if startNumber  lt   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  gt  endNumber  return         if cur  gt   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

User · Answer

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

User · Answer

def fib x  y  n       if n  lt  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  gt  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

User · Answer

def fib        a b   1 1     num eval input  Please input what Fib number you want to be calculated          num int int num-2      for i in range  num int           a b b a b     print b

User · Answer

OK   after being tired of referring all lengthy answers  now find the below sort  amp  sweet  pretty straight forward way for implementing Fibonacci in python  You can enhance it it the way you want by getting an argument or getting user input   or change the limits from 10000  As you need        def fibonacci        start   0      i   1      lt          lt append start      while start  lt  10000          start    i         lt append start          i   sum lt -2            lt append i      print  The Fibonaccii series     lt   This approach also performs good  Find the run analytics below  In  10    timeit fibonacci 10000000 loops  best of 3  26 3 ns per loop

User · Answer

Another way of doing it   a n  0 1  10 map lambda i  reduce lambda x y  a append x y  a -2    range n-2     Assigning list to  a   assigning integer to  n  Map and reduce are 2 of three most powerful functions in python  Here map is used just to iterate  n-2  times  a -2   will get the last two elements of an array  a append x y  will add the last two elements and will append to the array

User · Answer

Fibonacci series in python by creating null list                      inp int input         size of the series example it is 7                    n 0                    n1 1                    x                     blank list                    x insert 0 0      initially insert 0th position 0 element                    for i in range 0 inp-1                       nth n n1                     n n1                   swapping the value                     n1 nth                     x append n            append all the values to null list                    for i in x          run this loop so ans is 0 1 1 2 3 5 8                     print i end

User · Answer

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

User · Answer

there is a very easy method to realize that    you can run this code online freely by using http   www learnpython org     Set the variable brian on line 3   def fib n      This is documentation string for function  It ll be available by fib   doc     Return a list containing the Fibonacci series up to n     result      a   0 b   1 while a  lt  n      result append a     0 1 1 2 3 5  8   13  break     tmp var   b         1 1 2 3 5 8  13     b   a   b           1 2 3 5 8 13 21     a   tmp var         1 1 2 3 5 8  13       print a  return result  print fib 10     result should be this   0  1  1  2  3  5  8

User · Answer

this is an improvement to mathew henry s answer   def fib n       a   0     b   1     for i in range 1 n 1               c   a   b             print b             a   b             b   c   the code should print b instead of printing c  output  1 1 2 3 5

User · Answer

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  - gt  Mat       guard n  gt  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  - gt  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  - gt  Int        guard n  gt  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

User · Answer

Using append function to generate first 100 elements    def generate        series    0  1      for i in range 0  100           series append series i    series i 1        return series   print generate

User · Answer

use recursion   def fib n       if n    0          return 0     elif n    1          return 1     else          return fib n-1    fib n-2  x input  which fibonnaci do you want    print fib x

User · Answer

based on classic fibonacci sequence and just for the sake of the one-liners  if you just need the number of the index  you can use the reduce  even if reduce it s not best suited for this it can be a good exercise   def fibonacci index       return reduce lambda r v  r append r -1  r -2   or  r pop 0  and 0  or r   xrange index    0  1   1    and to get the complete array just remove the or  r pop 0  and 0   reduce lambda r v  r append r -1  r -2   or r   xrange last index    0  1

User · Answer

num is the number up to which your list will go  first I created a list  and I wanted to code  everything  but obviously  I could have typed l    0 1   def fab num        l          for k in range 0 2           l append k       while l -1  lt num          x   l -1  l -2           if x gt  num              break         else              l append x       return l

User · Answer

import time start time   time time       recursive solution def fib x  y  upperLimit       return  x    fib y   x y   upperLimit  if x  lt  upperLimit else  x    To test    print fib 0 1 40000000000000   print  run time      str time time   - start time     Results   0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765  10946  17711  28657  46368  75025  121393  196418  317811  514229  832040  1346269  2178309  3524578  5702887  9227465  14930352  24157817  39088169  63245986  102334155  165580141  267914296  433494437  701408733  1134903170  1836311903  2971215073  4807526976  7778742049  12586269025  20365011074  32951280099  53316291173  86267571272  139583862445  225851433717  365435296162  591286729879  956722026041  1548008755920  2504730781961  4052739537881  6557470319842  10610209857723  17167680177565  27777890035288  44945570212853   run time  0 04298138618469238

User · Answer

Using for loop and print just the result  def fib n  upto n number  - gt int      if n  0          return 0     elif n  1          return 1     a 0     b 1     for i in range 0 n-1           b a b         a b-a     return b   Result   gt  gt  gt fib 50  12586269025  gt  gt  gt  gt   gt  gt  gt  fib 100  354224848179261915075  gt  gt  gt     Print the list containing all the numbers  def fib n  upto n number  - gt int      l  0 1      if n  0          return l 0      elif n  1          return l     a 0     b 1     for i in range 0 n-1           b a b         a b-a         l append b      return l   Result   gt  gt  gt  fib 10   0  1  1  2  3  5  8  13  21  34  55

User · Answer

Recursion adds time  To eliminate loops  first import math  Then use math sqrt and golden ratio in a function      usr bin env python3  import math  def fib n       gr    1   math sqrt 5     2     fib first    gr  n -  1 - gr   n    math sqrt 5      return int round fib first    fib final   fib 100   print fib final    ref  Fibonacci Numbers in Python

User · Answer

It can be done by the following way    n   0  numbers    0   for i in range 0 11       print n      numbers append n      prev   numbers -2      if n    0          n   1     else          n   n   prev

User · Answer

def fib        a b   1 1     num eval input  Please input what Fib number you want to be calculated          num int int num-2      for i in range  num int           a b b a b     print b

User · Answer

based on classic fibonacci sequence and just for the sake of the one-liners  if you just need the number of the index  you can use the reduce  even if reduce it s not best suited for this it can be a good exercise   def fibonacci index       return reduce lambda r v  r append r -1  r -2   or  r pop 0  and 0  or r   xrange index    0  1   1    and to get the complete array just remove the or  r pop 0  and 0   reduce lambda r v  r append r -1  r -2   or r   xrange last index    0  1

User · Answer

def fib n        quot  quot  quot      n  gt   1  the number of elements in the Fibonacci sequence      quot  quot  quot      x  y   0  1     for i in range n           yield x         x  y   y  x   y

User · Answer

Fibonacci series in python by creating null list                      inp int input         size of the series example it is 7                    n 0                    n1 1                    x                     blank list                    x insert 0 0      initially insert 0th position 0 element                    for i in range 0 inp-1                       nth n n1                     n n1                   swapping the value                     n1 nth                     x append n            append all the values to null list                    for i in x          run this loop so ans is 0 1 1 2 3 5 8                     print i end

User · Answer

def fib x  y  n       if n  lt  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  gt  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

User · Answer

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

User · Answer

Canonical Python code to print Fibonacci sequence   a b 1 1 while True    print a    a b b a b         Could also use b a b a b-a   For the problem  Print the first Fibonacci number greater than 1000 digits long    a b 1 1 i 1 while len str a   lt  1000    i i 1   a b b a b  print i len str a   a

User · Answer

The fibonacci sequence if you don t know what that is basically you print out a number and each each number that you print out is the previous two numbers added together  a  b   0 1  for i in range 0  10       print a      a  b   b  a   b  output  0 1 1 2 3 5 8 13 21 34  So 0 and 1 if you add those together it equals 1 if you add 1 and 1 it equals 2 if you add 1 and 2 it equals 3 and it keeps going and keeps going   Fibonacci sequence here that I ve written using generators  def fib num        a  b   0 1      for i in range 0  num           yield  quot        quot  format i 1  a          a  b   b  a   b          for item in fib 10       print item   output  1  0 2  1 3  1 4  2 5  3 6  5 7  8 8  13 9  21 10  34  Fibonacci sequence that we went over before except now we have a function here yields and yield is the keyword that lets you know that it s a generator   So  it yields your result and then we can loop through the generator and print out each item  If we run through then we can see that it still works just like it worked before but now we re using generators instead which have more advantages over returning a list but there are times and when you wouldn t want to use generators  You need do to your research and figure out when you really do get those advantages from generators and when they may not be the best option for you

User · Answer

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 lt  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

User · Answer

This is similar to what has been posted  but it s clean  fast  and easy to read    def fib n     start with first two fib numbers fib list    0  1  i   0   Create loop to iterate through n numbers  assuming first two given while i  lt  n - 2      i    1       append sum of last two numbers in list to list     fib list append fib list -2    fib list -1   return fib list

User · Answer

well  there are many ways  I have made use of lists to solve this probelm   below is the working code     feel free to comment if any feedback  def fib n       if n    0   to start fibonacci seraries value must be  gt   1         print  Enter postive integer       elif n   1          print 0      else          li    0  1          for i in range 2  n     start the loop from second index as  li  is assigned for 0th and 1st index             li append li -1    li -2               i    1         print  li         is used to print elements from list in single line with spaces  n   int input  Enter the number for which you want to generate fibonacci series n    fib n

User · Answer

Canonical Python code to print Fibonacci sequence   a b 1 1 while True    print a    a b b a b         Could also use b a b a b-a   For the problem  Print the first Fibonacci number greater than 1000 digits long    a b 1 1 i 1 while len str a   lt  1000    i i 1   a b b a b  print i len str a   a

User · Answer

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  - gt  Mat       guard n  gt  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  - gt  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  - gt  Int        guard n  gt  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

User · Answer

Using append function to generate first 100 elements    def generate        series    0  1      for i in range 0  100           series append series i    series i 1        return series   print generate

User · Answer

Another way of doing it   a n  0 1  10 map lambda i  reduce lambda x y  a append x y  a -2    range n-2     Assigning list to  a   assigning integer to  n  Map and reduce are 2 of three most powerful functions in python  Here map is used just to iterate  n-2  times  a -2   will get the last two elements of an array  a append x y  will add the last two elements and will append to the array

User · Answer

def fib lowerbound  upperbound       x   0     y   1     while x  lt   upperbound          if  x  gt   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

User · Answer

there is a very easy method to realize that    you can run this code online freely by using http   www learnpython org     Set the variable brian on line 3   def fib n      This is documentation string for function  It ll be available by fib   doc     Return a list containing the Fibonacci series up to n     result      a   0 b   1 while a  lt  n      result append a     0 1 1 2 3 5  8   13  break     tmp var   b         1 1 2 3 5 8  13     b   a   b           1 2 3 5 8 13 21     a   tmp var         1 1 2 3 5 8  13       print a  return result  print fib 10     result should be this   0  1  1  2  3  5  8

User · Answer

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  gt  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  gt  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  gt  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    gt  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    gt  gt  gt  nth fib    10  55

User · Answer

15 minutes into a tutorial I used when learning Python  it asked the reader to write a program that would calculate a Fibonacci sequence from 3 input numbers  first Fibonacci number  second number  and number at which to stop the sequence   The tutorial had only covered variables  if thens  and loops up to that point  No functions yet  I came up with the following code   sum   0 endingnumber   1                  print   n  Fibonacci sequence   n   firstnumber   input  Enter the first number     secondnumber   input  Enter the second number     endingnumber   input  Enter the number to stop at      if secondnumber  lt  firstnumber       print   nSecond number must be bigger than the first number    n   else   while sum  lt   endingnumber       print firstnumber      if secondnumber  gt  endingnumber           break      else           print secondnumber         sum   firstnumber   secondnumber         firstnumber   sum         secondnumber   secondnumber   sum   As you can see  it s really inefficient  but it DOES work

User · Answer

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

User · Answer

well  there are many ways  I have made use of lists to solve this probelm   below is the working code     feel free to comment if any feedback  def fib n       if n    0   to start fibonacci seraries value must be  gt   1         print  Enter postive integer       elif n   1          print 0      else          li    0  1          for i in range 2  n     start the loop from second index as  li  is assigned for 0th and 1st index             li append li -1    li -2               i    1         print  li         is used to print elements from list in single line with spaces  n   int input  Enter the number for which you want to generate fibonacci series n    fib n

User · Answer

Simple def -- try this    def fib n       first   0     second   1     holder   0     array          for i in range 0  n         first   second       second   holder       holder   first   second       array append holder      return array  input - gt  10 output - gt   1  1  2  3  5  8  13  21  34  55

User · Answer

Simple Fibo   def fibo start  count       a    start  start 1      for i in range count-len a            a append a -1  a -2       return a a   fibo 0  10  print  fibo   a   OUTPUT   0  1  1  2  3  5  8  13  21  34   Fibonacci written as a Generator     fill in this function def fib        a   1     b   1     yield a      yield b      for i in range 2  10           c   a b         a  b   b  c         yield c       pass  this is a null statement which does nothing when executed  useful as a placeholder     testing code import types if type fib       types GeneratorType      print  Good  The fib function is a generator         counter   0     for n in fib            print n          counter    1         if counter    10              break

User · Answer

use recursion   def fib n       if n    0          return 0     elif n    1          return 1     else          return fib n-1    fib n-2  x input  which fibonnaci do you want    print fib x

User · Answer

A more detailed explanation of how Memoization works for Fibonacci sequence     Fibonacci sequence Memoization  fib cache    0 0  1 1   def fibonacci n       if n  lt  0          return -1     if fib cache has key n           print  Fibonacci sequence for  d    d cached     n  fib cache n           return fib cache n      else          fib cache n    fibonacci n - 1    fibonacci n - 2      return fib cache n   if   name         main         print fibonacci 6      print fib cache       fibonacci 7  reuses fibonacci 6  and fibonacci 5      print fibonacci 7      print fib cache

User · Answer

The fibonacci sequence if you don t know what that is basically you print out a number and each each number that you print out is the previous two numbers added together  a  b   0 1  for i in range 0  10       print a      a  b   b  a   b  output  0 1 1 2 3 5 8 13 21 34  So 0 and 1 if you add those together it equals 1 if you add 1 and 1 it equals 2 if you add 1 and 2 it equals 3 and it keeps going and keeps going   Fibonacci sequence here that I ve written using generators  def fib num        a  b   0 1      for i in range 0  num           yield  quot        quot  format i 1  a          a  b   b  a   b          for item in fib 10       print item   output  1  0 2  1 3  1 4  2 5  3 6  5 7  8 8  13 9  21 10  34  Fibonacci sequence that we went over before except now we have a function here yields and yield is the keyword that lets you know that it s a generator   So  it yields your result and then we can loop through the generator and print out each item  If we run through then we can see that it still works just like it worked before but now we re using generators instead which have more advantages over returning a list but there are times and when you wouldn t want to use generators  You need do to your research and figure out when you really do get those advantages from generators and when they may not be the best option for you

User · Answer

How about this one  I guess it s not as fancy as the other suggestions because it demands the initial specification of the previous result to produce the expected output  but I feel is a very readable option  i e   all it does is to provide the result and the previous result to the recursion    count the number of recursions num rec   0  def fibonacci num  prev  num rec  cycles        num rec   num rec   1      if num    0 and prev    0          result    0          num   1      else          result   num   prev      print result       if num rec    cycles          print  done       else          fibonacci result  num  num rec  cycles    Run the fibonacci function 10 times fibonacci 0  0  num rec  10    Here s the output   0 1 1 2 3 5 8 13 21 34 done

User · Answer

I was trying to avoid a recursive function to solve this problem  so I took an iterative approach  I was originally doing a memoized recursive function but kept hitting max recursive depth  I also had strict memory goals so you will see me  keeping the array as small as I can during the looping process only keeping 2-3 values in the array at any time   def fib n       fibs    1  1    my starting array     for f in range 2  n           fibs append fibs -1    fibs -2     appending the new fib number         del fibs 0    removing the oldest number     return fibs -1    returning the newest fib  print fib 6000000     Getting the 6 millionth fibonacci number takes about 282 seconds on my machine while the 600k fibonacci takes only 2 8 seconds  I was unable to obtain such large fibonacci numbers with a recursive function  even a memoized one

User · Answer

These all look a bit more complicated than they need to be  My code is very simple and fast   def fibonacci x        List          f   1     List append f      List append f   because the fibonacci sequence has two 1 s at first     while f lt  x          f   List -1    List -2     says that f   the sum of the last two f s in the series         List append f      else          List remove List -1     because the code lists the fibonacci number one past x  Not necessary  but defines the code better         for i in range 0  len List            print List i    prints it in series form instead of list form  Also not necessary

User · Answer

Fibonacci sequence is  1  1  2  3  5  8        That is f 1    1  f 2    1  f 3    2       f n    f n-1    f n-2     My favorite implementation  simplest and yet achieves a light speed in compare to other implementations  is this   def fibonacci n       a  b   0  1     for   in range 1  n           a  b   b  a   b     return b   Test   gt  gt  gt   fibonacci i  for i in range 1  10    1  1  2  3  5  8  13  21  34    Timing   gt  gt  gt    time  gt  gt  gt  fibonacci 100  3  CPU times  user 9 65 s  sys  9 44 ms  total  9 66 s Wall time  9 66 s   Edit  an example visualization for this implementations

User · Answer

Fibonacci sequence is  1  1  2  3  5  8        That is f 1    1  f 2    1  f 3    2       f n    f n-1    f n-2     My favorite implementation  simplest and yet achieves a light speed in compare to other implementations  is this   def fibonacci n       a  b   0  1     for   in range 1  n           a  b   b  a   b     return b   Test   gt  gt  gt   fibonacci i  for i in range 1  10    1  1  2  3  5  8  13  21  34    Timing   gt  gt  gt    time  gt  gt  gt  fibonacci 100  3  CPU times  user 9 65 s  sys  9 44 ms  total  9 66 s Wall time  9 66 s   Edit  an example visualization for this implementations

User · Answer

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

User · Answer

Just for fun  in Python 3 8  you can use an assignment expression  aka the walrus operator  in a list comprehension  e g     gt  gt  gt  a  b   0  1  gt  gt  gt   a  b     b    a    a    b  for   in range 8      first 10 Fibonacci numbers  0  1  1  2  3  5  8  13  21  34    An assignment expression allows you to assign a value to a variable and return it in the same expression  Therefore  the expression  b    a    a    b    is equivalent to executing   a  b   b  a   b   and returning the value of b

User · Answer

If you re a fan of recursion you can cache the results easily with the lru cache decorator  Least-recently-used cache decorator   from functools import lru cache    lru cache   def fib n       if n    0          return 0     elif n    1          return 1     else          return fib n-1    fib n-2    If you need to cache more than 128 values you can pass maxsize as an argument to the lru cache  e g  lru cache maxsize 500   If you set maxsize None the cache can grow without bound

User · Answer

This is similar to what has been posted  but it s clean  fast  and easy to read    def fib n     start with first two fib numbers fib list    0  1  i   0   Create loop to iterate through n numbers  assuming first two given while i  lt  n - 2      i    1       append sum of last two numbers in list to list     fib list append fib list -2    fib list -1   return fib list

User · Answer

This is the simplest one in python for Fibonacci series but adjusted  0  in output array by append   to result in result list second variable that is result append second   def fibo num       first   0     second   1     result    0      print  Fibonacci series is       for i in range 0 num           third   first   second          print second          result append second          first   second         second   third     print result      return fibo 7    OUTPUT  Fibonacci series is  0  1  1  2  3  5  8  13

User · Answer

Can you guys please check this out i think it is awesome and easy to understand   i   0 First Value   0 Second Value   1  while i  lt  Number          if i  lt   1                     Next   i        else                    Next   First Value   Second Value                   First Value   Second Value                   Second Value   Next        print Next         i   i   1

User · Answer

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 2n  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  lt   endNumber          if startNumber  lt   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  gt  endNumber  return         if cur  gt   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

User · Answer

Optimized function of finding Fibonacci by keeping list in memory  def fib n  a  0  1         while n  gt  len a            a append a -1    a -2       return a n-1   print  Fibonacci of 50 -     format fib 50

User · Answer

This is the simplest one in python for Fibonacci series but adjusted  0  in output array by append   to result in result list second variable that is result append second   def fibo num       first   0     second   1     result    0      print  Fibonacci series is       for i in range 0 num           third   first   second          print second          result append second          first   second         second   third     print result      return fibo 7    OUTPUT  Fibonacci series is  0  1  1  2  3  5  8  13

User · Answer

num is the number up to which your list will go  first I created a list  and I wanted to code  everything  but obviously  I could have typed l    0 1   def fab num        l          for k in range 0 2           l append k       while l -1  lt num          x   l -1  l -2           if x gt  num              break         else              l append x       return l

User · Answer

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

User · Answer

Can you guys please check this out i think it is awesome and easy to understand   i   0 First Value   0 Second Value   1  while i  lt  Number          if i  lt   1                     Next   i        else                    Next   First Value   Second Value                   First Value   Second Value                   Second Value   Next        print Next         i   i   1

User · Answer

Maybe this will help  def fibo n       result          a  b   0  1     while b  lt  n              result append b              a  b   b  b   a     return result

User · Answer

A more detailed explanation of how Memoization works for Fibonacci sequence     Fibonacci sequence Memoization  fib cache    0 0  1 1   def fibonacci n       if n  lt  0          return -1     if fib cache has key n           print  Fibonacci sequence for  d    d cached     n  fib cache n           return fib cache n      else          fib cache n    fibonacci n - 1    fibonacci n - 2      return fib cache n   if   name         main         print fibonacci 6      print fib cache       fibonacci 7  reuses fibonacci 6  and fibonacci 5      print fibonacci 7      print fib cache

User · Answer

Just going through http   projecteuler net problem 2 this was my take on it    Even Fibonacci numbers   Problem 2  def get fibonacci size       numbers    1 2      while size  gt  len numbers           next fibonacci   numbers -1  numbers -2          numbers append next fibonacci       print numbers  get fibonacci 20

User · Answer

It can be done by the following way    n   0  numbers    0   for i in range 0 11       print n      numbers append n      prev   numbers -2      if n    0          n   1     else          n   n   prev

User · Answer

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 2n  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  lt   endNumber          if startNumber  lt   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  gt  endNumber  return         if cur  gt   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

User · Answer

15 minutes into a tutorial I used when learning Python  it asked the reader to write a program that would calculate a Fibonacci sequence from 3 input numbers  first Fibonacci number  second number  and number at which to stop the sequence   The tutorial had only covered variables  if thens  and loops up to that point  No functions yet  I came up with the following code   sum   0 endingnumber   1                  print   n  Fibonacci sequence   n   firstnumber   input  Enter the first number     secondnumber   input  Enter the second number     endingnumber   input  Enter the number to stop at      if secondnumber  lt  firstnumber       print   nSecond number must be bigger than the first number    n   else   while sum  lt   endingnumber       print firstnumber      if secondnumber  gt  endingnumber           break      else           print secondnumber         sum   firstnumber   secondnumber         firstnumber   sum         secondnumber   secondnumber   sum   As you can see  it s really inefficient  but it DOES work

User · Answer

On the much shorter format   def fibbo range   a  b       if range   0           a  b   b  a b         print a          return fibbo range -1  a  b      return  fibbo 11  1  0

User · Answer

How about this one  I guess it s not as fancy as the other suggestions because it demands the initial specification of the previous result to produce the expected output  but I feel is a very readable option  i e   all it does is to provide the result and the previous result to the recursion    count the number of recursions num rec   0  def fibonacci num  prev  num rec  cycles        num rec   num rec   1      if num    0 and prev    0          result    0          num   1      else          result   num   prev      print result       if num rec    cycles          print  done       else          fibonacci result  num  num rec  cycles    Run the fibonacci function 10 times fibonacci 0  0  num rec  10    Here s the output   0 1 1 2 3 5 8 13 21 34 done

User · Answer

Using for loop and print just the result  def fib n  upto n number  - gt int      if n  0          return 0     elif n  1          return 1     a 0     b 1     for i in range 0 n-1           b a b         a b-a     return b   Result   gt  gt  gt fib 50  12586269025  gt  gt  gt  gt   gt  gt  gt  fib 100  354224848179261915075  gt  gt  gt     Print the list containing all the numbers  def fib n  upto n number  - gt int      l  0 1      if n  0          return l 0      elif n  1          return l     a 0     b 1     for i in range 0 n-1           b a b         a b-a         l append b      return l   Result   gt  gt  gt  fib 10   0  1  1  2  3  5  8  13  21  34  55

User · Answer

Doing this solution by calling function and modularized  def userInput        number   int input  Please enter the number between 1 - 40 to find out the      fibonacci          return number  def findFibonacci number       if number    0          return 0     elif number    1          return 1     else          return findFibonacci number - 1    findFibonacci  number - 2    def main        userNumber   userInput       print findFibonacci userNumber    main

User · Answer

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

User · Answer

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  gt  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  gt  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  gt  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    gt  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    gt  gt  gt  nth fib    10  55

User · Answer

Just going through http   projecteuler net problem 2 this was my take on it    Even Fibonacci numbers   Problem 2  def get fibonacci size       numbers    1 2      while size  gt  len numbers           next fibonacci   numbers -1  numbers -2          numbers append next fibonacci       print numbers  get fibonacci 20

User · Answer

Optimized function of finding Fibonacci by keeping list in memory  def fib n  a  0  1         while n  gt  len a            a append a -1    a -2       return a n-1   print  Fibonacci of 50 -     format fib 50

User · Answer

Doing this solution by calling function and modularized  def userInput        number   int input  Please enter the number between 1 - 40 to find out the      fibonacci          return number  def findFibonacci number       if number    0          return 0     elif number    1          return 1     else          return findFibonacci number - 1    findFibonacci  number - 2    def main        userNumber   userInput       print findFibonacci userNumber    main

User · Answer

Simple Fibo   def fibo start  count       a    start  start 1      for i in range count-len a            a append a -1  a -2       return a a   fibo 0  10  print  fibo   a   OUTPUT   0  1  1  2  3  5  8  13  21  34   Fibonacci written as a Generator     fill in this function def fib        a   1     b   1     yield a      yield b      for i in range 2  10           c   a b         a  b   b  c         yield c       pass  this is a null statement which does nothing when executed  useful as a placeholder     testing code import types if type fib       types GeneratorType      print  Good  The fib function is a generator         counter   0     for n in fib            print n          counter    1         if counter    10              break

User · Answer

I was trying to avoid a recursive function to solve this problem  so I took an iterative approach  I was originally doing a memoized recursive function but kept hitting max recursive depth  I also had strict memory goals so you will see me  keeping the array as small as I can during the looping process only keeping 2-3 values in the array at any time   def fib n       fibs    1  1    my starting array     for f in range 2  n           fibs append fibs -1    fibs -2     appending the new fib number         del fibs 0    removing the oldest number     return fibs -1    returning the newest fib  print fib 6000000     Getting the 6 millionth fibonacci number takes about 282 seconds on my machine while the 600k fibonacci takes only 2 8 seconds  I was unable to obtain such large fibonacci numbers with a recursive function  even a memoized one

User · Answer

This is quite efficient  using O log n  basic arithmetic operations   def fib n       return pow 2  lt  lt  n  n   1   4  lt  lt  2 n  -  2  lt  lt  n  - 1     2  lt  lt  n    This one uses O 1  basic arithmetic operations  but the size of the intermediate results is large and so is not at all efficient   def fib n       return  4  lt  lt  n  3 n        4  lt  lt  2 n  -  2  lt  lt  n  - 1   amp    2  lt  lt  n  - 1    This one computes X n in the polynomial ring Z X     X 2 - X - 1  using exponentiation by squaring  The result of that calculation is the polynomial Fib n X   Fib n-1   from which the nth Fibonacci number can be read   Again  this uses O log n  arithmetic operations and is very efficient   def mul a  b           return a 0  b 1  a 1  b 0  a 0  b 0   a 0  b 0  a 1  b 1   def fib n           x  r    1  0    0  1          while n                  if n  amp  1  r   mul r  x                  x   mul x  x                  n  gt  gt   1         return r 0

User · Answer

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 2n  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  lt   endNumber          if startNumber  lt   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  gt  endNumber  return         if cur  gt   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

User · Answer

This is quite efficient  using O log n  basic arithmetic operations   def fib n       return pow 2  lt  lt  n  n   1   4  lt  lt  2 n  -  2  lt  lt  n  - 1     2  lt  lt  n    This one uses O 1  basic arithmetic operations  but the size of the intermediate results is large and so is not at all efficient   def fib n       return  4  lt  lt  n  3 n        4  lt  lt  2 n  -  2  lt  lt  n  - 1   amp    2  lt  lt  n  - 1    This one computes X n in the polynomial ring Z X     X 2 - X - 1  using exponentiation by squaring  The result of that calculation is the polynomial Fib n X   Fib n-1   from which the nth Fibonacci number can be read   Again  this uses O log n  arithmetic operations and is very efficient   def mul a  b           return a 0  b 1  a 1  b 0  a 0  b 0   a 0  b 0  a 1  b 1   def fib n           x  r    1  0    0  1          while n                  if n  amp  1  r   mul r  x                  x   mul x  x                  n  gt  gt   1         return r 0

User · Answer

Just for fun  in Python 3 8  you can use an assignment expression  aka the walrus operator  in a list comprehension  e g     gt  gt  gt  a  b   0  1  gt  gt  gt   a  b     b    a    a    b  for   in range 8      first 10 Fibonacci numbers  0  1  1  2  3  5  8  13  21  34    An assignment expression allows you to assign a value to a variable and return it in the same expression  Therefore  the expression  b    a    a    b    is equivalent to executing   a  b   b  a   b   and returning the value of b

User · Answer

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 lt  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

User · Answer

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

User · Answer

import time start time   time time       recursive solution def fib x  y  upperLimit       return  x    fib y   x y   upperLimit  if x  lt  upperLimit else  x    To test    print fib 0 1 40000000000000   print  run time      str time time   - start time     Results   0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765  10946  17711  28657  46368  75025  121393  196418  317811  514229  832040  1346269  2178309  3524578  5702887  9227465  14930352  24157817  39088169  63245986  102334155  165580141  267914296  433494437  701408733  1134903170  1836311903  2971215073  4807526976  7778742049  12586269025  20365011074  32951280099  53316291173  86267571272  139583862445  225851433717  365435296162  591286729879  956722026041  1548008755920  2504730781961  4052739537881  6557470319842  10610209857723  17167680177565  27777890035288  44945570212853   run time  0 04298138618469238

User · Answer

These all look a bit more complicated than they need to be  My code is very simple and fast   def fibonacci x        List          f   1     List append f      List append f   because the fibonacci sequence has two 1 s at first     while f lt  x          f   List -1    List -2     says that f   the sum of the last two f s in the series         List append f      else          List remove List -1     because the code lists the fibonacci number one past x  Not necessary  but defines the code better         for i in range 0  len List            print List i    prints it in series form instead of list form  Also not necessary

User · Answer

this is an improvement to mathew henry s answer   def fib n       a   0     b   1     for i in range 1 n 1               c   a   b             print b             a   b             b   c   the code should print b instead of printing c  output  1 1 2 3 5

User · Answer

Maybe this will help  def fibo n       result          a  b   0  1     while b  lt  n              result append b              a  b   b  b   a     return result

User · Answer

OK   after being tired of referring all lengthy answers  now find the below sort  amp  sweet  pretty straight forward way for implementing Fibonacci in python  You can enhance it it the way you want by getting an argument or getting user input   or change the limits from 10000  As you need        def fibonacci        start   0      i   1      lt          lt append start      while start  lt  10000          start    i         lt append start          i   sum lt -2            lt append i      print  The Fibonaccii series     lt   This approach also performs good  Find the run analytics below  In  10    timeit fibonacci 10000000 loops  best of 3  26 3 ns per loop

[python] How to write the Fibonacci Sequence?

Examples related to python

Examples related to fibonacci

Examples related to sequences