mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-02-14, 13:08   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default GMP ECM slow on my laptop?

Would someone compare their CPU times with the following:

Code:
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [ECM]
Input number is 41395211369606896878762271001715299418628538444891068431339891131233286833518837537078454323513136270166441222001636474306346761096507512180479117007959668872537359710374519637202679457204183583357 (197 digits)
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=47819535
Step 1 took 40132723ms
Step 2 took 6371596ms
Run 2 out of 300:
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=43712352
Step 1 took 40294996ms
Step 2 took 6371876ms
Run 3 out of 300:
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=2848791383
Step 1 took 40156436ms
Step 2 took 6291052ms
Run 4 out of 300:
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=194802029
Step 1 took 39571027ms
Step 2 took 6356635ms
Run 5 out of 300:
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=2015941534
Step 1 took 39904213ms
Step 2 took 6184738ms
This is the cofactor of 2,1822M.

Inputs were:

gmpecm64 -c 300 -chkpnt file1 -base2 1822 500000000 < inputfile

11 hours for step 1 seems slow. Is it?

It is also clear that the Step 2 limit is too low. I need to set it near
10^15 or so.
R.D. Silverman is offline   Reply With Quote
Old 2011-02-14, 22:42   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32×331 Posts
Default

64 bit gmp-ecm on 1 core of a penryn Q9450 2.66 Ghz:

Code:
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [ECM]
Input number is 4139521136960689687876227100171529941862853844489106843133989113
12332868335188375370784543235131362701664412220016364743063467610965075121804791
17007959668872537359710374519637202679457204183583357 (197 digits)
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=1069381386
Step 1 took 8775181ms
Step 2 took 1918750ms

Stage2 with gmp-ecm built in B2 value is 1.5-8 times faster than stage1. The longer stage1 takes the faster stage2 is compared to stage1, see for example these timings: core2-64bittests.html
ATH is offline   Reply With Quote
Old 2011-02-14, 23:50   #3
Syd
 
Syd's Avatar
 
Sep 2008
Krefeld, Germany

2×5×23 Posts
Default

edit: these were accidently done without "-base2 1822", I'll redo and post here later.

Here are some results from my machines, all running linux:

32bit GMP-ECM on a P4 2Ghz, B1=50M only, no stage 2 (not enough memory):

Code:
GMP-ECM 6.2 [powered by GMP 4.3.2] [ECM]
Running on node_s_15
Input number is 41395211369606896878762271001715299418628538444891068431339891131233286833518837537078454323513136270166441222001636474306346761096507512180479117007959668872537359710374519637202679457204183583357 (197 digits)
Using MODMULN
Using B1=50000000, B2=96215189086, polynomial Dickson(12), sigma=1024836075
dF=65536, k=2, d=690690, d2=17, i0=56
Expected number of curves to find a factor of n digits:
20      25      30      35      40      45      50      55      60      65
2       5       16      59      263     1354    7921    51176   363393  2810305
Step 1 took 1800296ms
Using 46 small primes for NTT
Estimated memory usage: 257M
^C
with B1=500M stage 1 it would take an estimated ~5hours


Phenom 2 @3.6Ghz, libgmp compiled with -march=barcelona and -O3

