mpz_fac_ui (revised)

[Torbjorn Granlund]

Paul.Zimmermann at loria.fr (Paul Zimmermann) writes:

  here is a revised version of the improved mpz_fac_ui code I sent yesterday.
  It should run in O(M(n) log n), whereas the current code is O(M(n) log^2 n).
  
This is very cool, we like simple code with great performance.

My preliminary correctness testing of the code suggests that it
might not have been through any testing ordeal on your side yet.
:o)

The code has an apparent disliking for arguments just beyond an
integral power of 2, such as 18, 19, 34, 258, 16391...  Also, it
seems to get 0! and 1! a tad bit off.

The sieving tables might be possible to shrink to half their
current size if only odd numbers were represented.  Or would that
cost too much overhead?

Other issues:

1. Could (n over k) be computed similarly?  Want to work on that?
2. Some more comments wouldn't hurt.
3. How about speed for small operands, does it beat the current,
   complex code already from 3!  If not, we might want to have a
   base case under a threshold.

--
Torbjörn