# Algorithm puzzle challenge (Xojo vs C# vs Python)

At our company we have a Xojo fan, a C# fan and a Python fan.

We decided to have a little bit of fun and play a game to see which language runs a certain algorithm the fastest.

Here are the rules of the game:

Calculate the sum of all the prime numbers between 0 and 1,000,000. As output give the sum, total number of prime numbers, and the running time.

Currently I get Xojo to complete the taksk in 1.26s (compiled, not via IDE). C# is currently the winner completing the task in 0.4s (YES, a fraction of a second).

Something I already learned, it is better to use UInt32 instead of UInt64 where possible. With UInt64 my algorithm ran 2.4s, with UInt32 at ran 1.26s.

Here is the algorithm I used:

``````  Dim i As UInt32
Dim j As UInt32
Dim total As UInt64
Dim count As UInt32
Dim max As UInt32
Dim isPrime As Boolean
Dim startTime As Double
Dim endTime As Double

startTime = Microseconds()

total = 2
count = 0
i = 3
while i <= 1000000

max = Sqrt(i)
isPrime = true
j = 2
while (j <= max) and isPrime
if (i mod j) = 0 then
isPrime = false
end if
j = j + 1
wend

if isPrime then
total = total + i
count = count  + 1
end if

i = i + 2
wend

endTime = Microseconds()

System.DebugLog "Items: " + Str(count) + EndOfLine + _
"Sum: " + Str(total) + EndOfLine + _
"Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"``````

Can anyone spot obvious improvements I can make? Would be great if I could get it to run faster than C#.

FWIW, here is the C# code that currently beats my code:

``````using System;
using System.Diagnostics;

{
class Program
{
static void Main(string[] args)
{
int i = 3, j, count = 0;
double max, total = 2;
bool isPrime;

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();

while (i <= 1000000)
{
max = Math.Sqrt(i);
isPrime = true;
j = 2;
while (j <= max && isPrime)
{
if (i % j == 0)
isPrime = false;
j += 1;
}
if (isPrime)
{
total += i;
count ++;
}
i += 2;
}
stopWatch.Stop();
TimeSpan ts = stopWatch.Elapsed;
Console.WriteLine(String.Format("Items: {0}", count));
Console.WriteLine(String.Format("Sum: {0}", total));
Console.WriteLine(String.Format("Time: {0}", ts));
}
}
}``````

PS. If anyone knows why in the world C# would run so much faster, it would be nice if you could share your wisdom.

Fun contest Alwyn.

There used to be a difference in performance between xojoscript and xojo (xojoscript being faster), but I don’t know if that’s the case anymore.

Julen

``#pragma BackgroundTasks False``

It takes only half of the time for me (tested in IDE).

Beautiful Thomas, it now runs 0.524446.

The problem IS, the C# guy just got his code to run in 0.02s (by tweaking his types).

He simply changed `double max` to `int max`, and `double total` to `long total`.

[quote=336245:@Julen Ibarretxe Uriguen]Fun contest Alwyn.

There used to be a difference in performance between xojoscript and xojo (xojoscript being faster), but I don’t know if that’s the case anymore.

Julen[/quote]

I think I’ll have to test this, for the sake of the challenge

Try this…
I did consider changing isPrime from boolean to integer
then use isPrime = 1 or isPrime = 0
Then the

```if isPrime then total = total + i count = count + 1 end if```

becomes

``` total = total +isprime count = count + isprime```

removing one test

I would expect that using integer instead of UINTanything would mean faster performance as it should be using the ‘native’ integer size…?

[code]
#pragma DisableBoundsChecking
#pragma DisableAutoWaitCursor
#pragma StackOverflowchecking False
#pragma NilObjectChecking False

//these knocked off 30%

Dim i As UInt32
Dim j As UInt32
Dim total As UInt64
Dim count As UInt32
Dim max As UInt32
Dim isPrime As Boolean
Dim startTime As Double
Dim endTime As Double

startTime = Microseconds()

total = 2
count = 0
i = 3
while i <= 1000000

``````max = Sqrt(i)
isPrime = true
j = 2
while  isPrime and (j <= max)    //test for boolean first.. ignores the next bit so shaves off some time
if (i mod j) = 0 then
isPrime = false
end if
j = j + 1
wend

if isPrime then
total = total + i
count = count  + 1
end if

