mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-11-02, 14:33   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default Understandable QS java Implementation

Hi I’am a novice and I’have got a few novice questions:

1) Is there a java Implementation which is understandable?
I know http://www.alpertron.com.ar/ECM.HTM and a less advanced try http://www-fs.informatik.uni-tuebing...r/QuadAlg.html. These Implementations consist basically of one big static method. I wrote an OO-Implementation of QS. So the implementation of LPQS was just overriding a few methods. Now I want to switch to SIQS. But I’m still trying to understand it.

2) I wrote a variant which stops after sieving with all factors except the last k (say 35). Then only if the length of the remaining y (after the subtracting of factor length) is greater then a certain threshold (the QS threshold + k +3), sieving with the remaining factors is done. After sieving with a factor the length will be checked again (k has changed). In http://www.math.dartmouth.edu/~carlp/PDF/paper52.pdf a similar idea is mentioned.
In http://aux.planetmath.org/files/papers/235/mpqs.ps it is written that this idea only saves 20% Time. In my Implementation it saves 50% at 30 Digit numbers, while LPQS only saves 30%. I know that DLPQS will be fast only for very huge N. Does LPQS reach its advantages of saving over 50% only at bigger numbers?
ThiloHarich is offline   Reply With Quote
Old 2005-11-02, 14:57   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by ThiloHarich
1) Is there a java Implementation which is understandable?
I don't know about Java, but a well-documented tiny QS implementation in C can be found at www.boo.net/~jasonp/ksieve001.tar.gz. It's an SIQS implementation in a single file.

Quote:
Originally Posted by ThiloHarich
I know that DLPQS will be fast only for very huge N. Does LPQS reach its advantages of saving over 50% only at bigger numbers?
The crossover point for two large primes being more efficient is about 85 digits for msieve; people here don't consider that huge at all :)

The savings you get from LPQS will depend heavily on parameter choices in your implementation. For msieve the 50% figure happens at ~70 digits; for smaller sizes 40% faster is common. The tiny QS implementation above uses parameters that save 30-45% when using large primes for inputs of ~116 bits

jasonp
jasonp is offline   Reply With Quote
Old 2005-11-02, 15:31   #3
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11001012 Posts
Default

Thank you jasonp,

I just downloaded the sources.

In the papers I read so far I havent found how much faster the SIQS/MPQS is compared to the standard QS. But since the MPQS very often hits a smooth number compared with the standard QS it might be more then a linear factor. Are there any resluts?
ThiloHarich is offline   Reply With Quote
Old 2005-11-02, 17:25   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110101112 Posts
Default

Quote:
Originally Posted by ThiloHarich
Thank you jasonp,

I just downloaded the sources.

In the papers I read so far I havent found how much faster the SIQS/MPQS is compared to the standard QS. But since the MPQS very often hits a smooth number compared with the standard QS it might be more then a linear factor.
It's typically a factor of 6x - 10x faster. Even better, the relations accumulate at a constant rate instead of dropping off over time.

If performance is a concern you basically have to use multiple polynomials.

jasonp
jasonp is offline   Reply With Quote
Old 2005-11-02, 17:40   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by ThiloHarich
Thank you jasonp,

I just downloaded the sources.

In the papers I read so far I havent found how much faster the SIQS/MPQS is compared to the standard QS. But since the MPQS very often hits a smooth number compared with the standard QS it might be more then a linear factor. Are there any resluts?

My 1987 paper in Math. Comp. "The Multiple Polynomial Quadratic Sieve"
will give a novice all the information needed to implement the single large
prime version of the algorithm. The paper does require knowing a little
bit of elementary number theory (e.g. you need to know what a quadratic
residue is)

I also gives a comparison to the single polynomial version.

Mathematics of Computation is widely distributed. Any college library will
carry it.
R.D. Silverman is offline   Reply With Quote
Old 2005-11-03, 07:38   #6
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

I left the town were i have been studying. I only got bad access to paper libraies.
Is there still no proof on the deterministic runtime of QS?
ThiloHarich is offline   Reply With Quote
Old 2005-11-03, 11:23   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by ThiloHarich
I left the town were i have been studying. I only got bad access to paper libraies.
Is there still no proof on the deterministic runtime of QS?
There is still one unproven assumption: The norms that arise from
the range of a quadratic polynomial have the same statistical smoothness
properties as random integers.

The same obstacle applies (although for higher degree polynomials) for NFS.
R.D. Silverman is offline   Reply With Quote
Old 2005-11-03, 11:36   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101010101102 Posts
Default

In my factoring applet the #1 design objective was speed. All other features were secondary, including program readability if that was against running time.

That's why the applet is not OOP-oriented. In this way no objects have to be created and destroyed, which takes a lot of time.

Of course you can do an OOP-oriented factoring applet, but I think that it will run two or three times slower than a program that uses arrays to store data.

OOP in Java is great for serving Web pages but totally wrong for this kind of programs.
alpertron is offline   Reply With Quote
Old 2005-11-03, 11:44   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by alpertron
In my factoring applet the #1 design objective was speed. All other features were secondary, including program readability if that was against running time.

That's why the applet is not OOP-oriented. In this way no objects have to be created and destroyed, which takes a lot of time.

Of course you can do an OOP-oriented factoring applet, but I think that it will run two or three times slower than a program that uses arrays to store data.

OOP in Java is great for serving Web pages but totally wrong for this kind of programs.

AMEN!!!!
R.D. Silverman is offline   Reply With Quote
Old 2005-11-03, 13:12   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

47×229 Posts
Default

Quote:
Originally Posted by alpertron
OOP in Java is great for serving Web pages but totally wrong for this kind of programs.
"Totally wrong" is stating it a little too strongly in my opinion.

I can think of two reasons for writing an OOP implementation of MPQS. The first is if you are trying to learn how to write non-trivial OOP programs and need to code some algorithm for practice. Almost invariably it's better for a student to code something they find personally interesting than some arbitrary exercise from a book.

The second is if you intend your program to be used for pedagogical purposes. As alpertron says, production code is frequently optimised to the point of incomprehensibility. A clearly written though not particularly fast reference implementation of anything non-trivial is of great value.

Remember the original post which started thus:
Quote:
Originally Posted by ThiloHarich
Hi I’am a novice and I’have got a few novice questions:

1) Is there a java Implementation which is understandable?
That said, I strongly agree that with current OOP languages and compiler technology, OOP is a seriously bad idea for production code.


Paul
xilman is offline   Reply With Quote
Old 2005-11-03, 13:21   #11
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2028 Posts
Default

Quote:
Originally Posted by xilman

That said, I strongly agree that with current OOP languages and compiler technology, OOP is a seriously bad idea for production code.

Paul
In Java maybe, but well-written C++ code can be just as fast as C, while still using OOP. Of course, it's still possible to argue about what you mean by OOP
:-)

Chris
Chris Card is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PSIQS java package discussion Till Factoring 74 2021-07-24 15:19
Java applet alternative a1call Programming 19 2019-11-08 22:31
Simple Atkin sieve java example lucaf Computer Science & Computational Number Theory 8 2017-10-06 20:56
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Java based program GordonBM Information & Answers 11 2012-04-24 08:27

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


Tue Jul 27 18:09:35 UTC 2021 up 4 days, 12:38, 0 users, load averages: 1.67, 1.92, 1.97

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.