Fastest Primes Competition for new benchmark

[PhilipLeitch]

I recently took part in a competition for MS SQL Server to create a process that could calculate a list of primes, where the fastest process won.

This required a basic understanding of primes and a rather advanced understanding of SQL Server in order to get the fastest times.

The smallest tweaks sometimes produced big differences in time, so it was educational to all involved.


This got me thinking that the processes involved would be a really good benchmark for Mathcad so that we could compare speeds from version to version. So let's have a competition to see who can come up with the most efficient Mathcad worksheet to calculate primes.

This has to be a calculated list of primes (not loaded). The form of the processing is up to you:
- it could be a standard prime validation procedure;
- it could be something unique that you have come up with;
- it could be something that looks clunky, but is the fastest way to get the job done in MathCad.



Recording the time taken is going to be important too. Put this at the top of the worksheet:
Start:=time(0)

And this at the end:
time(0) - Start =

Go to the bottom of the worksheet and then calculate the worksheet - it may pay to have calculations turned off so that it only calculates when you tell it to.

This will give the time in seconds to calculate the sheet for your computer (and your version of MathCad).

The results should be an array which is either single column, or where the first column is the prime. This will assist with validating - the same validation code can be pasted at the end of each different method.

I'm working on the validation code now, and I will post it here shortly.

The code will need to run on multiple versions - let's say versions 11 on (but if there is support for earlier versions we can change that requirement). I can only test versions 13 and 14, so others will have to work with earlier versions.

To start with, let's set the competition to be all primes under 10,000,000, which is 664,579 primes. We can adjust that if the figure is too low or too high. I'd like a benchmark to be somewhere between 2-5 mins to run.

Cheers,
Philip
___________________
Nobody can hear you scream in Euclidean space.

[TomGutman]

Been there, done that, burned the T-shirt.

The sheet I posted in http://collab.mathsoft.com/read?125705,63 includes the evaluation (in the collapsed area) of PrimesTo for 10000000. Takes about 28 seconds on MC11 and about 9 seconds on MC14.
__________________
� � � � Tom Gutman

[PhilipLeitch]

Great.

Thanks - I'll look through that in more detail.

Philip
___________________
Nobody can hear you scream in Euclidean space.

[ptc-1368288]

On 8/19/2009 9:58:00 PM, Tom_Gutman wrote:
>Been there, done that, burned
>the T-shirt.
>
>The sheet I posted in
>http://collab.mathsoft.com/rea
>d?125705,63 includes the
>evaluation (in the collapsed
>area) of PrimesTo for
>10000000. Takes about 28
>seconds on MC11 and about 9
>seconds on MC14.
>__________________
>� � � � Tom Gutman
____________________________

< XX(1483) 11 s in my machine Mathcad 11.2a
Steven works sheet finds 664579 in 17 s
XX(1483) finds 664578

jmG

[Al2000]

On 8/19/2009 9:58:00 PM, Tom_Gutman wrote:
>Been there, done that, burned
>the T-shirt.
>
>The sheet I posted in
>http://collab.mathsoft.com/rea
>d?125705,63 includes the
>evaluation (in the collapsed
>area) of PrimesTo for
>10000000. Takes about 28
>seconds on MC11 and about 9
>seconds on MC14.

Interesting case of convergent evolution 🙂 I almost laughed when I donwloaded your sheet to compare your solution with mine. Well, I guess there are not too much choices... (well done, Eratosthenes!)

My solution is slightly faster than yours in my machine, about 2-3 seconds.



As reference, my machine is a Pentium 4, 3 GHz and I'm running Mathcad 2001 Pro.

The graph is a combined print screen of the two routines and the times displayed are with all programs (music, net services, keyboard hotkeys,...) disabled.

Saludos,

Al

[ptc-1368288]

The time I reported (<11 s) is for a smaller machine 1.8 G, 224MB. Can you attach the work sheet itself so to try it.

jmG

[Al2000]

