On 22/02/2018 16:00, Steven D'Aprano wrote:
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

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.

As I said, people keep missing the point. The fact this uses a grossly inefficient way of calculating Fibonacci seems to blind them to any other considerations.

The actual result is irrelevant, so long as its correct. The important thing is those 50 million calls.

If you want to know how well one language implementations deals with function calls compared to another, you will prefer a test that is doing 48 million function calls and little else, rather than one that does only three dozen.

And one that is harder for a compiler to optimise, as you want to know how fast those 48 million calls can be made, not how well a compiler can avoid doing them!

(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

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*.

By running a different program? Fine, then here's my submission for the N=20 case used in the tests:

  def fib(n): return 6765

You have to compare like with like when testing languages, otherwise there's no point. If you want to use an iterative algorithm, then do the same with Julia. But then these functions are so fast, that it's not clear exactly what you are testing.

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)

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.

(OK, my interpreter took nearly 4 minutes, but I use my own big integer algorithms. All jolly interesting, but a diversion.)

The fact is that the vast majority of integer calculations don't need to use big integers (pretty much 100% of mine). Probably most don't even need 64 bits, but 32 bits.

So, if there is a performance advantage in having separate 64-bit and big integer types, then why not make use of it?

There's been a lot of talk of the advantages of static typing, and here is one use for it.


Reply via email to