20061215, 15:44  #12 
Nov 2005
3^{2}×11 Posts 
@ jasonp Stopping to sieve with lower primes helps a lot. Hashing the factors is slows down my app by factor 2. How do you store the factors efficient?
I got the best results by: Sieving : Stopping to sieve with lower primes. Factoring:  Resieving up to a bound above the stop_sieving bound.  Trial division a) If the remaining value is no long calculate dividability by its quadratic roots b) If the remaining value is a long check dividability by '%' (Java) To Point a) For a p of the FB we have already calculated the (two) quadratic roots t^2 = n mod p for sieving. If q = t mod p we know that p divides q. This can be calculated fast. For 60 Bit N's I stop sieving with the 75th Factor (threshold is 2.5 * maximal Factor of FB). The bound to switch to Trial division is the 400th factor. Due to the range check of the VM in Java (which slows down array operations) this way to do it might not be the best way for C. 
20061215, 18:34  #13  
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
Quote:
jasonp 

20061217, 15:51  #14 
Nov 2005
3^{2}×11 Posts 
Oh sorry I mean 59 Digits (195 bits).

20061217, 22:52  #15 
Tribal Bullet
Oct 2004
DCE_{16} Posts 
Rereading your post, I see I didn't answer your questions. Using hashtables in msieve becomes more efficient when the inuts are 6570 digits and up; in that case the factor base becomes too large to iterate through efficiently, unless the entire sieve interval is handled all at once; but if the sieve interval is too large then you get too many cache misses applying updates to sieve values. The use of hashtables is a good compromise: you iterate only once through the factor base, but get the most reuse applying the updates to the sieve interval. I think the cutoff is 4000 factor base primes before it becomes worthwhile to switch over to using hashtables. That number will be machindependent; larger cache sizes mean the cutoff should become larger, since there is more overhead in the hashtable method.
Each hashtable entry is 8 bytes, and includes room for the prime to use, its log, and the offset into a sieve block. That leaves one byte I don't know what to do with. You can get away with 4 bytes per entry if you don't care which prime is associated with a given hashtable entry, and that can potetially make things much faster for very large sieving jobs, where the overhead of trial factoring is very low since smooth sieve values are very rare. I've been meaning to add that improvement, since old experiments show it makes sieving much faster (but slows down trial fatoring greatly). Using hashtables does mean the amount of memory used in the sieve is much higher than it has to be, but 50MB for a working set is not a big deal nowadays, and the speedup is just huge for the biggest jobs. jasonp 
20061217, 23:58  #16 
Nov 2005
1100011_{2} Posts 
Thanks for the Answers. I just downloaded and run your code on my Examples. Your Application is ~30 times faster then my Java Application.
Excellent job jasonp. 
20061218, 02:00  #17  
Tribal Bullet
Oct 2004
2·3·19·31 Posts 
Quote:
You may want to examine Dario's factoring applet for ideas on increasing the performance; if memory serves the performance difference between his code and mine is only a factor of about 3. jasonp 

20061218, 08:55  #18 
Nov 2005
3^{2}·11 Posts 
Only Factor 3 between Dario Alperns Applet and your c Application?
My application is nearly as fast as his applet, for moderate inputs around 60 digits. A trial run on 2400444429969727335088295023919557813543824570366289631639 (58 digits) needs 3m48sec at Dario Alperns Applet 3m32sec at my Application 6 sec at msieve 1.07 My application is not using the lagre Primes at the moment, and uses only one Polynomial for one 'a' (MPQS). Currently I do the Linear Algebra Step by Gaussian Elimination, which causes Problems for big Inputs. I have to switch to Lanczos. 
20061218, 14:11  #19  
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
Quote:
jasonp 

20061218, 14:40  #20 
Aug 2002
Buenos Aires, Argentina
2·11·61 Posts 
The timing cited by ThiloHarich is related to the extremely slow performance of Sun JVM for integer arithmetic. For instance the old Microsoft JVM was several times faster than Sun Java VM. I also tried IBM Java VM which also much faster than Sun JVM.
I think that jasonp was benchmarking an old version of msieve against my applet using Microsoft JVM. Since C programs do not need the virtual machine, they do not exhibit this problem. 
20061219, 09:08  #21 
Nov 2005
1100011_{2} Posts 
Hi Dario,
I am not very familar with applets. Can you start an applet with start options? The server option enables Hotspot, which helps a lot. The sieving routine can be replaced with the compiled code. This nearly halfes the execution Time. My code (and your applet) runs under JDK 1.5. Under JDK 1.6 my app runs much slower. I have not tried it under 1.4 (it is JDK 1.5 code style). Here were my start options: server Xmx500M Xms500m XX:+UseParallelGC XX:ParallelGCThreads=1 Factor 30 is realy a lot, i have to run other examples. 
20061219, 13:41  #22 
Aug 2002
Buenos Aires, Argentina
2·11·61 Posts 
I upgraded the Java Runtime Environment (JRE) to 1.5.0_10. It appears that the applet is extremely slow with this version. Unluckily I don't know how to go back to the version 1.5.0_06. Of course the versions 1.4.2_xx are faster than 1.5.0_xx
It is like the CPU manufacturers are paying Sun to make the JRE slower so they can sell the latest microprocessors. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 