P.I.E.S. - Prime Internet Eisenstein Search

[axn]

Originally Posted by Batalov

The last operation x^b may be a bit tricky; the usual exponentiation relies on x being small: lots of squarings with some mul by x.
When x is as large as the whole residue, the long mul will need to be implemented.

Squaring is done normally by:
* FFT
* point-wise squaring
* inv FFT
* carry adjustment.
During the carry adjustment, any mutliplication by the PRP-base can also be included.

For multiplication by a large X, we just need to repeat this operation once more (instead of doing it in carry propagation step) where we'll do point-wise multiplication by X (which would already be in FFT form). Since this would only be for a few 100 bits, the additional step doesn't matter in terms of speed. Should be very straightforward to implement.

[I don't know how this new-fangled Z transform works, but should be similar in principle).

[Batalov]

Originally Posted by axn

New version 0.5:

Fixed ETA calculation. Was off by a factor of 50% (if it said 1hr, it would actually take 1.5hr).
Changed ETA update frequency from once every 3 seconds to 10 seconds


Attached are the source, win32 exe (CUDA 3.2), and compile scripts for windows and linux.

Originally Posted by axn;primesearchteam.com

New version 0.6

CPU usage has been reduced, so fewer instances should be able to keep the GPUs fed (especially slower CPU/faster GPU combinations). You may want to retest which combinations of instances & B values gives most thruput.

There should be minor increase in overall thruput as well, as a result.

Share your experiences here.

Reposting from the other forum where sieving has been briefly run ~15 months ago and then was simply shut down and the effort discontinued.

axn, perhaps you could comment; maybe you have a code repository (at assembla?)

[Batalov]

I updated the cyclosv0.6.zip code to sieve for cyclotomics of the second type (Phi(3,-b^{3*2^n})) and will run the Phi(3,-b⁴⁹¹⁵²) for a short time. There should be perhaps a dozen primes there for b<1,500,000.
___________________
Phi(3,-b^{3^m*2^n}) with m>1 are less effective to run (at least on CPU) because only 3*2^n and 9*2^n FFT patterns are currently implemented in gwnum; the 9*2^n FFT is perfect for Phi(3,-b⁴⁹¹⁵²). A clever extension to CycloOCL code may change that.

[Batalov]

With Ryan P., we've run the Phi(3,-b^98304) series, too.
And now continuing with Phi(3,-b^196608) -- which will produce a string of 2-million digit primes.

Oh, it is so nice to have resources!

[axn]

Current tally is:

32768 27 (max = 1164012)
49152 18 (max = 1373894)
65536 18 (max = 1181782)
98304  8 (max = 1202113)
131072 3+1 (max = 1082083)

Plus assorted primes for 34992, 36864, 41472, 46656, 78732.

[Batalov]

Even more small ones:

1       2592
849     4096
5       5184
1       5832
355     8192
1       13122
107     16384
...     24576
48      32768
1       34992
2       36864
2       41472
1       46656
27      49152
1       59049 (3^10, Zhou)
18      65536
1       78732
8       98304
4       131072
2       196608
2       262144
1       393216
1       524288

[paulunderwood]

Originally Posted by Batalov

With Ryan P., we've run the Phi(3,-b^98304) series, too.
And now continuing with Phi(3,-b^196608) -- which will produce a string of 2-million digit primes.

Oh, it is so nice to have resources!

Congrats for this one!

[Batalov]

Thanks!

Writing the modified sieve was fun. I had to implement a modular cubic root again (but I already had an innoculation with this small diversion; this time I didn't need Adleman-Manders-Miller's; with the cyclotomic restrictions all cubic roots were easy).
And then the PhiExtension for P95 proved itself useful -- ...we still don't have a supernumeral-3 version of Cyclo{OCL|CPU}.

[paulunderwood]

Congrats to Serge and Ryan for this 2,259,865 digit prime

[pepi37]

Originally Posted by Batalov

With Ryan P., we've run the Phi(3,-b^98304) series, too.
And now continuing with Phi(3,-b^196608) -- which will produce a string of 2-million digit primes.

Oh, it is so nice to have resources!

Who has greater resources , you or him? :)

Congratulation on this huge prime.

[paulunderwood]

Wow! 3,068,389 decimal digits. Congrats to Ryan and Serge again.