A Speed Competition ;-)

Talk about anything
newbieforever
Posts: 444
Joined: 24 Aug 2016, 03:34

A Speed Competition ;-)

06 May 2020, 03:50

.
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
PrimeCompetition.jpg (13.81 KiB) Viewed 928 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 ;-)

31 May 2020, 05:53

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
Prime.jpg (12.47 KiB) Viewed 659 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
User avatar
nnnik
Posts: 4470
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: A Speed Competition ;-)

09 Jun 2020, 09:38

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

Return to “Offtopic”

Who is online

Users browsing this forum: No registered users and 6 guests