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.
> > + 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.