mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-12-21, 15:54   #34
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Why is msieve so dammed fast?
Practice practice practice :)

jasonp
jasonp is offline   Reply With Quote
Old 2006-12-21, 21:19   #35
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Here were my results based on my Factoring Algorithm:
Thanks for the comparisons, Thilo. The performance increase for JDK 1.6 without "-server" is surprising. I so far found no reason for it - but your postings on the java.sun.com forum.

What where the absolute runtimes of your benchmark? In the order of minutes?
Mystwalker is offline   Reply With Quote
Old 2006-12-22, 09:51   #36
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

1458 Posts
Default

They run only for about 10 sec. I run each test 3 times and took the best value.
I made longer runs for the -server option on JDK 1.5 and 1.6 to manifest the difference. It is there.

I only count the sieving phase, not the setup of the Factorbase (since the sieving phase dominates the running time for MPQS).
The IBM JRE has an interesting phenomenon. After the second polynom the performance goes down darmatically (factor 10) for one or two polynomials, then the performance comes back again. In the second or third run it performed well from the beginning. The Sun JRE has no such peeks.
I used System.currentTimeMillis () which is not very pecise. Since JDK 1.5 there is the more precise System.nanoTime().

How much faster is the SIQS compared with the MPQS?
I got a factor of 2 in my mind but hope for a bigger value.
In my tests the large prime variant gives a factor of 2 (simply since there were nearly as much large congruencies as normal congruencies).
So I can hope to improve Performance only by a factor of 4. So I am still far away from mseive
ThiloHarich is offline   Reply With Quote
Old 2006-12-22, 13:25   #37
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17·79 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
So I can hope to improve Performance only by a factor of 4. So I am still far away from mseive
Java experiences very high penalties for array access because it has the check whether the index is inside bounds. This does not happen on programs written in C.

If you are not writing applets, Java is a bad choice for numerical programs.
alpertron is offline   Reply With Quote
Old 2006-12-22, 13:33   #38
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17×79 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
The IBM JRE has an interesting phenomenon. After the second polynom the performance goes down darmatically (factor 10) for one or two polynomials, then the performance comes back again. In the second or third run it performed well from the beginning. The Sun JRE has no such peeks.
This is not strange at all. The Just in Time (JIT) compiler detects that it is running repeated code and starts compiling (slowing down code execution), then it works OK. It is possible that the Virtual Machine caches somewhere on your computer the compiled code so the second time your program starts, the delay is not noticeable.

You should run your programs for at least two minutes in order to have a better benchmark.
alpertron is offline   Reply With Quote
Old 2006-12-23, 19:24   #39
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

At http://dada.perl.it/shootout/sieve.html
there is a factor of 5 between C and JAVA on the Sieve of Erathostenes.
This should be due to the range check in JAVA, as you already said.

With JNI (Java Native Interface) you can call C or C++ from Java, in order to do the sieving. But because of the different management of (array) Objects this seems to be no good solution.
ThiloHarich is offline   Reply With Quote
Old 2006-12-23, 21:21   #40
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
With JNI (Java Native Interface) you can call C or C++ from Java, in order to do the sieving. But because of the different management of (array) Objects this seems to be no good solution.
In addition, you have the call overhead. Unless the call frequency is very low, this should negate (or at least reduce) any performance improvements.

As stated earlier, you could try gcj with the option -fno-bounds-check.
I haven't tested it yet, though.
Mystwalker is offline   Reply With Quote
Old 2006-12-26, 18:37   #41
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

I am working under windows. I hate all this linux gcc stuff. I can not get it running. Now I am downloading the minGW stuff. This is why i like java. It works.
ThiloHarich is offline   Reply With Quote
Old 2006-12-26, 21:54   #42
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

After fighting with gcj I did a test with the sieve of Erathostenes.
GCJ with --no-bounds-check has the same performance as JDK 1.5_08 -server.
So java do not seems to be a good solution for this kind of Algorithms.
ThiloHarich is offline   Reply With Quote
Old 2006-12-29, 15:53   #43
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

Back to the sieving.
I think it is not necessary to sieve with all primes of the factorbase.
As stated earlier we can skip sieving with the small primes.

When we have a sieving Intervall n*log n and a highest prime n*log n
sieving with the log (n) smallest prime has effort n*log n / (log n * log log (n)) = n / log log (n) sieving with the log (n) smallest primes has at least effort n * log (n)/ log log (n).

Sieving with (1-epsilon) * n highest of the n primes we have effort:
n*log n / (epsilon * n log (espilon * n)) = (1/eplison * (1+epsilon)) per prime. which is (1+1/eplison) * (1-epsilon)* n ~ 1/epsilon * n.

So sieving with the small primes is very expensive (i know the calculation above is very raw).

I stop sieving with the 30th smallest prime for factorBase Size 35576 (MPQS 65 Digit Input). And check the divideability of the smooth q(x) by checking if q(x) mod p is one of the values we tried to sieve with for prime p. I increased the smooth threshold from 1.1 * max_prime to 1.9 * max_prime. Since we have to check ~10 pseudo smooth q(x) to get one real smooth, this is no big extra effort.
@ Jasonp This is some kind of hashing with the prime we sieve with, if you want to see it in this way.

My idea is to start with normal sieving for bigger primes. After this phase we have collected pseudo smooth q(x) with many primes.
These were very sparse (compared to the sieve interval). Then we try to find the divisors of these q (x) for the remaining primes.

The question is: "Is there a clever way to find the small divisors?"
Is there a way to find them without checking every of the pseudo smooth values with every prime.
Can we create an efficient function which decides if the prime p divides one (or more precisely which of the) pseudo smooth q (x)?

We might calculate the remainder of q(x) after dividing out the bigger primes and start a Factorization.
Is there a fast algorithm for dividability with small primes?

@ alpertron do you factorize the small primes with the ECM?

Last fiddled with by ThiloHarich on 2006-12-29 at 16:03
ThiloHarich is offline   Reply With Quote
Old 2006-12-29, 16:17   #44
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

There is something I've been wondering about for a while: if you don't sieve with small primes, do you still sieve with large enough powers of small primes? I suppose you should, if sieving with, say, 127 is worthwhile, so should be sieving with 128.

Alex
akruppa 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 06:48.

Mon Mar 8 06:48:18 UTC 2021 up 95 days, 2:59, 0 users, load averages: 2.62, 2.63, 2.40

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.