 Ramana Uday -3 years ago 162
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? Prune

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download