mersenneforum.org ECM vs P1.
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-01-02, 21:54 #1 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 10001010011012 Posts ECM vs P1. I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish. If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally. However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
2014-01-02, 22:58   #2
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by petrw1 I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish. If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally.
Rather than rely on some ill-founded belief, why don't you
take the time and effort to learn how these algorithms actually work???
Or are you part of the IGG that is too lazy or unmotivated to be
bothered with something as trite as learning about this subject?

Quote:
 However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
You are severely confused. Let us take this one piece at a time.

I will assume that you mean "P-1" when you write P1.

(1) Where did you get the idea that running P-1 was equivalent to doing all ECM curves at once? Running P-1 is equivalent to running a
single elliptic curve.

(2) Comparing ECM running on a number of 5678 digits versus running
P-1 on a number of 44million digits is meshugah. Furthermore, I suspect
that you were not running an FFT Stage 2 for P-1. Its memory requirements are so vast that the machine would be paging continuously.
A machine running at (say) 2Ghz will yield 2Ghz days of CPU time per day
unless it is busy paging. I expect that ECM was doing some paging
and that you were only running Stage 1 of P-1.

If not, please say what B1/B2 limits you were using. Were you using a
GPU?

How much memory does the machine have?

2014-01-02, 23:06   #3
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts

Quote:
 Originally Posted by petrw1 I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish.
This is not an accurate summary of P-1.
I'd say instead that:
In P-1 factoring, you are interested in the factorization of the number 1 less than P ($P-1$).
In ECM you are interested in the factorization of some specific number $P+b$ where $b$ is about the size of $P$, (something like $-sqrt{P} < b < sqrt{P}$, which, roughly, means that the first half of the digits are the same as P and the rest are random) and can be calculated by a function where $f(sigma, P) = b$. Being able to choose different sigmas means that it's something like being able to run P-1 multiple times.
Which means that P-1 is like running a single curve of ECM where $b = -1$. For Mersenne and Fermat numbers, this happens to nicely coincide with known facts about what their factors can be, making it much more efficient than ECM at similar bounds.
Quote:
 Originally Posted by petrw1 If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally.
However, this is an accurate conclusion: both (in modern implementations) use FFTs, have a stage 1 based on B1 bounds, and a high-memory stage 2 based on B2 bounds.

Quote:
 Originally Posted by petrw1 However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
