Karim Belabas on Fri, 22 Sep 2006 14:43:10 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: PrimeLimit |
* 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] `