Prime Factor Coding Challenge

[BruceAmmons]

And the new leader is.... Ben (bsquared) with a time of 84 msec.

Bruce

[shoneill]

Aw man,

The (quite low) possibility of even getting into the same league as these times is kind of draining a bit of my motivation.

I suppose I could still whip up a decent sieve though.

Shane.

PS Congratulations on the outstanding time bben

[bsquared]

---

@Bruce Ammons wrote:

And the new leader is.... Ben (bsquared) with a time of 84 msec.

Bruce

---

Well, I guess Pollard's method (ok, Brent's improvement) isn't the fastest after all.  I had concentrated on it because I had already implemented it in C and knew how it worked fairly well, but couldn't do any better than ~1200ms.  The result above is an algorithmic improvement to something I had considered before and was prompted to return to by Franz .  I don't think I can make Brent's method go any faster - or at least I'm unwilling to invest any more effort in it.  Optimization of this method on the other hand... maybe there's still room for improvement...

For those that are interested, I also implemented this in C.  It ran ~20% faster: 47ms vs. 61ms (on my 3.8GHz P4).  But more could definately be done to make the C code more efficient

- ben.

[shoneill]

A general question.....

We know that the prime generation methods aren't going to be the fastest, but we're still interested in good prime generation routines, right?

How about a prime generation routine which doesn't EXACTLY return a correct list of primes.  I have a fast routine which generates the primes up to 100,000,000, but there are a few "extras" in there.  I guess there are around 100 to 200 "primes" too many.  Is this still submittable as a prime generator?  It makes no real difference in a trial division routine, as the "extras" simply are divided out by other primes, and we end up doing a couple of divisions for nothing.  I reckon the 100 or so wasted divisions (From 5.7 Million primes under 100,000,000) aren't really relevant.

On another aspect, does the prime generator have to really generate the prime numbers (i.e. as I32) or is it allowed to represent them in a different way (U32 as an array of 32 Bits comes to mind).

I'm looking for ways I might be able to compete since my "quadratic sieve" isn't working out too well.  Theoretically it works, but practically is sucks.

Shane.

[BruceAmmons]

I will take anything you think is cool as a submission.  If you have a really fast way to generate the prime numbers with a few extras, that sounds reasonable.  In your code, put comments about why you think your code excels in a particular area (speed, memory usage, efficiency, etc.)  After judging all the entries, I will probably talk about the cool stuff in the different methods.

You can store your prime numbers as a bit table, but you have to be able to retrieve them from the table to do the trial division.  Does that answer your question?

Bruce

[BruceAmmons]

Okay folks, we are getting down to the wire.  This Friday is the deadline for the challenge!!!  Please submit your solutions by midnight Friday.

During this week, I will not be posting any times.  No more results will be posted until I have the final results.

Please remember to put lots of comments in your code so I can figure out what you did.

Thanks,

Bruce

[shoneill]

Well, I have to withdraw from the race (more or less).

I'll probably send my last effort to Bruce today at some time, but I've had no time whatsoever recently to do more work on it.

It's a shame really, because I found the challenge fascinating.  Either way (I seriously doubt I'll be among the leaders - even the Trial division versions) it was a very interesting journey, and I learned quite a lot.

Some time I might finish my Quadratic sieve (In LV 8 with 64-bit integers maybe) and post it either way.  I have it almost finished, but it's unoptimized, and it doesn't really work properly.

Good luck everyone, and may be best algorithm win!  (Or maybe the best implementation of each algorithm?)

Shane.

[Ben]

Similarly for me Shane.

I will document what I have and submit it.

It was fun.

Ben

[shoneill]

OK, I know my version wasn't the fastest, but I think it should have calculated the 1000 numbers by now!

Seriously,  any word on when (or if) the results will be posted?

Bruce?  You still with us?

I want to find how far behind I am.

Shane.

[BruceAmmons]

Sorry, I got swamped by a project deadline and didn't have time to work on the coding challenge results.  It also took a little work to get the entries that were directly submitted to NI.  I have everything I need now, though, and I have a little time.  I should be able to post the results within a couple of days.

Bruce