Paul Zimmermann's challenge on the double factorial
Paul.Zimmermann at loria.fr
Tue Feb 2 13:45:40 CET 2010
> Date: Tue, 2 Feb 2010 11:51:07 +0100
> From: "peter.luschny" <peter.luschny at googlemail.com>
> Paul Zimmermann challenged us to write a faster function for
> calculating the double factorial: "Challenge: do better than mpz_fac_ui2 ..."
> His implementation, which he says is based on an idea of Scho"nhage
> et alia (see the reference in his listing), can be found here:
> I wrote a version which is not based on Scho"nhage's algorithm but
> also uses prime factorisation. I named it 'SwingDouble'. It seems
> to be faster, but what might be more significant, it uses less memory.
> Here is the output from a test run.
> Testing number: 32000000
> ParallelDouble: 20.734 sec, memory: 2062258 long
> SwingDouble: 24.093 sec, memory: 2062258 long
> ZimmermannDouble: 31.907 sec, memory: 65973814 long
> Testing number: 32000001
> ParallelDouble: 33.265 sec, memory: 3947628 long
> SwingDouble: 36.640 sec, memory: 3947628 long
> ZimmermannDouble: 37.281 sec, memory: 65973816 long
> Testing number: 64000000
> ParallelDouble: 45.906 sec, memory: 3947628 long
> SwingDouble: 53.531 sec, memory: 3947628 long
> ZimmermannDouble: 70.000 sec, memory: 131785085 long
> Testing number: 64000001
> ParallelDouble: 72.406 sec, memory: 7570170 long
> SwingDouble: 80.109 sec, memory: 7570170 long
> ZimmermannDouble: 80.812 sec, memory: 131785087 long
> The functions to compare are 'ZimmermannDouble' and 'SwingDouble'.
> The experimental variant 'ParallelDouble' is not part of this
> 'competition'. Please let me know if you think that the comparison
> is correct and fair. You can find the sources here:
> Peter Luschny
impressive timings! However my original challenge said
"do better than mpz_fac_ui2 for n=1000000"... How does
your code behave for n=1000000?
More information about the gmp-discuss