## A Speed Competition ;-)

newbieforever
Posts: 444
Joined: 24 Aug 2016, 03:34

### A Speed Competition ;-)

.
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 921 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
Posts: 444
Joined: 24 Aug 2016, 03:34

### Re: A Speed Competition ;-)

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 652 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
Posts: 4470
Joined: 30 Sep 2013, 01:01
Location: Germany

### Re: A Speed Competition ;-)

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.
Recommends AHK Studio