Factorial improvements

[Paul Zimmermann]

Someone who claims to be Torbjo"rn Granlund said on the list:

   If you got "orders of magnitude", i.e., >= 100 times improvement,
   I bow and promise never to write any more arithmetic routines in
   y life.  But I'd be brash enough to suggest that you remember
   incorrectly.

I got the following speedup with my code (I claim to be Paul Zimmermann):

mermoz% ./fac_ui 40000000
mpz_fac_ui took 727056ms    # reference gmp-4.1.4 code
mpz_fac_ui2 took 255384ms   # my new code

This is only a 2.85-fold speedup, but when 40000000 goes to infinity,
I believe the 2.85 ratio goes to infinity too. Unfortunately my computer
has not enough memory to try...

I've also tried the "current GMP code" [*] and I get:

mermoz% ./fac_ui_gmp 40000000
mpz_fac_ui took 727820ms    # reference gmp-4.1.4 code
mpz_fac_ui2 took 445347ms   # current GMP code

   I actually think the GMP 4.1.4 code is close to asymptically
   optimal, but others have shown that a 2-3 fold speedup is
   possible.

As far as I can see, both the gmp-4.1.4 code and the "current GMP code"
have complexity O(M(n) log(n)^2), whereas my implementation of Scho"nhage
and al.'s algorithm has complexity O(M(n) log(n)), so with a big enough
computer, it should be possible to get a speedup of >= 100.

Paul

[*] http://gmplib.org/list-archives/gmp-discuss/attachments/20050915/213ba335/fac_ui-0001.obj