20061221, 15:54  #34 
Tribal Bullet
Oct 2004
2×3×19×31 Posts 

20061221, 21:19  #35 
Jul 2004
Potsdam, Germany
3·277 Posts 
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? 
20061222, 09:51  #36 
Nov 2005
145_{8} Posts 
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 
20061222, 13:25  #37  
Aug 2002
Buenos Aires, Argentina
17·79 Posts 
Quote:
If you are not writing applets, Java is a bad choice for numerical programs. 

20061222, 13:33  #38  
Aug 2002
Buenos Aires, Argentina
17×79 Posts 
Quote:
You should run your programs for at least two minutes in order to have a better benchmark. 

20061223, 19:24  #39 
Nov 2005
101 Posts 
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. 
20061223, 21:21  #40  
Jul 2004
Potsdam, Germany
3×277 Posts 
Quote:
As stated earlier, you could try gcj with the option fnoboundscheck. I haven't tested it yet, though. 

20061226, 18:37  #41 
Nov 2005
101 Posts 
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.

20061226, 21:54  #42 
Nov 2005
101 Posts 
After fighting with gcj I did a test with the sieve of Erathostenes.
GCJ with noboundscheck 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. 
20061229, 15:53  #43 
Nov 2005
101 Posts 
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 (1epsilon) * 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) * (1epsilon)* 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 20061229 at 16:03 
20061229, 16:17  #44 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 
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 