Andrew Friedley (CNS Student Support)
Sat, 12 Jul 2003 11:04:52 -0500

> Maybe there's some optimizations we can make for small factors too.

I don't see any, but my sight is limited.

> > +mpz_remove_ui (mpz_ptr dest, mpz_srcptr src, unsigned int f)
> You mean unsigned long there no doubt.

got it.

> > +  if (f <= 0)
> > +    DIVIDE_BY_ZERO;
> An unsigned isn't often < 0.  :-)

oops :) got this too.

> > +  if (f == 2)
> Maybe this special case could cover any power of two.  (The same for
> the full mpz_remove too.)  I expect we're usually called with an odd
> factor though, so it wouldn't be too important.

A quick glance at the docs didnt show me anything, but is there a quick
way to determine if a number is a power of two?  For the original
mpz_remove version, I could use a mpz_scan1 to find the first set bit,
then run another mpz_scan1 on the remaining part of the number to
determine if any other bits are set.  For the _ui case, though, I'm
betting this isnt the best idea.

> > +      mpz_tdiv_qr (x, rem, dest, fpow[p]);
> I wonder if we can avoid calculating the quotient in the first loop.
> Then say mpn_divisible_p could use the fast mpn_modexact_1_odd on
> small divisors.

This is the first time I've started looking at the gmp code, but it
looks like I could use mpz_divexact (mpn_ ?) right away for the first
iteration, then pair mpz_divexact with mpn_divisible_p on further
iterations.  How does this sound?

With your continued feedback I'll work up an improved patch.