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]
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
if i == 0 :
if i == 1 :
return f(i-2) + f(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):
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.
I ran it with increasing powers of 10. At 10^1650, it was still printing output at full speed, and I interrupted the run.