4 ms·
Oh yeah you're right Although, wouldn't variable overflow be the case for any algorithm, since already the 100th or so Fibonacci number takes more space than 2
by osoba 12y ago
Oh yeah you're right
Although, wouldn't variable overflow be the case for any algorithm, since already the 100th or so Fibonacci number takes more space than 2^64
And if you were to use the full float precision of sqr5 (and not just 4 digits like I did), you would run into 64bit float overflow way before that algorithm stops being accurate
- TheLoneWolfling 12y agoEverything else is talking about bigints. If you were dealing with fixed-length integers, just use a lookup table. Also, you're wrong regarding floating-point. On my machine, fib(101) is off from your approximation by ~2 million (!). Well before hitting the limits of a 64-bit float. It starts erroring at n=71, and only gets worse from there. Worse, the relative delta grows as n increases.
- osoba 12y agoHmm ok Thanks for actually testing it
- TheLoneWolfling 12y agoPython is wonderful for that sort of thing.