A Speed Competition ;-)

[newbieforever]

.
May I present and initiate a funny, weird, but also serious competition here?

By means of AHK a tool for the determination of all prime numbers < 10**6 shall be created.

Conditions:
- The tool must be compiled.
- The executable must not be larger than 400 kB when compressed.
- Only AHK features may be used in the script (AHK_L, not AHK_H).
- The tool should be able to run on any Windows computer without pre-installed AHK.
- To check if a number is prime, the function Prime() (see below) must be used, other methods must not be used for this purpose.
- The script must first perform the "simple" calculation given below. Afterwards, a "smart" solution must be used, which then participates in the competition.
- In an ini file the calculation time for both methods and (for the purpose of checks) the number of prime numbers found and a checksum must be written. The list of prime numbers has to be created, but does not have to be output.
- The smart-to-simple ratio for the calculation time is the success criterion.

Who achieves the best smart-to-simple ratio and with which smart method?

As a reward for the winner I will write out a book present worth about 30 $ (€), the winner will be given the choice of the book.

PS: The extremely restrictive conditions may sound a bit strange, but they have a serious background (at least for me).

EDIT: Please do not post your code here right away, but first only your smart-to-simple ratio!

PrimeCompetition.jpg (13.81 KiB) Viewed 3274 times

Code: Select all

; PrimeCompetition.ahk

/*
By means of AHK a tool for the determination of all prime numbers < 10**6 shall be created.
Conditions:
- The tool must be compiled.
- The executable must not be larger than 400 kB when compressed.
- Only AHK features may be used in the script (AHK_L, not AHK_H).
- The tool should be able to run on any Windows computer without pre-installed AHK. 
- To check if a number is prime, the function Prime() (see below) must be used, other methods must not be used for this purpose.
- The script must first perform the "simple" calculation given below. Afterwards, a "smart" solution must be used, which then participates in the competition.
- In an ini file the calculation time for both methods and (for the purpose of checks) the number of prime numbers found and a checksum must be written. The list of prime numbers has to be created, but does not have to be output.
- The smart-to-simple ratio for the calculation time is the success criterion.
*/

b := 1000000
; With this b the calculation time for the simple method could be about 2 to 3 min.
; A smaller b could be used for tests.

Prime(n) {                          ; https://autohotkey.com/board/topic/47325-isprime-check-if-number-is-prime/
  Loop % Floor(Sqrt(n)) -1 {
	If !Mod(n, A_Index + 1)
      Return 0
    }
  Return 1
  }

IniF := A_ScriptDir . "\Prime.ini"
IniWrite, 0, %IniF%, Tim, Tsim
IniWrite, 0, %IniF%, Chk, Csim
IniWrite, 0, %IniF%, Num, Nsim


; SIMPLE METHOD
; =============

SetBatchLines, -1
SoundBeep
T := A_TickCount
n := 1 , Psim := "" , Csim := Nsim := 0 
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psim := Psim . n . "," , Csim := Csim + n , Nsim := Nsim + 1
  n := n + 2
  }
Psim := SubStr(Psim, 1, -1)
Tsim := A_TickCount - T
IniWrite, %Tsim%, %IniF%, Tim, Tsim
IniWrite, %Csim%, %IniF%, Chk, Csim
IniWrite, %Nsim%, %IniF%, Num, Nsim

SoundBeep, , 500


; SMART METHOD
; ============================

/*

INSERT HERE YOUR SMART SOLUTION!!!
==================================
Tsma, Nsma and Csma should be written to ini file.
A check by comparing Nsma and Csma with Nsim and Csim should be made.

*/

; COMPARING SMART VS. SIMPLE
; ==========================

Sma2Sim := Tsma / Tsim
MsgBox Smart to Simple ratio: %Sma2Sim%`r`n%Tsma% ms  vs.  %Tsim% ms

[newbieforever]

OK, I am overwhelmed by the great interest in my competition and the underlying question. I also understand that I am in a lost cause here.

