mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2010-04-06, 20:49   #1
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

607 Posts
Default gmp-ecm needed memory and runtime

Hello,
I run gmp-ecm with B1=43M and different input number length. Afterwards I made a chart of estimated memory (red line) and measured run time (blue line).
X: number length

Estimated memory is nearly linear increasing, this shows also the chart for different B1. But why is there a big jump in the line?

Runtime seems to grow potencially (bah, what is the right engl. word?). Can somobod confirm or explain it?

yoyo
Attached Thumbnails
Click image for larger version

Name:	43M.PNG
Views:	197
Size:	113.9 KB
ID:	4965  
yoyo is offline   Reply With Quote
Old 2010-04-07, 07:14   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

32×11×107 Posts
Default

Quote:
Originally Posted by yoyo View Post
Runtime seems to grow potencially (bah, what is the right engl. word?).
"Exponentially".

Paul
xilman is offline   Reply With Quote
Old 2010-04-07, 07:48   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·3,191 Posts
Default

This isn't an exponential-growth case. I can't think of a nice English word for "as some power of the input"; 'polynomially' suggests it's an integer exponent which isn't the case.
fivemack is offline   Reply With Quote
Old 2010-04-07, 13:52   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by yoyo View Post
Hello,
I run gmp-ecm with B1=43M and different input number length. Afterwards I made a chart of estimated memory (red line) and measured run time (blue line).
X: number length

Estimated memory is nearly linear increasing, this shows also the chart for different B1. But why is there a big jump in the line?

Runtime seems to grow potencially (bah, what is the right engl. word?). Can somobod confirm or explain it?

yoyo
read my joint paper with Sam Wagstaff:

A Practical Analysis of ECM
Math. Comp.
R.D. Silverman is offline   Reply With Quote
Old 2010-04-07, 16:09   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

Bob's paper would answer your question, but it's overkill for you needs, it's hard to get hold of if you aren't associated with a university, and it has an error that made it hard, at least for me, to follow (although not relevant to your question).

The jump in memory happens when the granularity of the FFT changes. Large numbers are represented as arrays of numbers - much like decimal numbers are arrays of digits. As the number gets larger, the maximum size permitted in each array element gets smaller.

To make up some numbers for the sake up discussion, as the size goes from 100 to 500 digits, you are using 3 digits per element, and the memory grows because you need 34 elements for the 100 digit numbers and 167 elements for the 500 digit number. But between 500 and 600 digits you must shift to 2 digits per element, so 600 digits requires arrays of length 300 - much longer than the 200 you would get from the earlier growth. It then grows slowly until the next jump.

The change in granularity is necessary because of how FFT multiplication deals with carrying. When we do multiplication by longhand, we treat the numbers as arrays of single digits and we integrate the carries in two stages. But FFT multiplication computes a convolution - this is as if we kept the results of each multiply (for 5x5, keeping the whole 25 instead of keeping the 5 and carrying the 2), AND in the addition stage we keep the whole totals instead of keeping the last digit and carrying the rest. Hence the convolution of 153 x 718 would be
Code:
       1   5   3
       7   1   8
      ----------
       8  40  24
    1  5   3
 7 35 21
 ---------------
 7 36 34  43  24

From which you could then do the carries as
       24
      43
     34
    36
    7
   ------
   109854

To get the product
The problem is that the individual array elements must be large enough to hold the column sums before the carry stage. As the array gets longer, the potential size of the sums grows. When the sum threatens to overflow, you must make the individual elements smaller.

William
wblipp is offline   Reply With Quote
Old 2010-04-07, 16:13   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

What is the unit of "length" and on what kind of system (in particular, 32 bit or 64 bit) were the timings produced?

Alex
akruppa is offline   Reply With Quote
Old 2010-04-07, 16:42   #7
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

607 Posts
Default

Quote:
Originally Posted by akruppa View Post
What is the unit of "length" and on what kind of system (in particular, 32 bit or 64 bit) were the timings produced?
Alex
Length=number of digits of the input number
It was produced on a 64bit Suse Linux i7 processor:
http://www.rechenkraft.net/yoyo/show...hp?hostid=8036

yoyo
yoyo is offline   Reply With Quote
Old 2010-04-09, 16:48   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Consider stage 1 and stage 2 separately, their run times behave rather differently for increasing input number size.

For relatively small input, usually bounded by GMP's MUL_TOOM22_THRESHOLD (28 by default on K8/K10 systems), the multiplication is simply quadratic time grammar-school, so in theory the time grows like the square of the number of words in the input. In practice the growth is a little slower due to overhead. In GMP-ECM 6.3 we also switch from GMP-ECM's own multiplication functions to GMP's which are faster for operands of more than 15-20 words (depending on CPU), so the growth will again slow down a bit, even though each algorithm is quadratic time. Above MUL_TOOM22_THRESHOLD, GMP uses asymptotically faster algorithms like Karatsuba with complexity O(n^1.59), Toom-3, etc, and eventually Schönhage-Strassen with O(n log n loglog n). So for large enough input, the stage 1 time eventually becomes quasi-linear.

In stage 2 the time is mostly linear in the size of the inputs. There is some modular arithmetic, but the time for polynomial multiplication normally dominates. With NTT, that time is O(deg * n^2) for conversion between Z/NZ and NTT primes, and O(n * deg * log(deg)) for the transforms. The initialisation of the NTT primes is cubic time however, which will dominate for large enough input. Without NTT, stage 2 uses Schönhage-Strassen which results in quasi-polynomial time for pretty much all input sizes, at the cost of using more memory.

So, sadly, there's no easy "grows like n^c" answer. Stage 1 is quasi-linear eventually, but almost quadratic for most numbers that we try to factor.
Stage 2 becomes cubic(!) eventually when using NTT, but is pretty much linear for numbers and parameters we typically use, and stays pretty much
linear if you don't use the NTT.

For stage 1, here's a graph for 1, ..., 23 words with B1=1M on a Core 2 2133 MHz.The graph fits a 51x2+106x+982 function pretty well up to 20 words, where a jump occurs since we switch to GMP functions at that point which are a no faster than our own on Core 2 but incur more overhead (Note: On AMD cpus we switch to GMP functions earlier, because they actually are faster there). I haven't made a graph for stage 2 times yet, but I expect that for reasonable B2 it will be pretty linear in the number of NTT primes, which is more-or-less proportional to the number of words in the modulus.

Alex
Attached Thumbnails
Click image for larger version

Name:	time.png
Views:	138
Size:	3.6 KB
ID:	4993  

Last fiddled with by akruppa on 2010-04-09 at 17:17
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is ECC memory needed? joe a Hardware 35 2016-11-07 22:06
Predicting QS and NFS runtime jasonp Factoring 2 2011-03-07 01:22
Memory Needed Unregistered Information & Answers 2 2009-09-20 15:21
ECM Runtime and F20 D. B. Staple Factoring 11 2007-12-12 16:52
amount of memory needed for Stage 2 (factor) pin Software 13 2003-03-18 19:54

All times are UTC. The time now is 03:19.

Sun Mar 7 03:19:18 UTC 2021 up 93 days, 23:30, 0 users, load averages: 1.39, 1.48, 1.40

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.