Igor Schein on Wed, 16 Mar 2005 20:25:49 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: *** prime: not enough precomputed primes

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:

(14:12:21) gp> default(primelimit,2^32-1)
  ***   default: incorrect value for primelimit [0-4294965247]: 4294967295
(14:12:22) gp> 4294965247==2^32-2^11-1

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

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