Ramana Uday - 1 month ago 18

Python Question

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.