20060111, 12:27  #1 
Aug 2002
Buenos Aires, Argentina
2·3^{2}·79 Posts 
Optimizing step 2 of ECM on Prime95
Just to satisfy my curiosity, I downloaded the Prime95 source files and started to read the file ecm.c, where ECM is implemented.
It is not completely clear to me, but it appears that the code is using 8 multiples of the point found at the end of step 1 in the table used in step 2 when the modulus is 30 (all positive integers coprime to 30 and less than it). But only 4 multiples are enough, thus needing half the memory and making it twice as fast. Please read the text I wrote on More detailed explanation section of ECM on MersenneWiki. 
20060111, 14:11  #2 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{5}·3^{5} Posts 
IIRC, prime95 steps through the B1 to B2 range in multiples of 60 when the modulus is 30.
P.S. You are very brave to be looking in the ecm source code! 
20060111, 14:20  #3 
Aug 2002
Buenos Aires, Argentina
2×3^{2}×79 Posts 
In that case the optimization is already done.
What about the other optimization I wrote on MersenneWiki (multiplying the coordinates of the points where C+60k+t and C+60kt are not both composite)? Using this, the step 2 speed almost doubled in my ECM applet. Last fiddled with by alpertron on 20060111 at 14:23 
20060111, 16:13  #4 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{5}·3^{5} Posts 
That should be implemented too

20060111, 17:27  #5 
Aug 2002
Buenos Aires, Argentina
2·3^{2}·79 Posts 
OK. I've seen that code on stage 2, using the sieve() function to find the primes.
Of course the comment on line 2762 should be Do the m to m+D range. Last fiddled with by alpertron on 20060111 at 17:29 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Optimizing a $1000 GIMPS investment  koskol  Hardware  11  20130210 23:57 
Optimizing for CPU architecture: unknown Intel  almostfrugal  Information & Answers  1  20120919 14:22 
Optimizing Core2 quad in Windows XP  John Rheinstein  Hardware  18  20090923 16:14 
Optimizing Athlon/Pentium3 Code  Joe O  Software  6  20031015 04:23 
Optimizing for Athlon??  Paulie  Software  6  20020913 23:01 