testing value of last digit of an integer.

Kevin Ryde user42 at zip.com.au
Mon Apr 5 00:54:47 CEST 2004

Alexander Kruppa <alexander.kruppa at stud.tu-muenchen.de> writes:
> Speaking of computing residues for small moduli m, does GMP have code
> to quickly compute residues if 2^GMP_NUMB_BITS == +/-1 (mod m), by
> computing the (alternating) sum of limbs and doing the modulo on that?

For internal use only, we have mpn_mod_34lsub1 which computes a
remainder modulo 3/4 of a limb minus 1.  Ie. modulo 2^24-1 on 32 bits
or 2^48-1 on 64 bits.

These moduli have nice small prime factors, and are going to be used
for residue tests in mpn_perfect_square_p in the next release.
mpz_probab_prime_p is a candidate too, but not yet done.

> I'll need a fast (mod 3) for a Toom-Cook variant, is there a function
> to quickly compute the sum of limbs already in there somewhere?

3 is a divisor of the above.

More information about the gmp-discuss mailing list