Paul Zimmermann's challenge on the double factorial

peter.luschny peter.luschny at
Tue Feb 2 11:51:07 CET 2010


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

More information about the gmp-discuss mailing list