Code:
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [ECM]
Running on debian
Input number is 41395211369606896878762271001715299418628538444891068431339891131233286833518837537078454323513136270166441222001636474306346761096507512180479117007959668872537359710374519637202679457204183583357 (197 digits)
Using MODMULN
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=1358602455
dF=524288, k=3, d=5705700, d2=17, i0=71
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
18      59      219     917     4234    21335   116936  683883  4265169 2.8e+07
Step 1 took 1776600ms
Using 24 small primes for NTT
Estimated memory usage: 2337M
Initializing tables of differences for F took 3420ms
Computing roots of F took 47140ms
Building F from its roots took 35840ms
Computing 1/F took 14350ms
Initializing table of differences for G took 360ms
Computing roots of G took 40460ms
Building G from its roots took 36840ms
Computing roots of G took 40500ms
Building G from its roots took 36800ms
Computing G * H took 7610ms
Reducing  G * H mod F took 7710ms
Computing roots of G took 40480ms
Building G from its roots took 36910ms
Computing G * H took 7670ms
Reducing  G * H mod F took 7680ms
Computing polyeval(F,G) took 66600ms
Computing product of all F(g_i) took 250ms
Step 2 took 432790ms
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
10.95h  1.50d   5.60d   23.44d  108.27d 1.49y   8.19y   47.91y  298.81y 1981y
and the last one: Core 2, 2,66Ghz, libgmp compiled with -march=nocona and -O2

Code:
GMP-ECM 6.3 [configured with GMP 5.0.1 and --enable-asm-redc] [ECM]
Running on node_n_11
Input number is 41395211369606896878762271001715299418628538444891068431339891131233286833518837537078454323513136270166441222001636474306346761096507512180479117007959668872537359710374519637202679457204183583357 (197 digits)
Using MODMULN
Using B1=500000000, B2=9535491365416, polynomial Dickson(30), sigma=256865628
dF=524288, k=3, d=5705700, d2=17, i0=71
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
18      59      219     917     4234    21335   116936  683883  4265169 2.8e+07
Step 1 took 3335970ms
Using 24 small primes for NTT
Estimated memory usage: 2337M
Initializing tables of differences for F took 6020ms
Computing roots of F took 80860ms
Building F from its roots took 56340ms
Computing 1/F took 22900ms
Initializing table of differences for G took 680ms
Computing roots of G took 70780ms
Building G from its roots took 56920ms
Computing roots of G took 70770ms
Building G from its roots took 56920ms
Computing G * H took 11980ms
Reducing  G * H mod F took 12260ms
Computing roots of G took 70770ms
Building G from its roots took 56750ms
Computing G * H took 11960ms
Reducing  G * H mod F took 12300ms
Computing polyeval(F,G) took 105690ms
Computing product of all F(g_i) took 390ms
Step 2 took 706760ms
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
20.04h  2.74d   10.24d  42.89d  198.11d 2.73y   14.99y  87.67y  546.77y 3624y

Last fiddled with by Syd on 2011-02-15 at 00:04 Reason: typo
Syd is offline   Reply With Quote
Old 2011-02-15, 09:08   #4
Syd
 
Syd's Avatar
 
Sep 2008
Krefeld, Germany

2·5·23 Posts
Default

The same with "-base2 1822":

P4, 2Ghz:
Step 1 took 4370690ms


Phenom 2, 3,6Ghz:
Step 1 took 4584750ms
Step 2 took 1073260ms

Core 2, 2,66Ghz:
Step 1 took 8830560ms
Step 2 took 1788570ms
Syd is offline   Reply With Quote
Old 2011-02-15, 10:17   #5
unconnected
 
unconnected's Avatar
 
May 2009
Russia, Moscow

23·313 Posts
Default

Seems that ecm is much faster without '-base2' option.

Last fiddled with by unconnected on 2011-02-15 at 10:18
unconnected is online now   Reply With Quote
Old 2011-02-16, 13:03   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by unconnected View Post
Seems that ecm is much faster without '-base2' option.
Thanks. This is VERY useful information.
R.D. Silverman is offline   Reply With Quote
Old 2011-02-16, 13:30   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46408 Posts
Default

The algebraic factor is less than half the size of the full 2^1822-1. The -base2 option forces arithmetic modulo 2^1822-1. It's not very surprising that working on a number of half the size is faster, even if that means a generic modulo reduction.
akruppa is offline   Reply With Quote
Old 2011-02-17, 14:16   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default "Wish List"

A useful feature (at least to me) would be to provide an input
to GMP-ECM that places a bound on CPU time.

I'd like to be able to (say) run for 12 hours, save a checkpnt file,
then quit.