i = i + 2
``````

wend

endTime = Microseconds()

msgbox "Items: " + Str(count) + EndOfLine + _
"Sum: " + Str(total) + EndOfLine + _
“Time: " + Str((endTime - startTime) / 1000000, “##########0.000000”) + " seconds”

//while isPrime=1 and (j <= max)
//if (i mod j) = 0 then
//isPrime = 0
//end if
//j = j + 1
//wend[/code]

Best time I now get is 0.48s.

PS. The C# guy just informed me he gets 0.2s, NOT 0.02s as previously reported. So the competition is still within reach…

Have you tried compiling for 64-bit using the aggressive compiler setting?

There are more pragmas you can use which would better replicate the C# code:

#pragma BoundsChecking False
#pragma StackOverflowChecking False
#pragma NilObjectChecking False

http://developer.xojo.com/pragma-directives

I don’t think the current version I’m using has that option (or at least, I couldn’t find an aggressive compiler setting)? I’m using Xojo 2016 r1.1.

[quote=336276:@Greg O’Lone]#pragma BoundsChecking False
#pragma StackOverflowChecking False
#pragma NilObjectChecking False[/quote]

To summarize, this is currently the code that gives the best run:

``````  #pragma BackgroundTasks False
#pragma BoundsChecking False
#pragma DisableBoundsChecking
#pragma StackOverflowchecking False
#pragma NilObjectChecking False

Dim i As Integer
Dim j As Integer
Dim total As Double
Dim count As Integer
Dim max As Integer
Dim isPrime As Boolean
Dim startTime As Double
Dim endTime As Double

startTime = Microseconds()

total = 2
count = 0
i = 3
while i <= 1000000

max = Sqrt(i)
isPrime = true
j = 2
while isPrime and (j <= max)
if (i mod j) = 0 then
isPrime = false
end if
j = j + 1
wend

if isPrime then
total = total + i
count = count  + 1
end if

i = i + 2
wend

endTime = Microseconds()

System.DebugLog "Items: " + Str(count) + EndOfLine + _
"Sum: " + Str(total) + EndOfLine + _
"Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"``````

On my computer your code runs in 0.46 seconds.

Compiling for 64 bit the code ran in 0.95 seconds!

Does anyone have an explanation?

Does this agree with your sum?

``Sum: 37550402023  Time: 0.0253104 seconds``

This is running compiled as 64 bit app.

My Code:

``````  #pragma BackgroundTasks False
#pragma BoundsChecking False
#pragma DisableBoundsChecking
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
dim et As Double=Microseconds
dim n(-1) As Boolean
dim m As Integer = 1000000
redim n(m)
dim i,j,k As Integer
dim sum As int64 = 0
j = 2
while j<m
for k = j to m
if not n(k) then
sum=sum+k
exit
end if
j=k
next
for i = k to m step k
n(i)=true
next
wend
txtAreaOut.Text="Sum: "+str(sum) +"  Time: "+str((Microseconds-et)/1e6)+" seconds"``````

IDE,
Xojo 2017r1.1
MacBook Pro 13" i3

Report:
Items: 78497
Sum: 3.755040e+10
Time: 2.999635 seconds

I used MsgBox to get the report

Does it run faster as a console app?

I think @Robert Weaver hit it right.

Here is a project showing the time difference. 0.03 seconds on my machine.

https://www.dropbox.com/s/dlclg0ke31pj0dq/Speed%20Test.xojo_binary_project?raw=1

results

``` Method1 Method2 In IDE Debug 4.6248 0.2559 Compiled 32 Bit 0.4548 0.0381 Compiled 64 Bit 0.9606 0.0306 64 Bit Aggressive 0.6168 0.0171```

Win 10, i7-2600, 3.40 GHz

FYI, my time of 0.0253 seconds was on a 2015 MacBook Pro 2.2 GHz Intel Core i7.
Compilation was set to aggressive.

WOW, Robert… just WOW…

That is the correct answer, and Xojo is now in the lead at our office (thanks to you)

The previous best time was C#, 0.2s

New best time is Xojo, 0.04s.

PS. And the 0.04s is a console app compiled as 32-bit. I’m sure a few more milliseconds might be shaved by using a 64-bit aggressive compilation.

O, just saw Neil posted a a nice table sowing the results between 32-bit and 64-bit.