New feature in my ECM applet - Page 4

alpertron · 2010-03-15, 00:28

Yesterday I uploaded a new version of the factorization applet which is 10% to 15% faster on SIQS depending on the number to be factored.

Now the code processes two polynomials simultaneously. In the previous version the sieve was an array of bytes, but now it is an array of shorts. So now the applet perform half as many bit comparisons as the previous version. It also permits some optimizations in the sieve stage.

Please let me know whether the applet works correctly.

alpertron · 2010-03-15, 15:19

This is a benchmark of the applet against the fastest SIQS factoring program on a Core 2 Duo 1.86 GHz:

Code:

               YAFU 1.17    Applet 03/13/2010
10^59+213           8s             15.2s
10^71-1         1m 10s          2m 29.3s
10^79+5923      6m 47s         17m 20.8s

bsquared · 2010-03-15, 15:46

I've tried it out on my benchmark suite (a series of random RSA numbers), here are the results on my p3 based Xeon @ 3.4 GHz (timings in seconds):

Code:

	yafu-1.17	alpertron 3/13/10
c50	1.4	        2.2
c55	4.0	        6.7
c60	14.0	        21
c65	38.2	        57.9
c70	87	        140
c75	289	        547
c80	589	        1326

It seems to be pretty fast but I don't have a comparison to the previous version on my machine so I can't judge the speedup.

Also one thing I noticed is that your SIQS routine uses a significantly smaller factor base on larger numbers. For instance the c75 uses 12622 primes while YAFU uses 26425 primes. Is this something you have optimized for your code? YAFU, at least, prefers a larger factor base - forcing it to use 12622 primes makes it run 5x slower.

alpertron · 2010-03-15, 16:40

