Make fibo faster

Question

I need to write a code to give a number and print me the F[number].This code is pretty slow.Any ideas for a faster code?

 while True:
      n=input()
      if n=='END' or n=='end':
         break
      class Fibonacci:
            def fibo(self, n):
                if int(n) == 0:
                   return 0
                elif int(n) == 1:
                   return 1
                else:
                  return self.fibo(int(n)-1) + self.fibo(int(n)-2)
      f=Fibonacci()
      print(f.fibo(n))

Why `class`? that declaration is totally unnecessary.. – Rocky Li Nov 30 '18 at 20:44 — Rocky Li, Nov 30 '18 at 20:44

Christian Sloper · Accepted Answer · 2018-11-30T21:59:14.690

2

I have written a bit about faster fibonacci in this post, maybe one of them is useful for you? https://sloperium.github.io/calculating-the-last-digits-of-large-fibonacci-numbers.html

Anyway. Your code is very slow because you get exponential running time calling the same subtrees over and over.

You can try a linear solution:

def fib3(n):
    if n == 0:
        return 0
    f1 = 0
    f2 = 1

    for i in range(n-1):
        f1,f2 = f2, f1+f2
    return f2

edited Nov 30 '18 at 21:59

answered Nov 30 '18 at 20:48

Christian Sloper

7,440
3
15
28

`n -= 1` is completely pointless; the `range` loop is using the original `n`. I'm guessing you started with a `while` loop based solution, changed to `for`, then didn't delete the `n-=1`. – ShadowRanger Nov 30 '18 at 21:36
you are very correct :-) – Christian Sloper Nov 30 '18 at 21:58

score 2 · Answer 2 · answered Nov 30 '18 at 20:49

2

You can use functools memoize to make it store previous values so it doesn't have to recursively call the fibonacci function. The example they list is literally fibonacci

answered Nov 30 '18 at 20:49

IanQ

1,831
5
20
29

score 1 · Answer 3 · answered Nov 30 '18 at 20:48

You can use a dict to memoize the function:

class Fibonacci:
    memo = {}
    def fibo(self, n):
        if n in self.memo:
            return self.memo[n]
        if int(n) == 0:
            value = 0
        elif int(n) == 1:
            value = 1
        else:
            value = self.fibo(int(n) - 1) + self.fibo(int(n) - 2)
        self.memo[n] = value
        return value

score 1 · Answer 4 · answered Nov 30 '18 at 20:48

Use dynamic programming: this prevents it calculating all the way down to 0 and 1 each time:

memory = {0:0, 1:1}
def fibo(n):
    if n in memory:
        return memory[n]
    else:
        ans = fibo(int(n)-1) + fibo(int(n)-2)
        memory[n] = ans
        return ans

Test:

>>> fibo(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

This is almost instantaneous.

score 1 · Answer 5 · answered Nov 30 '18 at 20:49

Don't use a class; you're not gaining anything from it
Don't needlessly redefine your class each loop
Convert from str to int once, up front, rather than over and over
(If not required by assignment) Use iterative solution, not recursive

With just #1-3, you'd end up with:

def fibo(n):   # Using plain function, defined once outside loop
    if n < 2:
        return n
    return fib(n - 1) + fibo(n - 2)

while True:
    n = input()
    if n.lower() == 'end':
        break
    print(fibo(int(n)))  # Convert to int only once

If you're not required to use a recursive solution, don't; Fibonacci generation is actually a pretty terrible use for recursion, so redefine the function to:

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

which performs O(n) work rather than O(2**n) work. Memoizing could speed up the recursive solution (by decorating fibo with @functools.lru_cache(maxsize=None)), but it's hardly worth the trouble when the iterative solution is just so much faster and requires no cache in the first place.

Make fibo faster

5 Answers5