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 :slight_smile:

LOL, he was actually standing right here next to me while you posted the question :slight_smile:

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

:slight_smile:

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. :slight_smile:

I imagine him walking away slowly, his head hung in shame.

And what of the C# fellow?