mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2006-04-01, 00:03   #45
VJS
 
VJS's Avatar
 
Dec 2004

13×23 Posts
Default

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...
VJS is offline  
Old 2006-04-03, 17:37   #46
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

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
Mystwalker is offline  
Old 2006-04-03, 17:39   #47
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

14778 Posts
Default

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?
Mystwalker is offline  
Old 2006-04-03, 18:15   #48
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1FD716 Posts
Default

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.
Prime95 is online now  
Old 2006-04-18, 10:15   #49
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

2678 Posts
Default

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
wreck is offline  
Old 2006-04-24, 18:39   #50
VJS
 
VJS's Avatar
 
Dec 2004

29910 Posts
Default

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.
VJS is offline  
Old 2006-04-25, 09:00   #51
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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.
Mystwalker is offline  
Old 2006-04-25, 11:23   #52
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts
Default

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.
R.D. Silverman is offline  
Old 2006-04-25, 17:06   #53
Joe O
 
Joe O's Avatar
 
Aug 2002

3×52×7 Posts
Default

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
Joe O is offline  
Old 2006-04-26, 09:05   #54
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

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.
Mystwalker is offline  
Old 2006-04-26, 11:14   #55
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts
Default

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?
R.D. Silverman is offline  
Closed Thread

Thread Tools


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