mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-12-15, 15:44   #12
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

@ 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.
ThiloHarich is offline   Reply With Quote
Old 2006-12-15, 18:34   #13
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
@ 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?

...

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.
I don't have a good grasp of what's optimal for inputs that are so small. I've certainly implemented tiny QS routines designed to handle them, but the bottlenecks are in different places compared to larger factorizations. You are correct that resieving is a big help, at least that's what my experiments show, but once the input size exceeds a pretty small value (128 bits?) there just aren't enough promising sieve values to make resieving worthwhile.

jasonp
jasonp is offline   Reply With Quote
Old 2006-12-17, 15:51   #14
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

Oh sorry I mean 59 Digits (195 bits).
ThiloHarich is offline   Reply With Quote
Old 2006-12-17, 22:52   #15
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DCE16 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Oh sorry I mean 59 Digits (195 bits).
Rereading your post, I see I didn't answer your questions. Using hashtables in msieve becomes more efficient when the inuts are 65-70 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 machin-dependent; 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
jasonp is offline   Reply With Quote
Old 2006-12-17, 23:58   #16
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11000112 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2006-12-18, 02:00   #17
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
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.
My pleasure

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
jasonp is offline   Reply With Quote
Old 2006-12-18, 08:55   #18
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32·11 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2006-12-18, 14:11   #19
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Only Factor 3 between Dario Alperns Applet and your c Application?

3m48sec at Dario Alperns Applet
3m32sec at my Application
6 sec at msieve 1.07
Oh...never mind. I didn't remember other people's experience correctly. A factor of 30 difference between Java and C is really a lot (many of msieve's tricks are turned off for inputs of that size)

jasonp
jasonp is offline   Reply With Quote
Old 2006-12-18, 14:40   #20
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·11·61 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-12-19, 09:08   #21
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11000112 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2006-12-19, 13:41   #22
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·11·61 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 08:09.

Mon Mar 1 08:09:00 UTC 2021 up 88 days, 4:20, 0 users, load averages: 2.02, 1.65, 1.49

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.