Failing that, is there any way for one Windows process to get the

(1) PID of another process by looking up the NAME in some system process table?
(2) Extract the CPU time associated with that PID?
(3) then essentially do a kill -9 on the PID???

It is easy to do in Unix. But Windows does not have the same fine-grained
process control as Unix. (or maybe it does and I am ignorant)
R.D. Silverman is offline   Reply With Quote
Old 2011-02-17, 14:40   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

If you're in a position to compile, then you can install a signal handler and add code like:
Code:
#ifdef WIN32
DWORD WINAPI countdown_thread(LPVOID pminutes) {
	DWORD minutes = *(DWORD *)pminutes;

	if (minutes > 0x7fffffff / 60000)
		minutes = 0;            /* infinite */

	Sleep(minutes * 60000);
	raise(SIGINT);
	return 0;
}

#else
void *countdown_thread(void *pminutes) {
	uint32 minutes = *(uint32 *)pminutes;

	if (minutes > 0xffffffff / 60)
		minutes = 0xffffffff / 60;   /* infinite */

	sleep(minutes * 60);
	raise(SIGINT);
	return NULL;
}
#endif
and call with
Code:
	if (deadline) {
#if defined(WIN32) || defined(_WIN64)
		DWORD thread_id;
		CreateThread(NULL, 0, countdown_thread, 
				&deadline, 0, &thread_id);
#else
		pthread_t thread_id;
		pthread_create(&thread_id, NULL, 
				countdown_thread, &deadline);
#endif
	}
Of course, to shutdown gracefully you'd need to periodically check if a signal was raised, otherwise if a checkpoint is written periodically then the timer thread can just call exit().

It would surprise me if the windows task scheduler could not be made to do something like this...
jasonp is offline   Reply With Quote
Old 2011-02-17, 14:57   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by jasonp View Post
If you're in a position to compile, then you can install a signal handler and add code like:
Code:
#ifdef WIN32
DWORD WINAPI countdown_thread(LPVOID pminutes) {
	DWORD minutes = *(DWORD *)pminutes;

	if (minutes > 0x7fffffff / 60000)
		minutes = 0;            /* infinite */

	Sleep(minutes * 60000);
	raise(SIGINT);
	return 0;
}

#else
void *countdown_thread(void *pminutes) {
	uint32 minutes = *(uint32 *)pminutes;

	if (minutes > 0xffffffff / 60)
		minutes = 0xffffffff / 60;   /* infinite */

	sleep(minutes * 60);
	raise(SIGINT);
	return NULL;
}
#endif
and call with
Code:
	if (deadline) {
#if defined(WIN32) || defined(_WIN64)
		DWORD thread_id;
		CreateThread(NULL, 0, countdown_thread, 
				&deadline, 0, &thread_id);
#else
		pthread_t thread_id;
		pthread_create(&thread_id, NULL, 
				countdown_thread, &deadline);
#endif
	}
Of course, to shutdown gracefully you'd need to periodically check if a signal was raised, otherwise if a checkpoint is written periodically then the timer thread can just call exit().

It would surprise me if the windows task scheduler could not be made to do something like this...
I've tried to get the task scheduler to do it. It does not (seem to) work very
well. Even when I set a max time of 12 hours, I have seen it fail to
halt a process that has run for longer than 12 hours.....
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
laptop victorvicentim Information & Answers 2 2009-09-01 00:20
Best Laptop ever? hhh Hardware 5 2007-02-12 20:58
$100 laptop paulunderwood Hardware 3 2005-11-24 19:35
laptop 24/7??? OmbooHankvald Hardware 16 2005-11-08 15:14
Laptop CPU ndpowell Hardware 1 2005-07-07 21:10

All times are UTC. The time now is 11:53.

Wed Nov 25 11:53:19 UTC 2020 up 76 days, 9:04, 4 users, load averages: 1.15, 1.40, 1.44

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