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.
The answer is
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 > len(numbers):
next_fibonacci = numbers[-1]+numbers[-2]
numbers.append(next_fibonacci)
print numbers
get_fibonacci(20)
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()
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
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 >= 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)
Maybe this will help
def fibo(n):
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, b + a
return result
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 "{}: {}".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.
def fib(n):
"""
n >= 1, the number of elements in the Fibonacci sequence
"""
x, y = 0, 1
for i in range(n):
yield x
x, y = y, x + y
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)
Using for loop and print just the result
def fib(n:'upto n number')->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
>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>>
Print the list containing all the numbers
def fib(n:'upto n number')->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
>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
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
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
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]
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))
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)
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 < 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
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<=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
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
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())
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)
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 < 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]
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.
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
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()
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
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
>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]
Timing
>>> %%time
>>> 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.
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])
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 < firstnumber:
print "\nSecond number must be bigger than the first number!!!\n"
else:
while sum <= endingnumber:
print firstnumber
if secondnumber > 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.
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. :)
import time
start_time = time.time()
#recursive solution
def fib(x, y, upperLimit):
return [x] + fib(y, (x+y), upperLimit) if x < 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
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)
Just for fun, in Python 3.8+ you can use an assignment expression (aka the walrus operator) in a list comprehension, e.g.:
>>> a, b = 0, 1
>>> [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.
import time
start_time = time.time()
#recursive solution
def fib(x, y, upperLimit):
return [x] + fib(y, (x+y), upperLimit) if x < 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
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.
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 < Number):
if(i <= 1):
Next = i
else:
Next = First_Value + Second_Value
First_Value = Second_Value
Second_Value = Next
print(Next)
i = i + 1
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 ....
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 > len(numbers):
next_fibonacci = numbers[-1]+numbers[-2]
numbers.append(next_fibonacci)
print numbers
get_fibonacci(20)
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 < Number):
if(i <= 1):
Next = i
else:
Next = First_Value + Second_Value
First_Value = Second_Value
Second_Value = Next
print(Next)
i = i + 1
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 ....
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.
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 < 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
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
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()
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=" ")
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<=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
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=" ")
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
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 "{}: {}".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.
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
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 < 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
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
...
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 < firstnumber:
print "\nSecond number must be bigger than the first number!!!\n"
else:
while sum <= endingnumber:
print firstnumber
if secondnumber > 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.
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))<=1000:
i=i+1
a,b=b,a+b
print i,len(str(a)),a
# 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]<num:
x = l[-1]+l[-2]
if x>=num:
break
else:
l.append(x)
return l
Using for loop and print just the result
def fib(n:'upto n number')->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
>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>>
Print the list containing all the numbers
def fib(n:'upto n number')->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
>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
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
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 >= 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)
Optimized function of finding Fibonacci by keeping list in memory
def fib(n, a=[0, 1]):
while n > len(a):
a.append(a[-1] + a[-2])
return a[n-1]
print("Fibonacci of 50 - {}".format(fib(50))
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 < 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]
Maybe this will help
def fibo(n):
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, b + a
return result
Optimized function of finding Fibonacci by keeping list in memory
def fib(n, a=[0, 1]):
while n > len(a):
a.append(a[-1] + a[-2])
return a[n-1]
print("Fibonacci of 50 - {}".format(fib(50))
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 -> 10
output -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
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.
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
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))
OK.. after being tired of referring all lengthy answers, now find the below sort & 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 < 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
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 -> 10
output -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
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)
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))<=1000:
i=i+1
a,b=b,a+b
print i,len(str(a)),a
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.
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.
def fib(n):
"""
n >= 1, the number of elements in the Fibonacci sequence
"""
x, y = 0, 1
for i in range(n):
yield x
x, y = y, x + y
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
>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]
Timing
>>> %%time
>>> 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.
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.
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
...
Just for fun, in Python 3.8+ you can use an assignment expression (aka the walrus operator) in a list comprehension, e.g.:
>>> a, b = 0, 1
>>> [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.
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())
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
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)
This is quite efficient, using O(log n) basic arithmetic operations.
def fib(n):
return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << 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 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << 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 & 1: r = mul(r, x)
x = mul(x, x)
n >>= 1
return r[0]
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]
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
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)
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.
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 < 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
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()
This is quite efficient, using O(log n) basic arithmetic operations.
def fib(n):
return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << 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 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << 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 & 1: r = mul(r, x)
x = mul(x, x)
n >>= 1
return r[0]
# 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]<num:
x = l[-1]+l[-2]
if x>=num:
break
else:
l.append(x)
return l
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. :)
OK.. after being tired of referring all lengthy answers, now find the below sort & 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 < 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
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
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])
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)
Source: Stackoverflow.com