Is there python function for printing the fibonacci nth number effeciently?

Question

I've already tried non efficent programming techniques

test.assert_equals(fib(0),0)
test.assert_equals(fib(1),1)
test.assert_equals(fib(2),1)
test.assert_equals(fib(3),2)
test.assert_equals(fib(4),3)
test.assert_equals(fib(5),5)
test.assert_equals(fib(1000),43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875)

A simple iterative loop should calculate the 1000th element in less than a millisecond. — interjay, Mar 07 '23 at 14:33

Silloky · Answer 1 · 2023-03-07T16:09:50.857

0

This will probably help :

https://www.sanfoundry.com/python-program-print-nth-fibonacci-number-using-dynamic-programming-memoization/

This is a pretty good website.

EDIT :

instead of memoization, we can use another formula :

from math import sqrt
def nthFib(n):
    res = int((((1+sqrt(5))**n)-((1-sqrt(5)))**n)/(2**n*sqrt(5)))
    print(res)
nthFib(12)

edited Mar 07 '23 at 16:09

answered Mar 07 '23 at 14:24

Silloky

147
13

Memoization. One step at a time. Sthing faster? – BobSfougaroudis Mar 07 '23 at 14:34
2

You shouldn't calculate `sqrt(5)` 3 times hand hope that this is optimized for you. – MrSmith42 Mar 07 '23 at 16:15
Your formula does not support `n=1000`, results in an overflow error. Not to mention that it's wrong after `n=71` – Henry Woody Mar 07 '23 at 16:16
Should I just delete my answer from now on ? – Silloky Mar 07 '23 at 16:21

Is there python function for printing the fibonacci nth number effeciently?

1 Answers1