Huge Fibonacci Number

Question

I just started learning algorithms and I am stuck with the problem of finding a huge Fibonacci number. My example input is 5949. The output should be calculated in less than 5 seconds.

Here is my attempt:

def calc_fib(n):
    if n < 0:
       print ("Error. Bad input")
    elif n <= 2:
        return 1
    else:
        F = []
    for i in range (2,n):
        F[i] = F[i-1]+F[i-2]
    return F[n]

n = int(input())
print(calc_fib(n))

But I get an error on line with arrays: IndexError: list index out of range

You can also have a look at [this answer](http://stackoverflow.com/a/14661740/2011147) — Selcuk, Apr 07 '16 at 10:41
If you just want to calculate the nth Fibonacci number there's no need to build a list. But if you want to calculate lots of Fibonacci numbers then a list can be handy. — PM 2Ring, Apr 07 '16 at 10:50
Unlike javascript, python does not make assumptions about array index - either the list is big enough or you are trying to access something out of the range of possibilities. — smac89, May 07 '18 at 03:01

GIRISH RAMNANI · Answer 1 · 2016-04-08T04:26:35.723

2

you created a empty list and are indexing position in the list which do not exist. Also use append as you are adding new elements

def calc_fib(n):
    if n < 0:
       print ("Error. Bad input")
    elif n <= 2:
        return 1
    else:
        F = [0,1] # <- change
    for i in range (2,n):
        F.append(F[i-1]+F[i-2]) # <- change
    return F[n]

n = int(input())
print(calc_fib(n))

edited Apr 08 '16 at 04:26

answered Apr 07 '16 at 10:32

GIRISH RAMNANI

614
6
18

Doesn't work. You have an off-by-one error: `for i in range (2,n):` should be `for i in range (3,n):` – Chris Apr 08 '16 at 04:21

score 1 · Answer 2 · answered Apr 07 '16 at 10:32

1

You need to initialize the first two elements of your array: when i=2, the line F[i]=F[i-1]+F[i-2] is really F[2]=F[1]+F[0]. But F[1] and F[0] don't exist: the array is empty!

answered Apr 07 '16 at 10:32

Chris

1,613
17
24

score 1 · Answer 3 · answered Apr 07 '16 at 11:06

As others have mentioned your error is due to attempting to access elements in the list that don't exist. A fresh Python list created using [] has no elements, you have to add elements to it before you can safely index into it.

As I mentioned in my comment you don't need to create a list here, unless you want to keep a table of Fibonacci numbers that can be accessed randomly.

To calculate single Fibonacci numbers Ibrahim's matrix multiplication algorithm is very fast, but it's not really necessary for calculating F(5949). A simple for loop can do that in less than 0.06 seconds on my old 2GHz machine.

from __future__ import print_function

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

# Test
for i in range(6):
    print(i, fib(i))

output

If you are doing this on Python 2 replace range in fib by xrange to save memory.

score 0 · Answer 4 · answered Apr 07 '16 at 10:31

0

You're getting an IndexError because you create an empty array, and in the next step you try to access its last two elements. You must initialize it with (at least) two elements.

answered Apr 07 '16 at 10:31

alexis

48,685
16
101
161

Ibrahim · Answer 5 · 2016-04-07T14:17:59.620

0

There are already some answers here explaining what's wrong with your approach. However, if you're looking for an alternative idea, here's a really fast approach to find fibonacci numbers. It uses matrix multiplication and completes in O(log N) time. Using this approach, you can find Fibonacci of 5949 in milliseconds.

def matrix_mul(A, B):
    return ([A[0][0] * B[0][0] + A[0][1] * B[1][0],
         A[0][0] * B[0][1] + A[0][1] * B[1][1]],
        [A[1][0] * B[0][0] + A[1][1] * B[1][0],
        A[1][0] * B[0][1] + A[1][1] * B[1][1]])

def matrix_exp(A, e):
    if not e:
        return [[1,0],[0,1]]
    elif e % 2:
        return matrix_mul(A, matrix_exp(A, e-1))
    else:
        sq= matrix_exp(A, e//2)
        return matrix_mul(sq, sq)

def fibo(n):
    M = [[1,1],[1,0]]
    return matrix_exp(M, n)[0][0]

Read this for understanding why this works

edited Apr 07 '16 at 14:17

answered Apr 07 '16 at 10:42

Ibrahim

837
2
13
24

While this is an _excellent_ algorithm your answer doesn't actually address the error in the OP's code. And that's (probably) why you got some down-votes. So you need to fix your answer to avoid getting more down-votes. And maybe the original down-voters will return and reverse their votes (or others will give you up-votes in compensation, although strictly speaking that's not encouraged on SO). – PM 2Ring Apr 07 '16 at 11:10
"My example input is 5949. The output should be calculated in less than 5 seconds" This is the thing I addressed specifically. OP wanted a fast algorithm and others were already pointing out the issues with the his code, so there was no point in repeating that. I provided him an alternative solution which he may consider. – Ibrahim Apr 07 '16 at 13:04
I get that. However, in my experience, supplying great code that addresses the OP's real needs _isn't_ sufficient on SO, you also need to answer the question they asked or risk getting downvotes. Which is why the first paragraph in my answer exists. :) Sometimes, I'll just say "so-and-so explained why you are getting that error, but a better way to do what you want is this way...". – PM 2Ring Apr 07 '16 at 13:12
I really like your last idea :) admittedly you've spent more time on SO than me. – Ibrahim Apr 07 '16 at 14:17

Huge Fibonacci Number

5 Answers5