mersenneforum.org New GMP!!
 Register FAQ Search Today's Posts Mark Forums Read

2006-04-01, 00:03   #45
VJS

Dec 2004

13×23 Posts

Quote:
 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...

2006-04-03, 17:37   #46
Mystwalker

Jul 2004
Potsdam, Germany

3·277 Posts

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:

Quote:
 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

2006-04-03, 17:39   #47
Mystwalker

Jul 2004
Potsdam, Germany

14778 Posts

Compiling gwnum also did not work:

Quote:
 \$ 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?

2006-04-03, 18:15   #48
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

1FD716 Posts

Quote:
 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.

 2006-04-18, 10:15 #49 wreck     "Bo Chen" Oct 2005 Wuhan,China 2678 Posts 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. Code: 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 Last fiddled with by wreck on 2006-04-18 at 10:23
 2006-04-24, 18:39 #50 VJS     Dec 2004 29910 Posts 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.
2006-04-25, 09:00   #51
Mystwalker

Jul 2004
Potsdam, Germany

3×277 Posts

Quote:
 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.

Quote:
 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.

2006-04-25, 11:23   #52
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts

Quote:
 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.

2006-04-25, 17:06   #53
Joe O

Aug 2002

3×52×7 Posts

Quote:
 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

2006-04-26, 09:05   #54
Mystwalker

Jul 2004
Potsdam, Germany

3·277 Posts

Quote:
 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.

2006-04-26, 11:14   #55
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts

Quote:
 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?

All times are UTC. The time now is 01:33.

Sat Jan 28 01:33:32 UTC 2023 up 162 days, 23:02, 0 users, load averages: 1.37, 1.18, 1.12