PrimeLimit

[Tautócrona]

Hi all:

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. Besides, the speed drops a lot, 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. I wonder if: a) one could set an arbitrarily long
limit for PrimeLimit, and b) one could get a bigger table of stored primes, to raise the
speed of forprime.

Thank you!

Jose Brox
http://espanol.groups.yahoo.com/group/Telecomunicacion/
***@terra.es
MSN Messenger: ***@hotmail.com

[Karim Belabas]

Post by Tautócrona
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).

Post by Tautócrona
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...

Post by Tautócrona
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)

Post by Tautócrona
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.

Post by Tautócrona
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]
`

[cino hilliard]

Subject: Re: PrimeLimit
Date: Fri, 22 Sep 2006 14:40:44 +0200

Post by Tautócrona
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.

(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...

The log of these is nicely linear.
1.77815125
2.093421685
2.357934847
2.64738297
2.926856709
3.211921084
3.496929648

You store the prime differences in the gp environment. Do you keep a running
prime every so
often to increment from or do you just add up the differences?

I have beat the prime limit problem from the standpoint of prime(x) by using
a sieve program to
store the 37,607,912,018 primes less than a trillion in binary format which
requires 301 gigs of
file space. Then I call a prime c program that reads this file with a
prime2 routine in Pari.

prime2(n) = \\ the nth prime using f:\sieve\primeapigcc.exe calling
prime2-1000bill.bin
{
local(x,s);
s=concat("f:/sieve/primeapigcc ",Str(n));
s=concat(s," > temp.txt"); \\Must save to a temp file for
correct output
system(s);
return(read("temp.txt"))
}


For example.
(16:43:03) gp > prime2(37607912018)
%40 = 999999999989

The sieve program takes about 1/2 a day to store. I would like to use a
difference scheme
to store many more primes in a lot less space. I guess the problem here will
be speed again.

My guess that the ith prime for every million primes could be stored in a
seperate file with a
value indication the record of the difference file. The we just add from
that point.

This would reduce the file considerabley or allow a whole bunch more primes.

Enjoy,
Cino Hilliard,

[P***@cwi.nl]

Instead of storing the primes themselves,
first observe any prime p > 30 satisfies GCD(p, 30) = 1.
For k >= 1, let a byte identify which (if any)
of 30*k + (1, 7, 11, 13, 17, 19, 23, 29) is/are prime.
A table with the primality of all integers between 30 and
a trillion will need (1 trillion)/30 bytes = 33 gigabytes,
way down from 301 gigabytes. You can change the wheel
to operate modulo 210, 2310, or 30030 rather than 30.

This data structure lets one test whether a random
integer within table range is prime. If one has a population
count instruction, one can quickly jump to the n-th prime
given the m-th prime for some m near n.

Peter Montgomery

Post by cino hilliard

Subject: Re: PrimeLimit
Date: Fri, 22 Sep 2006 14:40:44 +0200

Post by Tautócrona
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.

(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...

The log of these is nicely linear.
1.77815125
2.093421685
2.357934847
2.64738297
2.926856709
3.211921084
3.496929648
You store the prime differences in the gp environment. Do you keep a running
prime every so
often to increment from or do you just add up the differences?
I have beat the prime limit problem from the standpoint of prime(x) by using
a sieve program to
store the 37,607,912,018 primes less than a trillion in binary format which
requires 301 gigs of
file space. Then I call a prime c program that reads this file with a
prime2 routine in Pari.
prime2(n) = \\ the nth prime using f:\sieve\primeapigcc.exe calling
prime2-1000bill.bin
{
local(x,s);
s=concat("f:/sieve/primeapigcc ",Str(n));
s=concat(s," > temp.txt"); \\Must save to a temp file for
correct output
system(s);
return(read("temp.txt"))
}
For example.
(16:43:03) gp > prime2(37607912018)
%40 = 999999999989
The sieve program takes about 1/2 a day to store. I would like to use a
difference scheme
to store many more primes in a lot less space. I guess the problem here will
be speed again.
My guess that the ith prime for every million primes could be stored in a
seperate file with a
value indication the record of the difference file. The we just add from
that point.
This would reduce the file considerabley or allow a whole bunch more primes.
Enjoy,
Cino Hilliard,