New GMP!!

[VJS]

Originally Posted by PBMcL

Bob, this may be true on a one processor machine, but the disparity in memory requirements between step 1 and step 2 has led me to a different strategy for multi-processor machines in the case where step 2 is going to use most of the available RAM. Given, say, a four processor box I choose B1 and B2 so that step 2 takes just less than a quarter of the total (step 1 plus step 2) time (which may require some test curves), then I stagger start 4 copies of ECM so that only one copy at a time is in step 2. Otherwise the machine spends huge amounts of time swapping pages to/from the disk.

Interesting, however Bob's point was based on the most efficient bounds for B1 vs B2 assuming the computer is not a limitation.

I suggest you try to stick with that recommendation and use the following technique to circumvent the memory limitation. You can setup the B1 B2 bounds as Bob suggested where b1 takes slightly more time than b2, say 2%.

Using the command line save the residue from stage 1 and start a second stage 1 curve with the first processor.
With the second processor run the stage 2 curve on the stage 1 residue, after several day you may build up a few extra stage 1's but I'm sure you can deal with that.

I would think that most 4 processor machines have at least 4G of memory so curves taking more than 2G??? Those must be some high bounds...

[Mystwalker]

I tried the mingw version of gwnum - and failed. I just realized that, unfortunately, the output that corrupted. I hope this piece of it is enough for help. I currently don't have access to a build system:

libecm.a(Fgw.o)(.text+0x27f): In function `make_conv_plan':
C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/Fgw.c:127: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x291):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:127: undefined reference to `valloc'
libecm.a(Fgw.o)(.text+0x2c7):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:136: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x2dd):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:139: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x330):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:169: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x359):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:177: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x38a):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:184: undefined reference to `_FFTLEN'
libecm.a(Fgw.o)(.text+0x427):C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/F
gw.c:139: more undefined references to `_FFTLEN' follow
libecm.a(Fgw.o)(.text+0xef9): In function `Fgwmul':
C:/Programme/msys/home/dennis/ecm-6.1-beta2 gwnum/Fgw.c:771: undefined reference

[Mystwalker]

Compiling gwnum also did not work:

$ make
gcc -I.. -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c ecmstag1.c
gcc -I.. -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c cpuid.c
gcc -I.. -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c gwnum.c
gcc -I.. -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c gwutil.c
g++ -I.. -I../dbldbl -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c gwdbldb l.cpp
In file included from gwdbldbl.cpp:44:
../dbldbl/doubledouble.cc: In function `int digits(const doubledouble&, const
doubledouble&)':
../dbldbl/doubledouble.cc:72: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/doubledouble.h:234: warning: in passing argument 1 of `int intq(const
doubledouble&)'
In file included from gwdbldbl.cpp:44:
../dbldbl/doubledouble.cc: In function `doubledouble modf(const doubledouble&,
doubledouble*)':
../dbldbl/doubledouble.cc:232: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble exp(const doubledouble&)':
../dbldbl/math.cc:45: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble hypot(doubledouble,
doubledouble)':
../dbldbl/math.cc:70: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble log(const doubledouble&)':
../dbldbl/math.cc:113: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble powint(const doubledouble&, int)':
../dbldbl/math.cc:138: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble sin(const doubledouble&)':
../dbldbl/math.cc:181: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/math.cc:181: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble atan(const doubledouble&)':
../dbldbl/math.cc:303: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble erf(doubledouble)':
../dbldbl/math.cc:345: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/math.cc:354: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble erfc(doubledouble)':
../dbldbl/math.cc:397: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/math.cc:405: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
In file included from gwdbldbl.cpp:45:
../dbldbl/math.cc: In function `doubledouble gamma(doubledouble)':
../dbldbl/math.cc:491: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/math.cc:491: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
../dbldbl/math.cc:491: warning: passing `double' for argument 1 of `
doubledouble::doubledouble(int)'
gcc -I.. -O2 -march=i486 -malign-double -DADD_UNDERSCORES -c giants.c
objcopy -Oelf32-i386 -Icoff-i386 mult.obj mult.o
c:\Programme\MinGW\bin\objcopy.exe: mult.obj: Invalid bfd target
make: *** [mult.o] Error 1

Any suggestions? Maybe I have to update parts of mingw?

[Prime95]

Originally Posted by Mystwalker

Compiling gwnum also did not work:

Any suggestions? Maybe I have to update parts of mingw?

You'll need to get binutils and add COFF object file support in order to rebuild gwnum.

[wreck]

I want to know why the B2 always changed when the new version coming.
and how many curves should run with the B1 and default B2.

some test data:
GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Input number is 162385812809900583261295597372983559948698484946321658540735656202018003505845104737134070357362269119992033891923896707742660065148483572244656969761256208962241824944638737217461295395400432531624931235045560966776497496089919 (228 digits)
Using B1=11000000, B2=25577181640, polynomial Dickson(12), sigma=894268038
Step 1 took 556908ms
Step 2 took 194815ms


