mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2006-01-11, 12:27   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17·79 Posts
Default 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.
alpertron is offline   Reply With Quote
Old 2006-01-11, 14:11   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

162768 Posts
Default

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!
Prime95 is offline   Reply With Quote
Old 2006-01-11, 14:20   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17·79 Posts
Default

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+60k-t are not both composite)? Using this, the step 2 speed almost doubled in my ECM applet.

Last fiddled with by alpertron on 2006-01-11 at 14:23
alpertron is offline   Reply With Quote
Old 2006-01-11, 16:13   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1CBE16 Posts
Default

That should be implemented too
Prime95 is offline   Reply With Quote
Old 2006-01-11, 17:27   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17·79 Posts
Default

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 2006-01-11 at 17:29
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Optimizing a $1000 GIMPS investment koskol Hardware 11 2013-02-10 23:57
Optimizing for CPU architecture: unknown Intel almostfrugal Information & Answers 1 2012-09-19 14:22
Optimizing Core2 quad in Windows XP John Rheinstein Hardware 18 2009-09-23 16:14
Optimizing Athlon/Pentium3 Code Joe O Software 6 2003-10-15 04:23
Optimizing for Athlon?? Paulie Software 6 2002-09-13 23:01

All times are UTC. The time now is 14:07.

Sat Mar 6 14:07:49 UTC 2021 up 93 days, 10:19, 0 users, load averages: 1.12, 1.09, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.