Re: PrimeLimit

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

* Tautócrona [2006-09-20 15:20]:
> I usually work with primes in Pari-GP, and find the PrimeLimit
> parameter very small for my purposes. I know that with the command
> Default(PrimeLimit, N) I can make PrimeLimit as big as N, but N ~
> 4*10^9 seems to be the final limit.

It is (on a 32-bit machine).

> Besides, the speed drops a lot

Could you post a specific (minimal) example ? I doubt primelimit / forprime
are the culprits here, something in your code must get slower as p increases:

(11:22) gp > default(primelimit,2^31)
time = 14,648 ms.
(11:22) gp > gettime(); for (i=25,31, forprime(p=2,2^i,); print(gettime()))
60
124
228
444
845
1629
3140

Nicely linear in forprime's upper bound...

> I suppose because the primes up to 10^6 are precomputed and stored,
> and from there they are computed every time I run the routine. 

No. All primes up to primelimit are store once and for all (actually,
the differences between consecutive primes)

> I wonder if: a) one could set an arbitrarily long limit for PrimeLimit,

That wouldn't be too useful. How much physical memory does your machine
have ? 1GB ? Then primelimit would be restricted around 10^10 anyway.

> and b) one could get a bigger table of stored primes, to raise the
> speed of forprime.

One thing that could be done is to allow 'forprime' to sieve himself
up to primelimit^2, a sizeable extension.

Another is to let it test for (pseudo-)primality (after a preliminary
sieve), making its range arbitrary.

This won't cure your speed problem, though.

Cheers,

    K.B.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`