Improvement to mpz_nextprime

[Karl Hasselström]

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 treskal.com
      www.treskal.com/kalle