Peter-Lawrence . Montgomery on Mon, 25 Sep 2006 03:14:40 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: PrimeLimit |
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, > > >