On 8/20/2009 3:19:46 AM, jmG wrote:

>The time I reported (<11 s)
>is for a smaller machine 1.8
>G, 224MB. Can you attach the
>work sheet itself so to try
>it.

I ask your pardon for not fixing the program to work with ORIGIN = 0 nor removing formatting.

Saludos,

Al

[ptc-1368288]

On 8/20/2009 8:20:15 AM, Al2000 wrote:
>On 8/20/2009 3:19:46 AM, jmG wrote:
>The
>time I reported (<11 s)
>is for a
>smaller machine 1.8
>G, 224MB. Can you
>attach the
>work sheet itself so to
>try
>it.

I ask your pardon for not
>fixing the program to work with ORIGIN =
>0 nor removing formatting.

Saludos,

Al
__________________

OK, Al is upset !

Can't download your work sheet because the file name has gyzmas on letters.
Saludos amigo.


jmG

[Al2000]

No problem

[ptc-1368288]

On 8/20/2009 3:20:10 PM, Al2000 wrote:
>No problem
______________________

Thanks for the work sheet, comparative timing [10000000]
Tom XX(1483)... 8 seconds all correct
Yours ......... 7 seconds 1rst and last incorrect.

jmG

[Al2000]

On 8/20/2009 10:18:11 PM, jmG wrote:
...
>Yours ......... 7 seconds 1rst and last
>incorrect.

Damn! There it goes my reputation!

[ptc-1368288]

On 8/20/2009 11:26:01 PM, Al2000 wrote:
>On 8/20/2009 10:18:11 PM, jmG wrote:
>...
>>Yours ......... 7 seconds 1rst and last
>>incorrect.
>
>Damn! There it goes my reputation!
___________________________

Sorry amigo, check !
Only your program goes, not your reputation.

jmG

[PhilipLeitch]

That does raise a question - is 1 a prime?

I take it that it isn't, because it isn't divisible by both 1 and itself. Not "both" - because there is only 1. That is, 1 has only itself as a factor, where-as every other prime has itself and 1. Is that right?

Is there a more accurate way of stating what a prime is?



Philip
___________________
Nobody can hear you scream in Euclidean space.

[Al2000]

On 8/21/2009 2:04:41 AM, pleitch wrote:
>That does raise a question -
>is 1 a prime?
>
>I take it that it isn't,
>because it isn't divisible by
>both 1 and itself. Not "both"
>- because there is only 1.
>That is, 1 has only itself as
>a factor, where-as every other
>prime has itself and 1. Is
>that right?
>
>Is there a more accurate way
>of stating what a prime is?
>

Jean is right, number 1 is no longer considered a prime number (from middle 1900's, but I never got the memo, I was too young 🙂

Currently definition is that a prime number is only divisible by TWO distintic factors, 1 and itself.

Saludos,

Al

[TomGutman]

One is not usually considered a prime. It is a unit (a number that has an inverse). The logic is that primes represent the unique factors of numbers, but that uniqueness is only up to unit factors -- you can always insert additional unit factors (for the normal integers, the only units are 1 and -1).

Another viewpoint is that of ideals. Primes are numbers that generate maximal ideals. But units do not generate ideals at all, but recreate the entire ring.
__________________
� � � � Tom Gutman

[AlvaroDíaz]

On 8/21/2009 2:04:41 AM, pleitch wrote:
>Is there a more accurate way of stating what a prime is?

See

http://en.wikipedia.org/wiki/Wilson's_theorem

This give a necessary and sufficient condition.

Alvaro.

[ptc-1368288]

The prime numbers has been a common bench mark as far as the Byte magazine in 1983. In almost every issue of the magazine, the bench marks were reported. I might still have the "Ontario Technologist" magazine reporting 32 hrs 15 minutes Cray X-100 for the Mersenne 69 [from instantaneous recollection, as I write it]. So, nothing new Philip, but still interesting to see old goodies grow wings and fly again.

jmG