Therefore I hereby declare the competition closed.

Finally, I would like to present my own "smart method" using an example. On my old Surface 3 (Win 10), this smart method reduces the calculation time by about 90%.

Prime.jpg (12.47 KiB) Viewed 3005 times

Please note that the script must be compiled with an AutoHotkey.exe, not with an AutoHotkey.bin. (With a compressed AutoHotkeyU32.exe you get an exe size of 377 kB.)

I would like to note that my "competition" here is related to my concern presented here:
https://www.autohotkey.com/boards/viewtopic.php?f=13&t=75330

But, as I said, it has become clear to me in the meantime that I am completely and finally in a lost position.

Code: Select all

; Prime.ahk
; !!! NOTE !!!
; For demo purposes this script must be compiled with AutoHotkey.exe, not AutoHotkey.bin.
; As long as there is no /e option for compiled scripts, this is the only simple way 
; to use a compiled script as an interpreter for external scripts.
; (However, the ability to send CL parameters to the embedded script is lost.)

IniF := A_ScriptDir . "\Prime.ini"
IniWrite, 0, %IniF%, Tim, Tsim
IniWrite, 0, %IniF%, Chk, Csim
IniWrite, 0, %IniF%, Num, Nsim

b := 1000000

; GET PRIME NUMBERS < b BY USING THE Prime() FUNCTION
; Output: number of prime numbers, checksum (sum of all prime numbers), calculation time

Prime(n) {                          ; https://autohotkey.com/board/topic/47325-isprime-check-if-number-is-prime/
  Loop % Floor(Sqrt(n)) -1 {
	If !Mod(n, A_Index + 1)
      Return 0
    }
  Return 1
  }

; SIMPLE METHOD
; =============

SetBatchLines, -1
SoundBeep
T := A_TickCount
n := 1 , Psim := "" , Csim := Nsim := 0 
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psim := Psim . n . "," , Csim := Csim + n , Nsim := Nsim + 1
  n := n + 2
  }
Psim := SubStr(Psim, 1, -1)
Tsim := A_TickCount - T
IniWrite, %Tsim%, %IniF%, Tim, Tsim
IniWrite, %Csim%, %IniF%, Chk, Csim
IniWrite, %Nsim%, %IniF%, Num, Nsim

SoundBeep, , 500


; NEWBIEFOREVER's SMART METHOD
; ============================

T := A_TickCount
SoundBeep

; Creating and executing two auxiliary scripts

IniWrite, 0, %IniF%, Tim, Tsm0
IniWrite, 0, %IniF%, Chk, Csm0
IniWrite, 0, %IniF%, Num, Nsm0
IniWrite, 0, %IniF%, Tim, Tsm1
IniWrite, 0, %IniF%, Chk, Csm1
IniWrite, 0, %IniF%, Num, Nsm1
IniWrite, 0, %IniF%, Tim, Tsm2
IniWrite, 0, %IniF%, Chk, Csm2
IniWrite, 0, %IniF%, Num, Nsm2
IniWrite, 0, %IniF%, Tim, Tsm3
IniWrite, 0, %IniF%, Chk, Csm3
IniWrite, 0, %IniF%, Num, Nsm3

Interpr := A_AhkPath
If A_IsCompiled
   Interpr := SubStr(A_ScriptFullPath, 1, -3) . "exe"
Int1  := A_ScriptDir . "\Int1.exe"
Int2  := A_ScriptDir . "\Int2.exe"
Int3  := A_ScriptDir . "\Int3.exe"
FileCopy, %Interpr%, %Int1%
FileCopy, %Interpr%, %Int2%
FileCopy, %Interpr%, %Int3%

Aux1 := A_ScriptDir . "\Aux1.ahk"
Aux2 := A_ScriptDir . "\Aux2.ahk"
Aux3 := A_ScriptDir . "\Aux3.ahk"