Both P-1 and ECM run FFTs, involving some significant amount of memory in stage 2. The biggest variable here is: How much memory was being used? Memory speed differences could be causing the difference between your machine and the reference machine (the machine whose benchmark was used to calculate what constitutes a GHz-day - I believe it's a Core 2 Duo).

Another smaller variable: What FFT size was being used in each test? Different CPUs can scale the speeds at different FFT sizes differently.

At a guess, your assigned memory or memory bandwidth is lower than the reference machine's. You might be able to improve this by upping the memory Prime95 can use, and using the fastest dual-channel memory configuration possible for your setup.

Last fiddled with by Mini-Geek on 2014-01-02 at 23:10

2014-01-02, 23:10   #4
chalsall
If I May

"Chris Halsall"
Sep 2002

221068 Posts

Quote:
 Originally Posted by R.D. Silverman How much memory does the machine have?
(In the voice of AGENT SMITH) MR. SILVERMAN...

Sorry, that's all I've got....

2014-01-02, 23:27   #5
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

43·103 Posts

Quote:
 Originally Posted by R.D. Silverman Rather than rely on some ill-founded belief, why don't you take the time and effort to learn how these algorithms actually work??? Or are you part of the IGG that is too lazy or unmotivated to be bothered with something as trite as learning about this subject? ..... A combination of too busy and sufficiently lacking in the fundamentals of any of these topics to learn enough to answer my question. You are severely confused. Let us take this one piece at a time. I will assume that you mean "P-1" when you write P1. ......... yes (1) Where did you get the idea that running P-1 was equivalent to doing all ECM curves at once? Running P-1 is equivalent to running a single elliptic curve. .........I stand corrected. (2) Comparing ECM running on a number of 5678 digits versus running P-1 on a number of 44million digits is meshugah. Furthermore, I suspect that you were not running an FFT Stage 2 for P-1. Its memory requirements are so vast that the machine would be paging continuously. A machine running at (say) 2Ghz will yield 2Ghz days of CPU time per day unless it is busy paging. I expect that ECM was doing some paging and that you were only running Stage 1 of P-1. If not, please say what B1/B2 limits you were using. Were you using a GPU? ..........B1=260000000, B2=26000000000 for ECM of 8192. ..........B1=570000, B2=9975000 for P-1 of 64M ..........No GPU How much memory does the machine have? ........1000Meg. 800 allocated to Prime95
See dots above. Thx for answering and questioning.

2014-01-02, 23:54   #6
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by petrw1 See dots above. Thx for answering and questioning.
1G is simply not enough memory for running Step 2 of either P-1
or ECM in an efficient manner.

What code are you using? Are you using GMP-ECM? It allows
one to limit memory usage in Step 2 by partitioning the data
that is generated into pieces.

Of course, one pays a penalty for this partitioning. How much of a penalty
depends on the size of the pieces relative to the amount of total
memory.

Your computer is simply underpowered and undersized by current
standards.

You would be well advised to spend a few bucks and buy more memory.
For (say) $50 you will enhance your performance by a fair bit. 2014-01-02, 23:59 #7 R.D. Silverman Nov 2003 1C4016 Posts Quote:  Originally Posted by petrw1 See dots above. Thx for answering and questioning. You wrote in response: Quote:  ..... A combination of too busy and sufficiently lacking in the fundamentals of any of these topics to learn enough to answer my question. Lack of fundamentals is correctable. It just requires motivation and dedication. We can help guide you. How much mathematics have you studied? Do you have a STEM degree? How well did you do in your math classes in high school?  2014-01-03, 01:26 #8 TheMawn May 2013 East. Always East. 172710 Posts Message deleted by TheMawn Last fiddled with by TheMawn on 2014-01-03 at 01:28 Reason: Duplicate Post somehow 2014-01-03, 01:28 #9 TheMawn May 2013 East. Always East. 32778 Posts Quote:  Originally Posted by R.D. Silverman Your computer is simply underpowered and undersized by current standards. You would be well advised to spend a few bucks and buy more memory. For (say)$50 you will enhance your performance by a fair bit.
Note to petrw1: Your older machine will very likely be using DDR2 memory. DDR2 is more expensive as it is an outdated standard. Newegg has a bunch but it's not cheap. Might not be worth your while.

Quote:
 Originally Posted by R.D. Silverman Lack of fundamentals is correctable. It just requires motivation and dedication. We can help guide you. How much mathematics have you studied? Do you have a STEM degree? How well did you do in your math classes in high school?
I've never fully understood that math either. I visit the P-1 and ECM pages on the mersenne wiki but I never get very far. I'll follow this discussion along out of curiosity.

2014-01-03, 03:49   #10
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

43·103 Posts

Quote:
 Originally Posted by R.D. Silverman You wrote in response: Lack of fundamentals is correctable. It just requires motivation and dedication. We can help guide you. How much mathematics have you studied? Do you have a STEM degree? How well did you do in your math classes in high school?
High school Math, though done well, was completed 37 year ago.
A University degree in Computer Science minoring in Math was completed 33 years ago.
33 years of IT work devoid of Math pretty much rusted all the math brain cells.
Don't know what STEM is.

And with a full time job still going; a wife and 4 kids and 3 grandkids and a hobby in music....as much as I would love to learn more about this stuff ... can't do it at this time That is why I need to concede that the best I can do is ask questions and hope someone is willing to give a quick and simple answer.

Sorry...and thanks again.

P.S. I agree that I should give this PC a proper burial. Plans are underway; in the meantime I hear CheeseHead "100.01 MPH > 100 MPH"

Last fiddled with by petrw1 on 2014-01-03 at 03:50

2014-01-03, 10:46   #11
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by petrw1 High school Math, though done well, was completed 37 year ago. A University degree in Computer Science minoring in Math was completed 33 years ago. 33 years of IT work devoid of Math pretty much rusted all the math brain cells. Don't know what STEM is. And with a full time job still going; a wife and 4 kids and 3 grandkids and a hobby in music....as much as I would love to learn more about this stuff ... can't do it at this time That is why I need to concede that the best I can do is ask questions and hope someone is willing to give a quick and simple answer.
The problem is that quite often, the answers are neither quick nor
simple. As in this case. Understanding the performance of ECM and
P-1 require fairly deep understanding not only of their underpinnings
but also of computer architecture.

Music? Consider how long it takes to learn to play (say) Chopin on
the piano. People are willing to devote time to things they like.
However, everyone here while claiming to be interested in this subject
always show disdain for taking the time to learn it.