20100315, 00:28  #34 
Aug 2002
Buenos Aires, Argentina
1352_{10} 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. 
20100315, 15:19  #35 
Aug 2002
Buenos Aires, Argentina
2^{3}·13^{2} 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^711 1m 10s 2m 29.3s 10^79+5923 6m 47s 17m 20.8s Last fiddled with by alpertron on 20100315 at 15:20 
20100315, 15:46  #36 
"Ben"
Feb 2007
2^{2}·859 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:
yafu1.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 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 20100315 at 15:48 Reason: wrong numbers 
20100315, 16:40  #37 
Aug 2002
Buenos Aires, Argentina
2^{3}·13^{2} 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. 
20100315, 16:45  #38 
"Ben"
Feb 2007
2^{2}×859 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.

20100315, 18:06  #39 
Aug 2002
Buenos Aires, Argentina
10101001000_{2} Posts 
Since I do not know the value of the C75, I multiplied by 2 the prime base size and then I redid 10^711 and 10^79+5923.
For 10^711 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. 
20100315, 20:29  #40 
Aug 2002
Buenos Aires, Argentina
548_{16} 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?

20100315, 20:52  #41 
"Ben"
Feb 2007
6554_{8} Posts 
Yeah, it would be interesting... If you can supply linux or windows executables, I'd be happy to test them.

20100316, 02:21  #42  
"Ben"
Feb 2007
2^{2}×859 Posts 
Quote:
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 

20100316, 03:02  #43 
Aug 2002
Buenos Aires, Argentina
2^{3}·13^{2} 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 
20100316, 03:09  #44 
"Ben"
Feb 2007
2^{2}×859 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 fnoboundscheck and fnostorecheck might help the speed. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java applet alternative  a1call  Programming  19  20191108 22:31 
New online applet for factorization  ET_  Lone Mersenne Hunters  69  20140601 17:34 
A strange applet:  3.14159  Miscellaneous Math  7  20100601 01:29 
Faster factorization applet  alpertron  Factoring  14  20060101 04:00 
Binomial Expansion Applet  jinydu  Lounge  2  20040505 08:33 