Scr1 =
(
SetBatchLines, -1
T := A_TickCount
IniF := A_ScriptDir . "\Prime.ini"
b := %b%
n := 3 , Psm1 := "" , Csm1 := Nsm1 := 0
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psm1 := Psm1 . n . "," , Csm1 := Csm1 + n , Nsm1 := Nsm1 + 1
  n := n + 8
  }
Psm1 := SubStr(Psm1, 1, -1)
Tsm1 := A_TickCount - T
IniWrite, `%Tsm1`%, `%IniF`%, Tim, Tsm1
IniWrite, `%Csm1`%, `%IniF`%, Chk, Csm1
IniWrite, `%Nsm1`%, `%IniF`%, Num, Nsm1
Prime(n) {
  Loop `% Floor(Sqrt(n)) -1 {
	If !Mod(n, A_Index + 1)
      Return 0
    }
  Return 1
  }
)

Scr2 =
(
SetBatchLines, -1
T := A_TickCount
IniF := A_ScriptDir . "\Prime.ini"
b := %b%
n := 5 , Psm2 := "" , Csm2 := Nsm2 := 0
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psm2 := Psm2 . n . "," , Csm2 := Csm2 + n , Nsm2 := Nsm2 + 1
  n := n + 8
  }
Psm2 := SubStr(Psm2, 1, -1)
Tsm2 := A_TickCount - T
IniWrite, `%Tsm2`%, `%IniF`%, Tim, Tsm2
IniWrite, `%Csm2`%, `%IniF`%, Chk, Csm2
IniWrite, `%Nsm2`%, `%IniF`%, Num, Nsm2
Prime(n) {
  Loop `% Floor(Sqrt(n)) -1 {
	If !Mod(n, A_Index + 1)
      Return 0
    }
  Return 1
  }
)

Scr3 =
(
SetBatchLines, -1
T := A_TickCount
IniF := A_ScriptDir . "\Prime.ini"
b := %b%
n := 7 , Psm3 := "" , Csm3 := Nsm3 := 0
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psm3 := Psm3 . n . "," , Csm3 := Csm3 + n , Nsm3 := Nsm3 + 1
  n := n + 8
  }
