Improvement to mpz_nextprime

Karl Hasselström kha at
Mon Jun 26 13:51:53 CEST 2006

On 2006-06-22 12:31:11 -0300, Décio Luiz Gazzoni Filho wrote:

> On Jun 22, 2006, at 9:33 AM, Torbjorn Granlund wrote:
> > The code for initializing the residues will want to do a lot of
> > dividing, and here tabled preinverses will help a lot.
> By tabled preinverses you mean the constants used in Barrett
> division, right? My concern in this case (and it's probably valid
> for the method from your paper as well) is that these constants are
> computed to a large precision, as large as the argument to
> mpz_nextprime(). So if we're searching for 1k-bit primes, we'd need
> a table with 1k-bit entries per prime, so that's 78 Mbit or 10 MB to
> store a table of primes up to 1 million. I believe that raises
> memory usage and locality concerns, and it severely limits the
> amount of primes to use in the sieve. In that light, I think
> Bernstein's tree- product method looks better. Unless of course I'm
> mistaken and there's a more space-efficient way of storing
> pre-computed inverses.

I think Torbjörn is referring to using 1-limb inverses for 1-limb
divisors (there's a lot of code in GMP already doing this). When
dividing an n-limb number by a 1-limb number, you still need only a
1-limb inverse of the divisor (though you could use a longer inverse
if you wanted, but that's off-topic here), and since multiplication is
typically faster than division, the cost of inverting once and
multiplying n times is less than the cost of dividing n times -- for
large enough n, of course.

Computing 1-limb inverses may still cost hundreds of cycles, though,
so caching them in a table if they are going to be used over and over
could be a win.

Karl Hasselström, kha at

More information about the gmp-discuss mailing list