20200522, 04:37  #34 
Romulan Interpreter
Jun 2011
Thailand
3·13·229 Posts 
Wow! Ben, that is freaking wonderful! And you kept it for yourself for such a long time!
Now I will have to upgrade yafu... (grrr... still using old versions here and there, you know, if it works, don't fix it...) (unfortunately, since I discovered pari, I did most of my "numerology" in it, so the loops and screws came somehow too late, but be sure I will give it a try, I still have some ideas in a far side corner of the brain, which I never had the time/knowledge/balls to follow...) Last fiddled with by LaurV on 20200522 at 04:39 
20200522, 16:24  #35  
"Ben"
Feb 2007
13·257 Posts 
Quote:
Last fiddled with by bsquared on 20200522 at 16:24 

20200527, 18:48  #36 
"Ben"
Feb 2007
13×257 Posts 
I've been spending a little time with the TLP variation again... integrating jasonp's batch factoring code and investigating parameters. The batch factoring code provides a huge speedup for TLP, easily twice as fast as before at C110 sizes. The crossover with DLP quadratic sieve now appears to be around C110, although I'm still not convinced I have found optimal parameters for TLP. There are a lot of influential parameters. So as of now, TLP is still slower than regular DLP in sizes of interest to the quadratic sieve (C95C100).
Code:
C110 48178889479314834847826896738914354061668125063983964035428538278448985505047157633738779051249185304620494013 80 threads of cascadelake based xeon: DLP: 1642 seconds for sieving TLP: 1578 seconds for sieving 
20200712, 16:06  #37  
"Tilman Neumann"
Jan 2016
Germany
3×139 Posts 
Quote:
Compare a polynomialmajor SIQS to a primemajor SIQS. (both singlethreaded) The conversion of my old (polynomialmajor) SIQS to a primemajor SIQS took two steps: 1. Compute the solution arrays for all (a, b)polynomials of one aparameter outside the sieve. 2. In the sieve, have outer loop over primes, inner loop over polynomials. At first, performance was very bad. I had to switch two parameters to improve that: 1. Increase the sieve array size. 2. Reduce qCount = the number of q's whose product gaves the aparameter. These measures improved performance a lot, but the result is still bad. Here is a comparison to the polynomialmajor sieve: Code:
200 bit: Polymj 4s, 789ms, Primemj 11s, 224ms, ratio = 2.34370 210 bit: Polymj 8s, 22ms, Primemj 21s, 269ms, ratio = 2.65133 220 bit: Polymj 19s, 609ms, Primemj 55s, 826ms, ratio = 2.84695 230 bit: Polymj 40s, 232ms, Primemj 2m, 12s, 960ms, ratio = 3.30483 240 bit: Polymj 55s, 305ms, Primemj 3m, 12s, 622ms, ratio = 3.48290, Primemj sieveArraySize = 119552 250 bit: Polymj 2m, 15s, 526ms, Primemj 8m, 11s, 63ms, ratio = 3.62338, Primemj sieveArraySize = 159744 260 bit: Polymj 4m, 49s, 561ms, Primemj 43m, 30s, 551ms, ratio = 9.01554, Primemj sieveArraySize = 206848 For smaller N, the performance gap stems mostly from additional array accesses and another loop for the largest primes that is not necessary in the polynomialmajor version. The performance breakin at 260 bit might point out too many L3 cache misses. Kleinjungs SIQS might remedy many of the problems of a silly primemajor sieve. But maybe we can see here what the challenge is.  @Jason: It seems that Colin Percivals stuff has never been published? The only thing I found were some comments in another forum... Last fiddled with by Till on 20200712 at 16:24 

20200713, 15:52  #38 
Tribal Bullet
Oct 2004
3·1,163 Posts 
It was never published. When I asked him about it in ~2007 he said he was too busy with his startup company to work on it.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where do I send my PRP primes with large k?  Trilo  Riesel Prime Search  3  20130820 00:32 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
NFS with 5 and 6 large primes  jasonp  Factoring  4  20071204 18:32 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 