On Thu, 22 Feb 2018 12:03:09 +0000, bartc wrote:
> The idea of the Fibonacci benchmark is to test how effectively an
> implementation manages large numbers of recursive function calls. Then,
> fib(36) would normally involve 48,315,633 calls.
>
> This version does only 37, giving a misleading impression.
Who cares if it only does 37? There is *absolutely no benefit* to those
additional 48,315,596 calls, and thanks to the benchmark I discovered
that.[1]
I want to know what is the fastest implementation of Fibonacci I can
write. I'm not married to the idea that I have to make a ludicrous 48
million function calls just to get the 36th Fibonacci number.
> (It then goes on to suggest using 'numba', and using its JIT compiler,
> and using on that on an /iterative/ version of fib(). Way to miss the
> point.
Indeed, you certainly have.
> It might be a technique to bear in mind, but it is nonsensical to say
> this gives a 17,000 times speed-up over the original code.
That's *exactly what it did*.
How many years, decades, have you been programming? Have you not realised
yet that the best way to optimize code is to pick the fastest algorithm
you can that will do the job? There's no law that says because you
started with a slow, inefficient algorithm you have to stay with it.
> Here's another speed-up I found myself, although it was only 50 times
> faster, not 17,000: just write the code in C, and call it via
> os.system("fib.exe").
Did you include the time taken to capture the text output from stdout,
parse it, and convert to an int?
Did your C code support numbers greater than 2**64? My fibonacci function
can calculate the 10,000th Fibonacci number in a blink of the eye:
py> fibi(10000)
336447648764317832666216120051075...976171121233066073310059947366875
Output truncated for brevity, it is a 2090-digit number.
Admittedly it did take about a minute and a half to generate all 208988
digits of the one millionth Fibonacci number, but the performance is fast
enough for my needs.
[1] Actually I already knew it, but then I didn't perform these
benchmarks, I'm just linking to them.
--
Steve
--
https://mail.python.org/mailman/listinfo/python-list
