Re: *** prime: not enough precomputed primes

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

* Igor Schein [2005-03-16 20:27]:
> On Wed, Mar 16, 2005 at 09:24:25AM +0100, Karim Belabas wrote:
>> * Mc Laughlin, James [2005-03-16 07:48]:
>>> (01:38) gp > prime(10^7)
>>>
>>>   *** prime: not enough precomputed primes
>>>
>>> How do get a larger list of precomputed primes so that, for example,
>>> prime(10^12)
>>> will return the 10^12th prime?
>>
>> The answer to the first part of the question is
>>
>>   default(primelimit, 100M) [ or 100000000, or 10^8 ]
>>
>> [ you may also edit the gprc file to make it the default; or, starting gp from
>> a shell, you can type gp -p 100M ]
>>
>> The answer to the second part is: you can't. Functions dealing with prime
>> numbers (prime, primes, primepi, forprime...) are implemented with a (very)
>> naïve algorithm, requiring all needed primes to be precomputed. No
>> on-the-fly sieving.
>>
>> So, to get the 10^12-th prime, you need to store all primes up to
>> ~ 10^12 log(10^12) ~ 2.8 E13. And it's doubtful your hardware will be up
>> to the task [ gp won't even let you try on a 32-bit architecture. Then
>> you'll need a few TBytes of main memory. ].
>
> Several idle remarks.
>
> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
> ? ??primelimit
> primelimit (default 500k):
>
>   gp  precomputes  a list of all primes less than primelimit at initialization
> time.   These  are used by many arithmetical functions.   If you don't plan to
> invoke any of them, you can just set this to 1.  The maximal value is 2^32 - 1
> (resp 2^64 - 1) on a 32-bit (resp. 64-bit) machine.
> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
>
> However, in actuality the maximal value for 32bit is 2^32-2^11-1:

Indeed. I have fixed the doc in CVS [ made the statement less precise... ]

> Next, ?primel<TAB> doesn't do the completion (bug?)

primelimit is a PARI concept, not a function, hence there's no (basic)
online help for it and ?primelimit would give nothing.

On the other hand, ??primelimit is definitely valid. I have fixed the
contextual completion system to include 'defaults' in the list of
completions in this case.

> Finally, primelimit of 2^32-2^11-1 translates into less than 256MB of
> RAM allocated.  So on a Linux machine with sufficient physical RAM and
> hugemem kernel patch, you could potentially store all primes up to
> almost 100GB <=> 4GB of RAM ( I am not sure about going beyong 4GB ).
> But IIRC, the limitation is also in the algorithm, which stores gaps
> up to certain size, so if you reach a gap over that size limit, you
> have to use a large storage type, blowing up your memory
> requirements.

This is not the main issue. If the primes up to N are precomputed and stored,
that should be enough for all routines that currently require the primes
up to N^2. (Of course they will still be more efficient if all such primes
are available instead of requiring extra sieving...)

For larger values, one should do some on the fly sieving on decent-sized
chunks of consecutive integers (using whatever primes are currently
available) + pseudo-primality checks for whatever remains.

Conceptually easy, but not exactly trivial to incorporate in a transparent,
generic way ==> TODO.

Cheers,

    Karim.
--
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]