Re: PrimeLimit

[Peter-Lawrence.Montgomery@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
>
>
>>From: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
>>To: pari-users@list.cr.yp.to
>>Subject: Re: PrimeLimit
>>Date: Fri, 22 Sep 2006 14:40:44 +0200
>>
>>* 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.
>
>>(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,
>
>
>