The number of primes in the base were optimal (at least that's what I found several years ago) on an obsolete AMD K6/2 450 MHz.

I will change the size as you suggest above and then I will test the applet.

bsquared · 2010-03-15, 16:45

It took quite a bit of testing to get the factor base bounds optimally determined for YAFU... they may or not be right for your Applet but you're welcome to try them out. They were optimized for a core2 based Xeon system, but seemed to be pretty close for other architectures as well. The lookup table I use is in the function get_params() inside siqs_aux.c.

alpertron · 2010-03-15, 18:06

Since I do not know the value of the C75, I multiplied by 2 the prime base size and then I redid 10^71-1 and 10^79+5923.

For 10^71-1 the SIQS algorithm needed 3m 10s while for 10^79+5923 SIQS was running for 19m 18s. So I will not change the settings. It appears that the interaction with the Java Virtual Machine changes the optimum settings.

alpertron · 2010-03-15, 20:29

It should be interesting to compile the applet to native code using gcj or similar tool, disabling array checks. How the produced executable compares to YAFU?

bsquared · 2010-03-15, 20:52

Quote:

Originally Posted by alpertron

It should be interesting to compile the applet to native code using gcj or similar tool, disabling array checks. How the produced executable compares to YAFU?

Yeah, it would be interesting... If you can supply linux or windows executables, I'd be happy to test them.

bsquared · 2010-03-16, 02:21

Quote:

Originally Posted by bsquared

Yeah, it would be interesting... If you can supply linux or windows executables, I'd be happy to test them.

I had a quick go at this. I was able to produce object files from the 3 source files. But when I went to link them I got an error:

Code:

% gcj expression.o ecm.o Siqs.o -lgij -o ecm
expression.o (.rodata+0x0): multiple definition of 'java resource .dummy'
ecm.o:(.rodata+0x0): first defined here
Siqs.o:(.rodata+0x0): multiple definition of 'java resource .dummy'
ecm.o:(.rodata+0x0): first defined here
collect2: ld returned 1 exit status

A quick google seems to indicate this is a gcj bug. I haven't taken it any further.

alpertron · 2010-03-16, 03:02

I downloaded MinGW which includes gcj version 4.4.0.

Using the command line:

Code:

gcj expression.java ecm.java Siqs.java -lgij -o ecm.exe

I got a executable file whose size is 1098166 bytes, but when I tried to run it, it showed the error C0000005 (which is an access violation) and aborted execution.

bsquared · 2010-03-16, 03:09

What if you give it an explicit entry point using --main ?

I wasn't familiar enough with your code or java in general to try this - I just used the -lgij library suggested in the gcj man pages.

Also, if you get it to work, compiling again with -fno-bounds-check and -fno-store-check might help the speed.

2010-03-15, 15:19	#35
alpertron Aug 2002 Buenos Aires, Argentina 5F3₁₆ Posts	This is a benchmark of the applet against the fastest SIQS factoring program on a Core 2 Duo 1.86 GHz: Code: YAFU 1.17 Applet 03/13/2010 10^59+213 8s 15.2s 10^71-1 1m 10s 2m 29.3s 10^79+5923 6m 47s 17m 20.8s Last fiddled with by alpertron on 2010-03-15 at 15:20

2010-03-15, 15:46	#36
bsquared "Ben" Feb 2007 3·5·251 Posts	I've tried it out on my benchmark suite (a series of random RSA numbers), here are the results on my p3 based Xeon @ 3.4 GHz (timings in seconds): Code: yafu-1.17 alpertron 3/13/10 c50 1.4 2.2 c55 4.0 6.7 c60 14.0 21 c65 38.2 57.9 c70 87 140 c75 289 547 c80 589 1326 It seems to be pretty fast but I don't have a comparison to the previous version on my machine so I can't judge the speedup. Also one thing I noticed is that your SIQS routine uses a significantly smaller factor base on larger numbers. For instance the c75 uses 12622 primes while YAFU uses 26425 primes. Is this something you have optimized for your code? YAFU, at least, prefers a larger factor base - forcing it to use 12622 primes makes it run 5x slower. Last fiddled with by bsquared on 2010-03-15 at 15:48 Reason: wrong numbers

2010-03-16, 03:02	#43
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	I downloaded MinGW which includes gcj version 4.4.0. Using the command line: Code: gcj expression.java ecm.java Siqs.java -lgij -o ecm.exe I got a executable file whose size is 1098166 bytes, but when I tried to run it, it showed the error C0000005 (which is an access violation) and aborted execution.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Java applet alternative	a1call	Programming	19	2019-11-08 22:31
New online applet for factorization	ET_	Lone Mersenne Hunters	69	2014-06-01 17:34
A strange applet:	3.14159	Miscellaneous Math	7	2010-06-01 01:29
Faster factorization applet	alpertron	Factoring	14	2006-01-01 04:00
Binomial Expansion Applet	jinydu	Lounge	2	2004-05-05 08:33

2010-03-15, 00:28	#34
alpertron Aug 2002 Buenos Aires, Argentina 1523₁₀ Posts	Yesterday I uploaded a new version of the factorization applet which is 10% to 15% faster on SIQS depending on the number to be factored. Now the code processes two polynomials simultaneously. In the previous version the sieve was an array of bytes, but now it is an array of shorts. So now the applet perform half as many bit comparisons as the previous version. It also permits some optimizations in the sieve stage. Please let me know whether the applet works correctly.

2010-03-15, 16:40	#37
alpertron Aug 2002 Buenos Aires, Argentina 5F3₁₆ Posts	The number of primes in the base were optimal (at least that's what I found several years ago) on an obsolete AMD K6/2 450 MHz. I will change the size as you suggest above and then I will test the applet.

2010-03-15, 16:45	#38
bsquared "Ben" Feb 2007 3×5×251 Posts	It took quite a bit of testing to get the factor base bounds optimally determined for YAFU... they may or not be right for your Applet but you're welcome to try them out. They were optimized for a core2 based Xeon system, but seemed to be pretty close for other architectures as well. The lookup table I use is in the function get_params() inside siqs_aux.c.

2010-03-15, 18:06	#39
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	Since I do not know the value of the C75, I multiplied by 2 the prime base size and then I redid 10^71-1 and 10^79+5923. For 10^71-1 the SIQS algorithm needed 3m 10s while for 10^79+5923 SIQS was running for 19m 18s. So I will not change the settings. It appears that the interaction with the Java Virtual Machine changes the optimum settings.

2010-03-15, 20:29	#40
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	It should be interesting to compile the applet to native code using gcj or similar tool, disabling array checks. How the produced executable compares to YAFU?

2010-03-16, 03:09	#44
bsquared "Ben" Feb 2007 3×5×251 Posts	What if you give it an explicit entry point using --main ? I wasn't familiar enough with your code or java in general to try this - I just used the -lgij library suggested in the gcj man pages. Also, if you get it to work, compiling again with -fno-bounds-check and -fno-store-check might help the speed.