BotXXX P4 - GMP-ECM 6.1-beta2 [powered by GMP 4.2] [ECM]
Input number is (10^239-1)/9/479/142847911 (228 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=2918134401
Step 1 took 492485ms
Step 2 took 204422ms

[VJS]

Well your result looks pretty good nonetheless.

10% faster in stage 1 with a B2 increase of 40% for pretty much the same time input.

[Mystwalker]

Originally Posted by wreck

I want to know why the B2 always changed when the new version coming.

That's because the optimal distribution between B1 and B2 changes with ongoing improvement. If, for example, the computation of stage2 (--> B2) got faster, it would be wise to increase its default value.

and how many curves should run with the B1 and default B2.

Just use the -v parameter. Now, you can see how many curves you have to run for the chosen digit level. You can even investigate a little and come up with a better B2 value, because the default one is not necessarily the best in every situation, e.g. the use of Prime95 for stage1 for numbers with base 2 lowers the optimal B2 value.

[R.D. Silverman]

Originally Posted by wreck

I want to know why the B2 always changed when the new version coming.
and how many curves should run with the B1 and default B2.

I have said multiple times this before, but the message does not seem
to get across.

The response surface (for probability of success as a function of B1, B2,
#curves) is VERY shallow in the neighborhood of the optimum.

It DOES NOT REALLY MATTER if one varies B2 from the 'true' optimum.
One can spend CPU time by increasing B2. Or one can reduce B2 and run
more curves in the same amount of time. The probability of overall success
is relatively INSENSITIVE to this choice. [as long as you are not too far
off in selection of B1]. Select B1. Determine how much time you
want to spend. Period. Don't worry about B2.

My paper with Sam Wagstaff: "A Practical Analysis of The Elliptic Curve
Factoring Algorithm" should be mandatory reading for anyone who
wants to worry about how to select the parameters.

[Joe O]

My paper with Sam Wagstaff: "A Practical Analysis of The Elliptic Curve
Factoring Algorithm" should be mandatory reading for anyone who
wants to worry about how to select the parameters.

This paper has been discussed many times in these fora. Please look here:
http://www.mersenneforum.org/showthr...urve#post77078

[Mystwalker]

Originally Posted by Joe O

This paper has been discussed many times in these fora. Please look here:
http://www.mersenneforum.org/showthr...urve#post77078

Maybe we should link available information on these topics in a more prominent place - when knowledge is buried deep into a forum, I don't expect new members to get a hold of it.
We could promote the mersennewiki and enhance the "Choosing the best parameters for ECM" section.

It is important to remind oneself that parameter choices of ECM are not as critical as they are for e.g. NFS. On the other hand, I found non-negligible speedups especially for base-2 factorizations when step1 is performed with prime95/mprime. For B1=11e7 (which is a rather extreme case), the optimal B2 parameter gives me a performance increase of over 30%. For B1=250K, it went down to ~7.5%.
Using only gmp-ecm, the improvement is much smaller. In my opinion, here, it only makes sense for "bigger" factorizations (e.g. B1 >= 11M), where even a speedup of some percent add up to hours or even days.

[R.D. Silverman]

Originally Posted by Mystwalker

Maybe we should link available information on these topics in a more prominent place - when knowledge is buried deep into a forum, I don't expect new members to get a hold of it.
We could promote the mersennewiki and enhance the "Choosing the best parameters for ECM" section.

It is important to remind oneself that parameter choices of ECM are not as critical as they are for e.g. NFS. On the other hand, I found non-negligible speedups especially for base-2 factorizations when step1 is performed with prime95/mprime. For B1=11e7 (which is a rather extreme case), the optimal B2 parameter gives me a performance increase of over 30%. For B1=250K, it went down to ~7.5%.
Using only gmp-ecm, the improvement is much smaller. In my opinion, here, it only makes sense for "bigger" factorizations (e.g. B1 >= 11M), where even a speedup of some percent add up to hours or even days.

This is gibberish at worst and misleading at best.

The term "performance increase" is not what is being measured here.

When you say that for B1 = 110M the optimal B2 improves "performance"
by 30% do you mean that your probability of finding a 55 digit factor
increased by 30% over choosing a smaller B2 but with more curves????
[i.e. the time you spent is held constant]? 30% is much too large.
The response surface is too flat. I do not believe this number. Where
did you get it?

I doubt this is what you mean. We have not FOUND enough 55 digit
factors to even MAKE this kind of measurement. You say that a speedup
" of some percent add up to hours or even days." This is MEANINGLESS
because

(1) You certainly do not have enough data to be able to say that
an optimally chosen B2 will save "days" in finding a p55. How many p55's
have you found? The time it takes to find even one will be a random
variable with fairly high variance. It will take a lot of successes to determine
a difference between the mean time for two different B2 values. The entire
effort of the entire world has not collected enough data.

(2) What does "days" mean? How many machines etc.

You are being very imprecise in your terminology and it will be
highly misleading to the naiive user.

Certainly changing B2 will affect the run time for each curve. But for
a fixed amount of time, reducing B2 allows more curves to be run.

Let N be the number of curves you run with optimal B2 and let
N' be the number of curves you run with sub-optimal B2'. Let
P(B1, B2) be the probability of success *per curve*. Then the
respective overall probabilities will be 1 - (1 - P(B1,B2))^N and
1 - (1 - P(B1, B2'))^N'. If you spend the same amount of time
with each set of parameters, the ratio of the probabilities will be very close
to 1 if B1 is chosen appropriately. They will certainly NOT differ
by 30% and you can't possibly have collected enough data to justify
your claim of 30%. How many 55 digit factors have you found?