Ramana Uday Ramana Uday - 1 month ago 18
Python Question

Product of 2 fibonacci numbers

My assignment:


Given a number, say prod (for product), we search two Fibonacci
numbers F(n) and F(n+1) verifying

F(n) * F(n+1) = prod if F(n) * F(n+1) = prod<br><br>


Your function productFib takes an integer (prod) and returns an array:

[F(n), F(n+1), True] else


F(m) being the smallest one such as F(m) * F(m+1) > prod

[F(m), F(m+1), False]


Examples:

productFib(714) # should return [21, 34, True],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34

productFib(800) # should return [34, 55, False],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55



My code:

def f(i):
if i == 0 :
return 0
if i == 1 :
return 1
return f(i-2) + f(i-1)

def productFib(prod):
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]


I am new to programming; this runs very slow for large numbers. How can I reduce the time complexity?

Answer Source

First and foremost, your f function is horridly time-consuming: it computes f(n) for low n many times. Memoize the function: keep results in a list, and just refer to that list when you compute again.

memo = [1, 1]

def f(i):
    global memo

    if i >= len(memo):
        # Compute all f(k) where k < i
        f_of_i = f(i-2) + f(i-1)
        memo.append(f_of_i)

    return memo[i]

Note that this sequence still guarantees that you will fill in memo in numerical order: f(i-2) is called before f(i-1), and both are called before adding f(i) to the list.

Calling f(100000000000000) (10^14) with this returns instantaneously. I haven't tried it with higher numbers.

UPDATE

I ran it with increasing powers of 10. At 10^1650, it was still printing output at full speed, and I interrupted the run.