Paul Zimmermann's challenge on the double factorial

[Paul Zimmermann]

       Peter,

> Date: Tue, 2 Feb 2010 11:51:07 +0100
> From: "peter.luschny" <peter.luschny at googlemail.com>
> 
> Hi,
> 
> Paul Zimmermann challenged us to write a faster function for
> calculating the double factorial: "Challenge: do better than mpz_fac_ui2 ..."
> http://gmplib.org/list-archives/gmp-discuss/2009-January/003510.html
> 
> 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:
> http://www.loria.fr/~zimmerma/software/double_fac_ui.c
> 
> 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:
> http://www.luschny.de/math/factorial/testdoublefactorial.zip
> 
> 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?

Paul