On Wed, Apr 9, 2008 at 6:03 AM, Yannick Gingras ygingras@ygingras.net wrote:
Greetings Lispers of Montréal, I just did some test with GCC's tail call elimination. The result is quite impressive: the tail recursive version of a Mandelbrot set generator runs faster than the iterative one.
http://ygingras.net/b/2008/4/tail-call-elimination-is-good-in-c-too
I still don't know how to explain this. At the very least, the recursive version should be slower by one extra function call. Anyone knows how it's possible to produce better machine code for the tail recursive version?
To answer your question: AFIAK it isn't possible.
Upon brief inspection I notice the invariants for the two algorithms are different:
In the recursive version the invariant is (iter != 0) && (Tr + Ti <= 4.0) In the iterative version the invariant is: (i<iter) && (Tr+Ti <= limit*limit)
So here is the evidence you aren't comparing the same algorithms.
Christopher Diggins http://www.cdiggins.com