Psm3 := SubStr(Psm3, 1, -1)
Tsm3 := A_TickCount - T
IniWrite, `%Tsm3`%, `%IniF`%, Tim, Tsm3
IniWrite, `%Csm3`%, `%IniF`%, Chk, Csm3
IniWrite, `%Nsm3`%, `%IniF`%, Num, Nsm3
Prime(n) {
  Loop `% Floor(Sqrt(n)) -1 {
	If !Mod(n, A_Index + 1)
      Return 0
    }
  Return 1
  }
)

FileAppend, %Scr1%, %Aux1%
FileAppend, %Scr2%, %Aux2%
FileAppend, %Scr3%, %Aux3%

Run, %Int1% %Aux1%
Run, %Int2% %Aux2%
Run, %Int3% %Aux3%

; Running master part

n := 1 , Psm0 := "" , Csm0 := Nsm0 := 0 
Loop 
  {
  If (n > b - 1)
    Break
  If Prime(n)
    Psm0 := Psm0 . n . "," , Csm0 := Csm0 + n , Nsm0 := Nsm0 + 1
  n := n + 8
  }
Psm0 := SubStr(Psm0, 1, -1)
Tsm0 := A_TickCount - T
IniWrite, %Tsm0%, %IniF%, Tim, Tsm0
IniWrite, %Csm0%, %IniF%, Chk, Csm0
IniWrite, %Nsm0%, %IniF%, Num, Nsm0

; Detecting end

Loop {
  IniRead, Nsm1, %IniF%, Num, Nsm1
  IniRead, Nsm2, %IniF%, Num, Nsm2
  IniRead, Nsm3, %IniF%, Num, Nsm3
  If (Nsm1 && Nsm2 && Nsm3)
    Break
  }

IniRead, Tsm1, %IniF%, Tim, Tsm1
IniRead, Csm1, %IniF%, Chk, Csm1
IniRead, Tsm2, %IniF%, Tim, Tsm2
IniRead, Csm2, %IniF%, Chk, Csm2
IniRead, Tsm3, %IniF%, Tim, Tsm3
IniRead, Csm3, %IniF%, Chk, Csm3

Nsma := Nsm0 + Nsm1 + Nsm2 + Nsm3
Csma := Csm0 + Csm1 + Csm2 + Csm3

IniWrite, %Tsma%, %IniF%, Tim, Tsma
IniWrite, %Csma%, %IniF%, Chk, Csma
IniWrite, %Nsma%, %IniF%, Num, Nsma

Tsma := A_TickCount - T

Sleep, 100
FileDelete, %Int1%
FileDelete, %Int2%
FileDelete, %Int3%
FileDelete, %Aux1%
FileDelete, %Aux2%
FileDelete, %Aux3%

SoundBeep, , 500

If (!(Nsma = Nsim) || !(Csma = Csim)) {
  MsgBox ERROR
  ExitApp
  }  

; COMPARING SMART VS. SIMPLE
; ==========================

Sma2Sim := Tsma / Tsim
MsgBox Smart to Simple ratio: %Sma2Sim%`r`n%Tsma% ms  vs.  %Tsim% ms

[nnnik]

I would have competed but the rules were kind of too strict.
Specifically I have a better isPrime function - but that function relies on finding all the primes before this prime and buffering it.
This would have significantly increased the speed of the overall process by orders of magnitude.

[Kotte]

Even though this competition is over (from start it seems), I still wanted to give it a shot so I started to translate my "primes_under" script, written in python. If I count the time it took me before I gave up trying to get my script working in ahk, my Sma2Sim was around 20. When I ran my script in python and compared to your Tsim I got 0.0003. So lets call it an even 10 The script is around 0.6kB. When I failed to get it to work in ahk, I didn't bother making an exe. I'll give it another go when I get more familiar with ahk

[joedf]

For the benefit of everyone, I'd like to see other speedy methods regardless of the rules!

[Sam_]

For the benefit of everyone, I'd like to see other speedy methods regardless of the rules!

If the goal is to compute a list of all prime numbers <= n (of reasonable sized n), I suspect the fastest solution would be to write an optimized Sieve of Eratosthenes function in C++, convert it to machine code letting the compiler perform its optimizations, and then use that machine code in AHK.

Short of that, here’s my approach. Runs in just under 2 sec for me.

Code: Select all

tic:=QPC(1), Arr2:=FindPrimes2(10**6), toc:=(QPC(1)-tic)
MsgBox, % "Processing took " toc " sec."
ExitApp

; Finds all prime numbers <= n
; Returns an array of keys 0 to (at least) n with logical values indicating whether it is prime
FindPrimes2(n){
	VarSetCapacity(ii,n,49), is_prime:=StrSplit(StrGet(&ii,n,"CP0")), is_prime[1]:=0, is_prime[0]:=0, i:=2
	While ((j:=i*i)<=n)
		{
		If is_prime[i]
			{
			While (j<=n)
				is_prime[j]:=0, j+=i
			}
		i++
		}
	Return is_prime
}

QPC(R:=0){ ; By SKAN, http://goo.gl/nf7O4G, CD:01/Sep/2014 | MD:01/Sep/2014
  Static P:=0, F:=0, Q:=DllCall("QueryPerformanceFrequency","Int64P",F)
  Return !DllCall("QueryPerformanceCounter","Int64P",Q)+(R?(P:=Q)/F:(Q-P)/F) 
}

Apparently there are other suggestions for optimization out there, like sieving by only the odd numbers, but it depends more on what you want your output to look like, and whether the added code complexity actually gains you any speed in AHK. What was your solution?

[joedf]

That's neat! I haven't actually touched any prime number code in a while...