Efficient calculation of Fibonacci series
Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once. Take a look at the following image.
It represents calculating Fibonacci(5)
with your function. As you can see, it computes the value of Fibonacci(2)
three times, and the value of Fibonacci(1)
five times. That just gets worse and worse the higher the number you want to compute.
What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."
There are a few options to make this faster:
1. Create a list "from the bottom up"
The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3]
, you can use the last two numbers in that list to create the next number.
This approach would look something like this:
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs
...
Then you can get the first 20 fibonacci numbers by doing
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Or you can get the 17th fibonacci number from a list of the first 40 by doing
>>> fib_to(40)[17]
1597
2. Memoization (relatively advanced technique)
Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:
>>> def fib(n, computed = {0: 0, 1: 1}):
... if n not in computed:
... computed[n] = fib(n-1, computed) + fib(n-2, computed)
... return computed[n]
This allows you to compute big fibonacci numbers in a breeze:
>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!
import functools
@functools.lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
This does pretty much the same thing as the previous function, but with all the computed
stuff handled by the lru_cache
decorator.
3. Just count up (a naïve iterative solution)
A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing
>>> def fib(n):
... a, b = 0, 1
... for _ in range(n):
... a, b = b, a+b
... return a
I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100)
is going to be a lot faster than [fib(n) for n in range(101)]
because with the latter, you still get the problem of computing each number in the list from scratch.
Efficient calculation of Fibonacci series
Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once. Take a look at the following image.
It represents calculating Fibonacci(5)
with your function. As you can see, it computes the value of Fibonacci(2)
three times, and the value of Fibonacci(1)
five times. That just gets worse and worse the higher the number you want to compute.
What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."
There are a few options to make this faster:
1. Create a list "from the bottom up"
The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3]
, you can use the last two numbers in that list to create the next number.
This approach would look something like this:
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs
...
Then you can get the first 20 fibonacci numbers by doing
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Or you can get the 17th fibonacci number from a list of the first 40 by doing
>>> fib_to(40)[17]
1597
2. Memoization (relatively advanced technique)
Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:
>>> def fib(n, computed = {0: 0, 1: 1}):
... if n not in computed:
... computed[n] = fib(n-1, computed) + fib(n-2, computed)
... return computed[n]
This allows you to compute big fibonacci numbers in a breeze:
>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!
import functools
@functools.lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
This does pretty much the same thing as the previous function, but with all the computed
stuff handled by the lru_cache
decorator.
3. Just count up (a naïve iterative solution)
A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing
>>> def fib(n):
... a, b = 0, 1
... for _ in range(n):
... a, b = b, a+b
... return a
I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100)
is going to be a lot faster than [fib(n) for n in range(101)]
because with the latter, you still get the problem of computing each number in the list from scratch.
Most efficient way to calculate Fibonacci sequence in Javascript
If you don't have an Array then you save on memory and .push
calls
function fib(n) {
var a = 0, b = 1, c;
if (n < 3) {
if (n < 0) return fib(-n);
if (n === 0) return 0;
return 1;
}
while (--n)
c = a + b, a = b, b = c;
return c;
}
Finding out nth fibonacci number for very large 'n'
You can use the matrix exponentiation method (linear recurrence method).
You can find detailed explanation and procedure in this or this blog. Run time is O(log n).
I don't think there is a better way of doing this.
Computational complexity of Fibonacci Sequence
You model the time function to calculate Fib(n)
as sum of time to calculate Fib(n-1)
plus the time to calculate Fib(n-2)
plus the time to add them together (O(1)
). This is assuming that repeated evaluations of the same Fib(n)
take the same time - i.e. no memoization is used.
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.
Alternatively, you can draw the recursion tree, which will have depth n
and intuitively figure out that this function is asymptotically O(2
n
)
. You can then prove your conjecture by induction.
Base: n = 1
is obvious
Assume T(n-1) = O(2
n-1
)
, therefore
T(n) = T(n-1) + T(n-2) + O(1)
which is equal to
T(n) = O(2
n-1
) + O(2
n-2
) + O(1) = O(2
n
)
However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n)
since both are defined as
f(n) = f(n-1) + f(n-2)
.
The leaves of the recursion tree will always return 1. The value of Fib(n)
is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, T(n)
is equal to Fib(n) x O(1)
. Consequently, the tight bound for this function is the Fibonacci sequence itself (~θ(1.6
n
)
). You can find out this tight bound by using generating functions as I'd mentioned above.
nth fibonacci number in sublinear time
The n
th Fibonacci number is given by
f(n) = Floor(phi^n / sqrt(5) + 1/2)
where
phi = (1 + sqrt(5)) / 2
Assuming that the primitive mathematical operations (+
, -
, *
and /
) are O(1)
you can use this result to compute the n
th Fibonacci number in O(log n)
time (O(log n)
because of the exponentiation in the formula).
In C#:
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
const double inverseSqrt5 = 0.44721359549995793928183473374626
const double phi = 1.6180339887498948482045868343656
*/
static int Fibonacci(int n) {
return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
Related Topics
What Is Ruby Equivalent of Python's 'S= "Hello, %S. Where Is %S" % ("John","Mary")'
Benchmarks: Does Python Have a Faster Way of Walking a Network Folder
Is There a Static Analysis Tool for Python, Ruby, SQL, Cobol, Perl, and Pl/Sql
Ruby Methods Equivalent of "If a in List" in Python
Bloomberg Server API and Ruby/Python
Pyobjc VS Rubycocoa for MAC Development: Which Is More Mature
Create Static Graphics Files (Png, Gif, Jpg) Using Ruby or Python
Python's Equivalent for Ruby's Define_Method
Python Equivalent of Ruby's .Select
How to Decrypt Aws Ruby Client-Side Encryption in Python
Is Module _File_ Attribute Absolute or Relative
Typeerror: Objectid('') Is Not JSON Serializable
Pandas Get Column Average/Mean
Driving Excel from Python in Windows
How to Parse a Time String Containing Milliseconds in It with Python
How to Change the Default MySQL Connection Timeout When Connecting Through Python