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

I added just one line to your code Robert, because part of the rules are that on has to report the number of prime numbers as well. But it still runs in the same time. So, this is currently the best code:

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

dim n(-1) As Boolean
dim m As Integer = 1000000
redim n(m)
dim i,j,k As Integer
dim sum As int64 = 0
Dim startTime As Double
Dim endTime As Double
Dim count As Integer

startTime = Microseconds()

j = 2
while j<m
for k = j to m
if not n(k) then
sum=sum+k
count = count + 1
exit
end if
j=k
next
for i = k to m step k
n(i)=true
next
wend

endTime = Microseconds()

msgbox "Items: " + Str(count)
msgbox "Sum: " + Str(sum)
msgbox "Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"``````

Any more ideas how this can be improved even further?

I’m getting 0.019 seconds on a 2015 MacBook Pro I7 compiled to 64bit aggressive.
Desktop app not console.

How’s the Python guy getting on LOL, he was actually standing right here next to me while you posted the question He is currently rewriting the Xojo code in Python so that we can compare further.

…asking me some question about Redim and what the purpose of Redim is.

He actually got his speed down to 0.3s which is very impressive if I might say. Will see how the Xojo algorithm fairs on Python.

Im pretty sure we already know what these primes are.

```dim Primes(7498) Primes(0) = 2 Primes(1) = 3 ... etc``` Along Jeff’s comment…

I have an idea for an optimization that requires an acknowledgement that 2 is prime and no other even number is prime. Is that permitted under the rules?

Basically we decided that we are not allowed to use lookups, and that the values need to be “calculated”, so that should be permitted Kem.

In my first method I also skipped all even numbers, but it still didn’t come close to Robert’s time.

I think with my next attempt I’m going to check if one can’t maybe split the loop in two by using threading, and effectively halving the time.

Threading won’t help and would actually slow it down. On the other hand, here are my results:

``````Original:
Items: 78,498
Sum: 37,550,402,023
Time: 0.016 s

Mine:
Items: 78,498
Sum: 37,550,402,023
Time: 0.007 s``````

And the code:

``````const kMax = 1000000
dim notPrime( kMax ) as boolean

dim lastOuterIndex as integer = Sqrt( kMax ) + 1
for outer as integer =  3 to lastOuterIndex step 2
dim firstInnerIndex as integer = outer * outer
dim stepper as integer = outer * 2
for inner as integer = firstInnerIndex to kMax step stepper
notPrime( inner ) = true
next
next

dim sum As int64 = 2
Dim count As Integer = 1
for i as integer = 3 to kMax step 2
if notPrime( i ) = false then
count = count + 1
sum = sum + i
end if
next``````

Essentially, it does what Robert’s does, but it precomputes the primes and skips the even numbers.

Edit: This is a desktop app compiled with 64-bt aggressive running on a MacBook Pro 2.9 GHz i7.

This gives further speed improvement.
Time: 0.0142204 seconds

``````  #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 int64
dim sum As int64 = 2
dim count As Int64=1
j = 3
while k<m
for k = j to m step 2
if not n(k) then
n(k)=true
sum=sum+k
count=count+1
exit
end if
next
j=k
for i = k*k to m step k
n(i)=true
next
wend
et=(Microseconds-et)/1e6
txtAreaOut.Text="Count: "+str(count) +"  Sum: "+str(sum) +"  Time: "+str(et)+" seconds"``````

One further optimization gets it down to 0.005s.

``````const kMax = 1000000
dim notPrime( kMax ) as boolean

dim lastOuterIndex as integer = Sqrt( kMax ) + 1
for outer as integer =  3 to lastOuterIndex step 2
if notPrime( outer ) = false then
dim firstInnerIndex as integer = outer * outer
dim stepper as integer = outer * 2
for inner as integer = firstInnerIndex to kMax step stepper
notPrime( inner ) = true
next
end if
next

dim sum As int64 = 2
Dim count As Integer = 1
for i as integer = 3 to kMax step 2
if notPrime( i ) = false then
count = count + 1
sum = sum + i
end if
next``````

Robert’s is still faster under 64 bit. This is very interesting. Nicely done Kem!

On my 32-bit console compiled version I now get 0.029 with Kem’s algorithm and 0.033s with Robert’s algorithm.

I really need to think about upgrading my Xojo license again, because I cannot unfortunately test the 64-bit aggresively compiled code on my current license.

However, this is seriously impressive.

This morning I started with a 7s result, which is now down to 0.029s (0.005 on 64-bit bit). That is Insane.

Now imagine all the software in the world was written with this optimization effort, where the industry would be at.

FWIW, the Python guy just informed me he gives up. Xojo wins this one.

I can imagine that.

Robert, FYI, loop indexes are calculated each time through the loop so you’re better off pre-calculating them. So:

``    for i = k*k to m step k``

would be faster as:

``````    dim firstK as Int64 = k * k
for i = firstK to m step k``````

Also, by using k as the step, you are flagging all the even numbers that you’re skipping anyway. For example, where k = 3, you flag 3, 6, 9, 12. Use `k * 2` to skip the even numbers, but again, cached for speed.

[quote=336325:@Neil Burkholder]Robert’s is still faster under 64 bit. This is very interesting.
[/quote]

I can’t reproduce those results. Difference between the Mac and Windows?

And honestly, with the speeds we’ve now achieved, it’s not like someone would have time to do laundry with the difference. I imagine him walking away slowly, his head hung in shame.

And what of the C# fellow?