Prime Factor Coding Challenge

[BruceAmmons]

I just received a submission from Benjamin Buhrow which comes in at a nice 2429 msec.  He tells me it is nice and robust and will handle any 16 digit number you can throw at it.

Watch out Franz, they are coming after you!!!

Bruce

[chilly_charly]

I must confess that I'm stuck. I have been trying (although not full time ;)) to develop something along Pollard's Rho method but my vis give really poor results (take minutes before finding the primes for the last test number :().  I think I'm missing something probably obvious in the method. Unless I find somebody to discuss this issue, that's the end of the road for me...

[alkazaa]

---

@chilly charly wrote:
.... I have been trying (although not full time ;)) to develop something along Pollard's Rho method ....

---

Hi CC,

I also started with Pollard's Rho (símply because it's the first one after 'trial division' treated under 'integer factorization' in wikipedia). My first coding attempt ended in producing 80% correct and 20% incorrect answers within a few seconds runtime. So the code was more or less correct, but probably some cases of overflow or similar were not considered. Before I continued to dive into the code to find out where it went wrong I googled a bit more for alternatives. All the ones mentioned in the wikipedia article seemed even more complicated then Pollard's rho, especially the Elliptic Curve Method (ECM), which seems to be considered the fastest at least for very big numbers, say 128 bits and more.

I stumbled then across an algorithm which was described as reasonably fast and had the big advantage that for an n-bit number it required in most parts of the code only (n/2)-bit precision. It seemed perfectly matched to Bruce's test numbers, in fact so perfect that I thought Bruce had exactly this algorithm in mind when he made up the numbers. In addition to allowing I32 arithmetic it also has a very simple code which turned out easy to debug. And debugging was indeed necessary since I started out with plagiarizing some C- and pseudocode fragments which turned out to be either incorrect or adapted to special cases. I ended up with rewriting the code from scratch, using no code fragments from other languages (which was healthy for the readability of the LV code, BTW).

For the special set of numbers that Bruce provided the method (it's due to a guy named Shanks and has the unpronounceable acronym SQUFOF, which stands for SQUare FOrm Factorization) might well be the fastest possible, but it is definitely the easiest to code IMO.

Would be nice to see an ECM implemented in LV, or to see how fast SQUFOF, when implemented in C, would do the job.

-Franz

[shoneill]

Indeed the Squares in the square form factorization (although I'm not familiar with the actual method) seems quite important.

Other methods including the quadratic sieve and the number field algorithm are all more or less based on Fermat's little theorem in being able to facorize the difference between two squares.

I have also come to the conclusion that adapting C-code (which in the case of factorization seems to have way more code for the purposes of optimization than anything else really) is probably counter-productive.  I've also abandoned this, and have atarted writing one from scratch.  Unfortunately, I needed quite a while to grasp exactly how it works.  Not quite finished yet, but it seems to beat my old version hands down.  Not sure it'll match the 139 msec, but once it's up and running I can starting tweaking.

Shane.

PS If my post sounds like I know what I'm talking about in the area of factorizing primes, It's pnly what I've learned since the beginning of the challenge.  Darn it Bruce, you've made me learn something 😉

Message Edited by shoneill on 11-02-2005 04:10 PM

[bsquared]

---

fahlers wrote:

I also started with Pollard's Rho (símply because it's the first one after 'trial division' treated under 'integer factorization' in wikipedia). My first coding attempt ended in producing 80% correct and 20% incorrect answers...

---

I too started out implementing pollard's rho. It is slower and gets things wrong i think because the method overflows double's digits of precision. specifically, you can't take y*y mod n when y is 16 digits long without losing some accuracy in y. I'd love to hear about ways around this without resorting to arbitrary precision methods. which, incidently, is what i actually did in order to make things work and get the time Bruce posted yesterday.  Pollard's method is pretty robust for N's of 16 digits.  running it for 1000 iterations or so with several different random functions should find any factor of 8 digits.  note that i haven't proved this, and since it is a probablistic algorithm, might fail for some N.  Also, it will fail if the input number is already prime.  Most of the strong and fast primalty checking routines that i know of also require extended precision tools.

---

fahlers wrote:

Would be nice to see an ECM implemented in LV, or to see how fast SQUFOF, when implemented in C, would do the job...

---

I agree, but i doubt that an ECM method would be faster than SQUFOF for this challenge because of the arbitrary precision necessary and other calculation overhead.  I've played with this method some in C (doesn't work yet).  the things i've read say that it is most useful for factoring numbers greater than those accessible to Pollard's Rho, but less than those that would require a quadratic or number field sieve, say numbers with between 15 and 40 digits or so.  My pollard routine in C together with small prime trial division clocks in at about 350ms for these challenge numbers, compared to 1.5sec for my LV routines (both on my 3.8GHz desktop).  I don't have a SQUFOF implemented in C so can't compare anything yet.

- Ben

[Ben]

"It's pnly what I've learned since the beginning of the challenge.  Darn it Bruce, you've made me learn something "

Don't you hate it when that happens!

Although I have learned more about primes than I ever thought I wanted to learn, I have stayed with the most simple approaches and have hammered away at devloping LV code to implement these simplistic approaches. I do not know if any of my version will be able to finish in less than the 5 minute limit, but I plan to submit them just as examples of LV code optimization. I feel that I have already won because of what I have learned in making my code run faster.

The good news is I can still cheer for "ben" to win.

Ben

Warning:

I have a sieve type algorithm that will find all primes less than 100M in about 7.5 seconds. That is about a 60X improvement over the "trial divide" version I posted earlier.

[bsquared]

---

Ben wrote:

I have a sieve type algorithm that will find all primes less than 100M in about 7.5 seconds. That is about a 60X improvement over the "trial divide" version I posted earlier.

---

Bruce said he was still interested in seeing fast methods for generating primes.  100M in 7.5sec is pretty impressive - i'm not even going to try to touch that.

p.s.  thanks for the encourgement

-ben.

[BruceAmmons]

Always happy when people are learning things, even when they try not to.

Due to popular demand, one of the categories will be routines that can factor ANY 16 digit DBL or indicate that it is a prime number.  The official rules for the competition stay the same, but for this category I will use a different number generator to test the additional criteria.  Probably just generate random 16 digit numbers and ask for the factors.  Obviously, the output of these will have to be DBL instead of I32.

Didn't realize Ben and bsquared were the same person.  Guess I just wasn't paying attention.

On a side note:  So far, this challenge has been really fun to supervise.  I am really looking forward to the final results.  If anybody has ideas for another challenge, please email them to me.

Bruce

[Ben]

"Didn't realize Ben and bsquared were the same person. "

We are NOT!

He knows something about math. I just talk a lot!

Besides, if I and he were the same person, my star rating would be a lot higher.

Ben

[bsquared]

Hey, you're the one with the "labview champion" tag.  i'm just a wannabe with too much spare time

- ben, a.k.a bsquared.