0

This is the code for returning two consecutive numbers of Fibonacci series whose product is passed in fib() function. If the product exceeds the given number, the code ends by returning those two numbers and False in the list as shown.

This takes a huge time to run for larger numbers. Can someone help me with the optimization of this code?

def fib(n):
    if n<=1:
        return n
    else:
        return fib(n-1) + fib(n-2)


def productFib(prod):           
    i = 0
    while i >= 0:
        a = fib(i)*fib(i+1)
        if a == prod:
            return [fib(i), fib(i+1), True]
        elif a > prod:
            return [fib(i), fib(i+1), False]
        i+=1
    
        
print(productFib(41)) # [8, 13, False]
print(productFib(40)) # [5, 8, True]
print(productFib(4895)) # [55, 89, True]
print(productFib(5895)) # [89, 144, False]

Fibonacchi series:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... .

Stephen Rauch
  • 47,830
  • 31
  • 106
  • 135
DigiLearner
  • 77
  • 1
  • 9
  • Use iterative generation of fibonacci numbers: https://medium.com/@danfcorreia/fibonacci-iterative-28b042a3eec – rdas May 15 '21 at 11:00
  • You call `fib(i)` and `fib(i+1)` three times each instead of once and storing the result. You can improve the efficiency of the `fib` function but you also need to optimize how you call it. – Guimoute May 15 '21 at 11:02

2 Answers2

2

The only thing I can think of looking at your code, would be to avoid calling the function again while returning the result and store the Fibonacci variables beforehand.

def productFib(prod):           
    i = 0
    while i >= 0:
        fib_curr = fib(i)
        fib_next = fib(i+1)
        a = fib_curr * fib_next
        if a == prod:
            return [fib_curr, fib_next, True]
        elif a > prod:
            return [fib_curr, fib_next, False]
        i+=1

If you are planning to run the code multiple times for different values like you have given examples of the print staetements, you could optimise it by storing the Fibonacci values in a list upto a certain number, and then iterate through the list till a match is found, by this method at least your code won't have to calculate the same values repetitively.

Shivam Roy
  • 1,961
  • 3
  • 10
  • 23
2

Your fiboncci function is very slow, because you're doing the same calculation again and again. It's a very well known problem, to solve that either you can use an iterative approach or use memoization. Fortunately, you don't need to write a code for it. Python has built in support for caching functions via lru_cache.

from functools import lru_cache

@lru_cache(maxsize=1000)
def fib(n):
    if n<=1:
        return n
    else:
        return fib(n-1) + fib(n-2)
kinshukdua
  • 1,944
  • 1
  • 5
  • 15
  • This should be the accepted answer, as this is a _Python_-specific solution. Self-rolling memoization seems absurd for this task so I especially appreciate the simplicity and directness of this answer. – Jason R Stevens CFA May 16 '21 at 04:01