mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-03-15, 00:28   #34
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

135210 Posts
Default

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 is offline   Reply With Quote
Old 2010-03-15, 15:19   #35
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·132 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2010-03-15, 15:46   #36
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·859 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2010-03-15, 16:40   #37
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·132 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2010-03-15, 16:45   #38
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2010-03-15, 18:06   #39
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101010010002 Posts
Default

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 is offline   Reply With Quote
Old 2010-03-15, 20:29   #40
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54816 Posts
Default

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?
alpertron is offline   Reply With Quote
Old 2010-03-15, 20:52   #41
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

65548 Posts
Default

Quote:
Originally Posted by alpertron View Post
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 is offline   Reply With Quote
Old 2010-03-16, 02:21   #42
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
bsquared is offline   Reply With Quote
Old 2010-03-16, 03:02   #43
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·132 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2010-03-16, 03:09   #44
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 15:55.

Fri May 7 15:55:20 UTC 2021 up 29 days, 10:36, 1 user, load averages: 4.53, 4.09, 4.16

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