[Beendet] µitLight März

MatthiasG.

Klar, erstelle dann im ersten Post eine Liste mit allen Skripts

Ubuntu

Naja wenns eine Linkliste ist dann ok.

mfg Ubuntu

**Andy**

Hi,
habe 2 Varianten am Start, eine listet die 100000 Primzahlen in "native AutoIt" zzt in 5 Sekunden @2.5Ghz mit "handelsüblichen" (String)-Befehlenund die andere, öhhm, mit Hilfe von 82 Bytes in einer AutoIt-Struct in unter 20 Millisekunden, unoptimiert...mal sehen, was sich da noch rausholen lässt....

MatthiasG.

So langsam geht der Monat zu Ende, ich wünsche allen weiterhin viel Erfolg!

**Andy**

Um nochmal alle Klarheiten zu beseitigen:
Die Bugfix´sche "Testumgebung" ist also verbindlich?!
D.h. das Filewrite schreibt einen Textstring(mit den Primzahlen von 2-...) in die Datei und das "wie kommen die Primen in den Textstring?" erfolgt vor der Zeitmessung?
Oder ist zwischen Zeitnahme und Filewrite eine "wie_auch_immer_Umformung" der Primzahlen in den String vorgesehen?

[autoit]

Local $timer = TimerInit()

[/autoit][autoit][/autoit][autoit]

Func _GetPrim(ByRef $timer)
; ...
; ...
ConsoleWrite(TimerDiff($timer) & @CRLF)
FileWrite($file, $100000_Primzahlen)
EndFunc

[/autoit]

**UEZ**

Ich dachte, dass wir den schnellsten Algorithmus zur Bestimmung von 100000 Primzahlen suchen, aber im 1. Post steht "Wer die höchste Primzahl nach 10 Minuten gefunden hat, hat gewonnen.".

Hier meine Version zur Bestimmung der 100000 Primzahlen:

Spoiler anzeigen

[autoit]

#include <Memory.au3>

[/autoit] [autoit][/autoit] [autoit]

Local $until = 1299709
Local $start = TimerInit()
;~ Local $pz = Eratosthenes_Calc($until)
Local $pz = Eratosthenes_Calc_ASM($until) ;bytecode variant
Local $stop = TimerDiff($start)
Local $rowl = Ceiling(($until ^ 0.5) ^ 0.5)
Local $aTemp = StringSplit(StringMid($pz, 1, StringLen($pz) - 1), " ")

[/autoit] [autoit][/autoit] [autoit]

#region GUI ini
Local $iMemo, $hGUI, $w, $h
Local $font_size = 9
Local $display = 0 ;display all prime numbers
If $display Then
$w = StringLen($until) * $rowl * $font_size
If $w < 400 Then
$w = 400
ElseIf $w > @DesktopWidth * 0.95 Then
$w = @DesktopWidth * 0.95
EndIf
$h = @DesktopHeight * 0.9
Else
$w = 400
$h = 150
EndIf
#endregion GUI ini

[/autoit] [autoit][/autoit] [autoit]

#region GUI
$hGUI = GUICreate("Prime Numbers Calculator by UEZ 2010", $w, $h, 0, 0)
$iMemo = GUICtrlCreateEdit("", 2, 2, $w - 4, $h - 6, 0x00200000 + 0x00100000 + 0x0800)
GUICtrlSetLimit(-1, 0x7FFFFFFF)
GUICtrlSetFont($iMemo, $font_size, 400, 0, "Courier New")
GUICtrlSetBkColor($iMemo, 0xFFFFFF)

[/autoit] [autoit][/autoit] [autoit]

MemoWrite("Sieving prime numbers till " & $until & ": " & @CRLF)
MemoWrite("Found " & $aTemp[0] & " prime numbers!" & @CRLF)
MemoWrite("Benchmark: " & Round($stop / 1000, 4) & " seconds to sieve prime numbers." & @CRLF)
If $display Then
MemoWrite(@CRLF & "Numbers:" & @CRLF)
For $z = 1 To $aTemp[0]
MemoWrite(StringFormat("%" & StringLen($until) + 1 & "s", $aTemp[$z] & " "))
If Mod($z, $rowl) = 0 Then MemoWrite(@CRLF)
Next
EndIf

[/autoit] [autoit][/autoit] [autoit]

MemoWrite(@CRLF)
#endregion GUI
GUISetState()
MouseClick("left", 100, 85, 1, 1)

[/autoit] [autoit][/autoit] [autoit]

While GUIGetMsg() <> -3
WEnd

[/autoit] [autoit][/autoit] [autoit]

Exit

[/autoit] [autoit][/autoit] [autoit]

Func Eratosthenes_Calc($l) ;
Local $p[$l + 1], $i, $j, $z, $n
For $z = 0x3 To $l Step 0x2
$p[$z] = 0x1
Next
For $i = 0x3 To Sqrt($l) Step 0x2
If $p[$i] And Mod($p[$i], 0x2) Then
For $j = $i * $i To $l Step $i
$p[$j] = 0
Next
$n &= $i & " "
EndIf
Next
If Not Mod($i, 0x2) Then $i += 0x1
For $z = $i To $l Step 0x2
If $p[$z] Then $n &= $z & " "
Next
Return "2 " & $n
EndFunc ;==>Eratosthenes_Calc

[/autoit] [autoit][/autoit] [autoit]

;this is nearly the same code as the AutoIt code above but in ASM
Func Eratosthenes_Calc_ASM($limit); thanks to Andy for helping me to get the ASM code runnning properly
#region bytecode
Local $bytecode = "0x558B6C2408C7450C020000008B5D006BDB04B80800000089C1C1C90241894C050883C00839D876EF89EF83C70883C70101DF" & _
"BB030000008B4D04B8080000008B74050839CB7F3383FE00750883C00883C302EBEB53505189D90FAFDB3B5D007F1489D86BC00483E804" & _
"C74405080000000001CBEBE759585BEBD28B75006BF604B80800000089C1C1C902418B5C050883FB00750983C00839F076EA5DC3E802000000" & _
"EBF05052535189D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6072083C701595B5A58C3"
#cs
:00000000 55 push ebp
:00000001 8B6C2408 mov ebp, dword ptr [esp+08]
:00000005 C7450C02000000 mov [ebp+0C], 00000002
:0000000C 8B5D00 mov ebx, dword ptr [ebp+00]
:0000000F 6BDB04 imul ebx, 00000004
:00000012 B808000000 mov eax, 00000008
:00000017 89C1 mov ecx, eax
:00000019 C1C902 ror ecx, 02
:0000001C 41 inc ecx
:0000001D 894C0508 mov dword ptr [ebp+eax+08], ecx
:00000021 83C008 add eax, 00000008
:00000024 39D8 cmp eax, ebx
:00000026 76EF jbe 00000017
:00000028 89EF mov edi, ebp
:0000002A 83C708 add edi, 00000008
:0000002D 83C701 add edi, 00000001
:00000030 01DF add edi, ebx
:00000032 BB03000000 mov ebx, 00000003
:00000037 8B4D04 mov ecx, dword ptr [ebp+04]
:0000003A B808000000 mov eax, 00000008
:0000003F 8B740508 mov esi, dword ptr [ebp+eax+08]
:00000043 39CB cmp ebx, ecx
:00000045 7F33 jg 0000007A
:00000047 83FE00 cmp esi, 00000000
:0000004A 7508 jne 00000054
:0000004C 83C008 add eax, 00000008
:0000004F 83C302 add ebx, 00000002
:00000052 EBEB jmp 0000003F
:00000054 53 push ebx
:00000055 50 push eax
:00000056 51 push ecx
:00000057 89D9 mov ecx, ebx
:00000059 0FAFDB imul ebx, ebx
:0000005C 3B5D00 cmp ebx, dword ptr [ebp+00]
:0000005F 7F14 jg 00000075
:00000061 89D8 mov eax, ebx
:00000063 6BC004 imul eax, 00000004
:00000066 83E804 sub eax, 00000004
:00000069 C744050800000000 mov [ebp+eax+08], 00000000
:00000071 01CB add ebx, ecx
:00000073 EBE7 jmp 0000005C
:00000075 59 pop ecx
:00000076 58 pop eax
:00000077 5B pop ebx
:00000078 EBD2 jmp 0000004C
:0000007A 8B7500 mov esi, dword ptr [ebp+00]
:0000007D 6BF604 imul esi, 00000004
:00000080 B808000000 mov eax, 00000008
:00000085 89C1 mov ecx, eax
:00000087 C1C902 ror ecx, 02
:0000008A 41 inc ecx
:0000008B 8B5C0508 mov ebx, dword ptr [ebp+eax+08]
:0000008F 83FB00 cmp ebx, 00000000
:00000092 7509 jne 0000009D
:00000094 83C008 add eax, 00000008
:00000097 39F0 cmp eax, esi
:00000099 76EA jbe 00000085
:0000009B 5D pop ebp
:0000009C C3 ret

[/autoit] [autoit][/autoit] [autoit]

:0000009D E802000000 call 000000A4
:000000A2 EBF0 jmp 00000094

[/autoit] [autoit][/autoit] [autoit]

:000000A4 50 push eax
:000000A5 52 push edx
:000000A6 53 push ebx
:000000A7 51 push ecx
:000000A8 89D8 mov eax, ebx
:000000AA BB0A000000 mov ebx, 0000000A
:000000AF 31C9 xor ecx, ecx
:000000B1 31D2 xor edx, edx
:000000B3 F7F3 div ebx
:000000B5 6652 push dx
:000000B7 80C101 add cl, 01
:000000BA 09C0 or eax, eax
:000000BC 75F3 jne 000000B1
:000000BE 6658 pop ax
:000000C0 0C30 or al, 30
:000000C2 AA stosb
:000000C3 E2F9 loop 000000BE
:000000C5 C60720 mov byte ptr [edi], 20
:000000C8 83C701 add edi, 00000001
:000000CB 59 pop ecx
:000000CC 5B pop ebx
:000000CD 5A pop edx
:000000CE 58 pop eax
:000000CF C3 ret
#ce
#endregion

[/autoit] [autoit][/autoit] [autoit]

Local $limes = Floor(Sqrt($limit))
Local $bin_len = Ceiling(StringLen($bytecode) * 0.5)
Local $pRemoteCode = _MemVirtualAlloc(0, $bin_len, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE)
Local $tCodeBuffer = DllStructCreate("byte[" & $bin_len & "]", $pRemoteCode)
DllStructSetData($tCodeBuffer, 1, $bytecode)
Local $tStruct = DllStructCreate("uint limit;uint limes;uint sieve[" & $limit + 1 & "];char prime[" & $limit & "]")
DllStructSetData($tstruct, "limit", $limit)
DllStructSetData($tstruct, "limes", $limes)
Local $ret = DllCall("user32.dll", "int", "CallWindowProcW", "ptr", $pRemoteCode, "ptr", DllStructGetPtr($tStruct), "int", 0, "int", 0, "int", 0)
Local $p = "2 3 5" & DllStructGetData($tStruct, "prime")
_MemVirtualFree($pRemoteCode, $bin_len, $MEM_DECOMMIT)
$tStruct = ""
$tCodeBuffer = ""
Return $p
EndFunc ;==>Eratosthenes_Calc_ASM

[/autoit] [autoit][/autoit] [autoit]

Func MemoWrite($sMessage = "")
GUICtrlSetData($iMemo, $sMessage, 1)
EndFunc ;==>MemoWrite

[/autoit]

Ich habe mal auch meine ASM Version dazu gepackt in der Bytecode Version (mein aller erster ASM Code überhaupt!)!

Vielen Dank an Andy für seine Hilfe und Unterstützung! Ohne seine Hilfe wäre wohl nie eine lauffähige Version entstanden!

~~Ich habe die Umwandlung von den Zahlen nach String in ASM noch nicht implementiert, so dass der Zeitgewinn in ASM durch das Auslesen des Structs wieder zunichte gemacht wird!~~

Auf meinem Schlepptop benötigt der AutoIt Code ca. 4.00 und der ASM Code ca. 0,07 Sekunden für die 100000 Primzahlen!

CPU: Intel(R) Pentium(R) Dual CPU T3200 @ 2.00GHz

Gruß,
UEZ

**Andy**

Wenn wir schon dabei sind^^
Dann zeige ich auch mal meine ASM-Version, incl. Umwandlung der Register in Zahlen.
Ggf. nur als 32Bit in XP/Vista (ohne DEP) lauffähig, an einer Version die auf allen BS läuft wird zzt gerade gearbeitet.

Spoiler anzeigen

[autoit]

#include <Array.au3>
#include <FASM.au3>

[/autoit] [autoit][/autoit] [autoit]

Local $ASM = FasmInit()
Local $maximum = 1299709

[/autoit] [autoit][/autoit] [autoit]

$t = TimerInit()
$primzahlen = _PrimeAsm($maximum) ;Assembler aufrufen, code assemblieren, in den Speicher schreiben und ausführen
$m = TimerDiff($t)

[/autoit] [autoit][/autoit] [autoit]

StringReplace($primzahlen, @CR, @CR, 0, 1) ;alle CR im String zählen.....auch AutoIt hat SPEEEEED^^
$anzahlprim = @extended ;hätte man auch vom Assembler zurückgeben lassen können^^
MsgBox(262144, "Primzahlen bis " & $maximum, $anzahlprim & " Primzahlen in " & Int($m) & " Millisekunden, Ausgabe der Zahlen folgt in Console....")
ConsoleWrite($primzahlen & @CRLF)

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

FasmExit($ASM)
Exit

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _PrimeAsm($limit) ;coded by Andy

[/autoit] [autoit][/autoit] [autoit]

FasmReset($ASM)

[/autoit] [autoit][/autoit] [autoit]

FasmAdd($ASM, "use32");32Bit-Version
FasmAdd($ASM, " push ebp "); ebp des aufrufenden Programms retten
FasmAdd($ASM, " mov ebp, dword[ESP+08h] "); "unseren" ebp setzen auf den Anfang unserer Struct
;dann ist...
; [EBP+0h] der erste Parameter (Limit) , da UINT ist er 4 Bytes lang, daher ist der nächste Parameter bei...
; [EBP+04h] der 2 Parameter (Limes), auch 4 Byte lang...daher findet man den 3. Parameter, unsere struct bei...
; [EBP+08h] der Anfang des Speicherbereichs Mem
;ich verwende die Hex-Zahlen, um bei verschiedenen Assemblern einen Standard zu haben, der Windowstaschenrechner ist Gold wert^^

[/autoit] [autoit][/autoit] [autoit]

FasmAdd($ASM, " mov ebx,dword[ebp+0h] "); Limit
FasmAdd($ASM, " mov eax,3 "); 3 ist die nächste Primzahl
FasmAdd($ASM, "Fill: "); Schleifenanfang
FasmAdd($ASM, " mov dword[ebp+08h+eax],30313031h "); an die Speicherstelle in der Struct den String "1010"
FasmAdd($ASM, " add eax,4 "); eax=eax+4 ;geht auch mit einem rep stosw^^ 10
FasmAdd($ASM, " cmp eax,ebx "); vergleiche eax mit $limit
FasmAdd($ASM, " jbe Fill "); Jump if below or equal (wenn <=) nach Fill, ansonsten weiter
;in der struct steht nun 001101010101010101010.....alle vielfachen von 2 sind 0, die erste 0 ist die 0, 2 ist die erste Primzahl!

[/autoit] [autoit][/autoit] [autoit]

;startadresse Struct Prim holen
FasmAdd($ASM, " mov edi, ebp "); an ebp steht der erste Parameter, wir brauchen aber die Adresse von ebp+8
FasmAdd($ASM, " add edi, 8 "); ebp+8 ist die adresse des ersten bytes der struct Mem
FasmAdd($ASM, " mov esi, edi "); ESI=anfang Mem
FasmAdd($ASM, " mov ecx,dword[EBP+0h] "); do until limit
FasmAdd($ASM, " mov ebx,3 "); ebx=aktuelle Zahl in der struct struct[1]=speicher[0] !!!!!!
FasmAdd($ASM, "L0: ")
FasmAdd($ASM, " mov eax,ebx "); eax=ebx=aktuelle primzahl
FasmAdd($ASM, " mul eax ");nächstes vielfaches der prim = quadrat der primzahl
;****************************************
;ACHTUNG, das Erbebnis von mul ist EDX:EAX also wird auch das edx-register verändert!
;*****************************************
FasmAdd($ASM, "L1: ")
FasmAdd($ASM, " mov byte[esi+eax],30h ");jedes vielfache der Primzahl in der struct zu "0" machen
FasmAdd($ASM, " add eax,ebx ");eax=eax+ebx vielfaches der Primzahl 20
FasmAdd($ASM, " cmp eax,ecx "); Vielfaches mit limit vergleichen
FasmAdd($ASM, " jl L1 "); solange eax < limit, die Vielfachen löschen
FasmAdd($ASM, "L2: ");nächste Primzahl holen
FasmAdd($ASM, " add ebx,2 ");2 zahlen weiter springen ,3,5,7,9,11,13,15....
FasmAdd($ASM, " cmp ebx,dword[EBP+0h] "); vgl aktuelle position mit dem Ende von Mem
FasmAdd($ASM, " ja exit ");wenn Ende erreicht, exit
FasmAdd($ASM, " cmp byte[esi+ebx],31h ");ist an dieser stelle in der struct eine primzahl?
FasmAdd($ASM, " jne L2 ");wenn nicht, nächste zahl wählen
;************************************************************
;aus einer Zahl(Registerinhalt) einen ZiffernString machen: http://dcla.rkhb.de/umwandlung/int2dez.html
;und in die Primstruct schreiben
;wird dieser Bereich auskommentiert, wird ein String aus nullen und einsen zurückgegeben 0=keine Prim 1=Prim
;dann können mit den AutoIt-Stringbefehlen die Primzahlen und deren Anzahl ausgelesen werden
FasmAdd($ASM, " push ebx ");alle benötigten Register sichern
FasmAdd($ASM, " push ecx ");alle benötigten Register sichern
FasmAdd($ASM, " mov eax, ebx ");Zahl laden
FasmAdd($ASM, " mov ebx, 10 "); Divisor
FasmAdd($ASM, " xor ecx, ecx ");ECX=0 (Anzahl der Ziffern)
FasmAdd($ASM, "Schleife_1: ")
FasmAdd($ASM, " xor edx, edx ")
FasmAdd($ASM, " div ebx "); EDX:EAX / EBX = EAX Rest EDX
FasmAdd($ASM, " push dx "); LIFO
FasmAdd($ASM, " add cl,1 "); ADD soll schneller sein als INC
FasmAdd($ASM, " or eax, eax "); AX = 0?
FasmAdd($ASM, " jnz Schleife_1 "); nein: nochmal
FasmAdd($ASM, "Schleife_2: ")
FasmAdd($ASM, " pop ax "); gepushte Ziffern zurückholen
FasmAdd($ASM, " or al, 00110000b "); Umwandlung in ASCII
FasmAdd($ASM, " stosb "); Nur AL nach [EDI] (EDI ist ein Zeiger auf den String)
FasmAdd($ASM, " loop Schleife_2 "); bis keine Ziffern mehr da sind
FasmAdd($ASM, " mov byte [edi],0Dh ");CR CarriageReturn, man könnte auch ein Komma (ascii=2C) einsetzen, dazu noch ein nullbyte als EndOfString
FasmAdd($ASM, " add edi,1 ");ein Byte weiter
FasmAdd($ASM, " pop ecx ");Register wiederherstellen
FasmAdd($ASM, " pop ebx ");Register wiederherstellen
;************************************************************Ende Ziffer aus Register

[/autoit] [autoit][/autoit] [autoit]

FasmAdd($ASM, " cmp ebx,dword[EBP+04h] "); vgl aktuelle position mit der wurzel der listengrösse
FasmAdd($ASM, " jl L0 "); solange ebx < wurzel listengrösse, gehe vielfache eliminieren

[/autoit] [autoit][/autoit] [autoit]

;jetzt ist die Mem-Struct völlig gefüllt aber die Primzahlen sind nur bis Limes in der Prim-Struct!
;also muss der Rest auch noch eingetragen werden
FasmAdd($ASM, " cmp ebx,dword[EBP+0h] "); vgl aktuelle position mit dem Ende von Mem
FasmAdd($ASM, " jl L2 "); solange ebx < limit, gehe vielfache eliminieren bzw "1"en in zifferfolgen umwandeln

[/autoit] [autoit][/autoit] [autoit]

FasmAdd($ASM, "exit: ");
FasmAdd($ASM, " mov byte [edi],00h ");nullbyte als EndOfString anfügen, damit hinter den Zahlen nicht die übrigen 0en und 1en stehen
FasmAdd($ASM, " pop ebp "); ebp des aufrufenden Programms restaurieren
FasmAdd($ASM, " ret "); und zurück, in eax steht das Ergebnis

[/autoit] [autoit][/autoit] [autoit]

$tStruct = DllStructCreate("uint Limit;uint Limes;char Mem[" & $limit + 10 & "]") ;char, dann kann man nachher schön mit den stringfunktionen suchen
DllStructSetData($tStruct, "Mem", "001") ;die ersten 3 Zahlen setzen, 0=0 1=0 2=1 , 2 ist die erste Primzahl
DllStructSetData($tStruct, "Limit", $limit);limit in die Struct schreiben
DllStructSetData($tStruct, "Limes", Floor(Sqrt($limit)) + 1);wurzel aus limit in die struct schreiben

[/autoit] [autoit][/autoit] [autoit]

$Ret = MemoryFuncCall("int:cdecl", FasmGetFuncPtr($ASM), "ptr", DllStructGetPtr($tStruct)); Assembler aufrufen
$pstring = "2" & @CR & "3" & @CR ;2 und 3 sind die ersten Primzahlen
$pstring &= DllStructGetData($tStruct, "Mem") ;alle Primzahlen aus der struct in den string schreiben

[/autoit] [autoit][/autoit] [autoit]

Return $pstring ;und zurückgeben

[/autoit] [autoit][/autoit] [autoit]

EndFunc ;==>_PrimeAsm

[/autoit]

Und natürlich für den Wettbewerb der AutoItcode, leider sind unter AutoIt alle "schnellen" Algorithmen langsamer als ein simples Bruteforce... ..oder überrascht mich^^
autoit.de/wcf/attachment/8457/

RAPTOR-ONE

So bevor ich es vergesse lade ich meine beiden Versionen noch schnell hoch
Passwort: Prim

Magnus

Zitat von Andy

Wenn wir schon dabei sind^^
Dann zeige ich auch mal meine ASM-Version, incl. Umwandlung der Register in Zahlen.
Ggf. nur als 32Bit in XP/Vista (ohne DEP) lauffähig, an einer Version die auf allen BS läuft wird zzt gerade gearbeitet.

Spoiler anzeigen

[autoit]
#include <Array.au3>
#include <FASM.au3>
[/autoit] [autoit][/autoit] [autoit]
Local $ASM = FasmInit()
Local $maximum = 1299709
[/autoit] [autoit][/autoit] [autoit]
$t = TimerInit()
$primzahlen = _PrimeAsm($maximum) ;Assembler aufrufen, code assemblieren, in den Speicher schreiben und ausführen
$m = TimerDiff($t)
[/autoit] [autoit][/autoit] [autoit]
StringReplace($primzahlen, @CR, @CR, 0, 1) ;alle CR im String zählen.....auch AutoIt hat SPEEEEED^^
$anzahlprim = @extended ;hätte man auch vom Assembler zurückgeben lassen können^^
MsgBox(262144, "Primzahlen bis " & $maximum, $anzahlprim & " Primzahlen in " & Int($m) & " Millisekunden, Ausgabe der Zahlen folgt in Console....")
ConsoleWrite($primzahlen & @CRLF)
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
FasmExit($ASM)
Exit
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Func _PrimeAsm($limit) ;coded by Andy
[/autoit] [autoit][/autoit] [autoit]
FasmReset($ASM)
[/autoit] [autoit][/autoit] [autoit]
FasmAdd($ASM, "use32");32Bit-Version
FasmAdd($ASM, " push ebp "); ebp des aufrufenden Programms retten
FasmAdd($ASM, " mov ebp, dword[ESP+08h] "); "unseren" ebp setzen auf den Anfang unserer Struct
;dann ist...
; [EBP+0h] der erste Parameter (Limit) , da UINT ist er 4 Bytes lang, daher ist der nächste Parameter bei...
; [EBP+04h] der 2 Parameter (Limes), auch 4 Byte lang...daher findet man den 3. Parameter, unsere struct bei...
; [EBP+08h] der Anfang des Speicherbereichs Mem
;ich verwende die Hex-Zahlen, um bei verschiedenen Assemblern einen Standard zu haben, der Windowstaschenrechner ist Gold wert^^
[/autoit] [autoit][/autoit] [autoit]
FasmAdd($ASM, " mov ebx,dword[ebp+0h] "); Limit
FasmAdd($ASM, " mov eax,3 "); 3 ist die nächste Primzahl
FasmAdd($ASM, "Fill: "); Schleifenanfang
FasmAdd($ASM, " mov dword[ebp+08h+eax],30313031h "); an die Speicherstelle in der Struct den String "1010"
FasmAdd($ASM, " add eax,4 "); eax=eax+4 ;geht auch mit einem rep stosw^^ 10
FasmAdd($ASM, " cmp eax,ebx "); vergleiche eax mit $limit
FasmAdd($ASM, " jbe Fill "); Jump if below or equal (wenn <=) nach Fill, ansonsten weiter
;in der struct steht nun 001101010101010101010.....alle vielfachen von 2 sind 0, die erste 0 ist die 0, 2 ist die erste Primzahl!
[/autoit] [autoit][/autoit] [autoit]
;startadresse Struct Prim holen
FasmAdd($ASM, " mov edi, ebp "); an ebp steht der erste Parameter, wir brauchen aber die Adresse von ebp+8
FasmAdd($ASM, " add edi, 8 "); ebp+8 ist die adresse des ersten bytes der struct Mem
FasmAdd($ASM, " mov esi, edi "); ESI=anfang Mem
FasmAdd($ASM, " mov ecx,dword[EBP+0h] "); do until limit
FasmAdd($ASM, " mov ebx,3 "); ebx=aktuelle Zahl in der struct struct[1]=speicher[0] !!!!!!
FasmAdd($ASM, "L0: ")
FasmAdd($ASM, " mov eax,ebx "); eax=ebx=aktuelle primzahl
FasmAdd($ASM, " mul eax ");nächstes vielfaches der prim = quadrat der primzahl
;****************************************
;ACHTUNG, das Erbebnis von mul ist EDX:EAX also wird auch das edx-register verändert!
;*****************************************
FasmAdd($ASM, "L1: ")
FasmAdd($ASM, " mov byte[esi+eax],30h ");jedes vielfache der Primzahl in der struct zu "0" machen
FasmAdd($ASM, " add eax,ebx ");eax=eax+ebx vielfaches der Primzahl 20
FasmAdd($ASM, " cmp eax,ecx "); Vielfaches mit limit vergleichen
FasmAdd($ASM, " jl L1 "); solange eax < limit, die Vielfachen löschen
FasmAdd($ASM, "L2: ");nächste Primzahl holen
FasmAdd($ASM, " add ebx,2 ");2 zahlen weiter springen ,3,5,7,9,11,13,15....
FasmAdd($ASM, " cmp ebx,dword[EBP+0h] "); vgl aktuelle position mit dem Ende von Mem
FasmAdd($ASM, " ja exit ");wenn Ende erreicht, exit
FasmAdd($ASM, " cmp byte[esi+ebx],31h ");ist an dieser stelle in der struct eine primzahl?
FasmAdd($ASM, " jne L2 ");wenn nicht, nächste zahl wählen
;************************************************************
;aus einer Zahl(Registerinhalt) einen ZiffernString machen: http://dcla.rkhb.de/umwandlung/int2dez.html
;und in die Primstruct schreiben
;wird dieser Bereich auskommentiert, wird ein String aus nullen und einsen zurückgegeben 0=keine Prim 1=Prim
;dann können mit den AutoIt-Stringbefehlen die Primzahlen und deren Anzahl ausgelesen werden
FasmAdd($ASM, " push ebx ");alle benötigten Register sichern
FasmAdd($ASM, " push ecx ");alle benötigten Register sichern
FasmAdd($ASM, " mov eax, ebx ");Zahl laden
FasmAdd($ASM, " mov ebx, 10 "); Divisor
FasmAdd($ASM, " xor ecx, ecx ");ECX=0 (Anzahl der Ziffern)
FasmAdd($ASM, "Schleife_1: ")
FasmAdd($ASM, " xor edx, edx ")
FasmAdd($ASM, " div ebx "); EDX:EAX / EBX = EAX Rest EDX
FasmAdd($ASM, " push dx "); LIFO
FasmAdd($ASM, " add cl,1 "); ADD soll schneller sein als INC
FasmAdd($ASM, " or eax, eax "); AX = 0?
FasmAdd($ASM, " jnz Schleife_1 "); nein: nochmal
FasmAdd($ASM, "Schleife_2: ")
FasmAdd($ASM, " pop ax "); gepushte Ziffern zurückholen
FasmAdd($ASM, " or al, 00110000b "); Umwandlung in ASCII
FasmAdd($ASM, " stosb "); Nur AL nach [EDI] (EDI ist ein Zeiger auf den String)
FasmAdd($ASM, " loop Schleife_2 "); bis keine Ziffern mehr da sind
FasmAdd($ASM, " mov byte [edi],0Dh ");CR CarriageReturn, man könnte auch ein Komma (ascii=2C) einsetzen, dazu noch ein nullbyte als EndOfString
FasmAdd($ASM, " add edi,1 ");ein Byte weiter
FasmAdd($ASM, " pop ecx ");Register wiederherstellen
FasmAdd($ASM, " pop ebx ");Register wiederherstellen
;************************************************************Ende Ziffer aus Register
[/autoit] [autoit][/autoit] [autoit]
FasmAdd($ASM, " cmp ebx,dword[EBP+04h] "); vgl aktuelle position mit der wurzel der listengrösse
FasmAdd($ASM, " jl L0 "); solange ebx < wurzel listengrösse, gehe vielfache eliminieren
[/autoit] [autoit][/autoit] [autoit]
;jetzt ist die Mem-Struct völlig gefüllt aber die Primzahlen sind nur bis Limes in der Prim-Struct!
;also muss der Rest auch noch eingetragen werden
FasmAdd($ASM, " cmp ebx,dword[EBP+0h] "); vgl aktuelle position mit dem Ende von Mem
FasmAdd($ASM, " jl L2 "); solange ebx < limit, gehe vielfache eliminieren bzw "1"en in zifferfolgen umwandeln
[/autoit] [autoit][/autoit] [autoit]
FasmAdd($ASM, "exit: ");
FasmAdd($ASM, " mov byte [edi],00h ");nullbyte als EndOfString anfügen, damit hinter den Zahlen nicht die übrigen 0en und 1en stehen
FasmAdd($ASM, " pop ebp "); ebp des aufrufenden Programms restaurieren
FasmAdd($ASM, " ret "); und zurück, in eax steht das Ergebnis
[/autoit] [autoit][/autoit] [autoit]
$tStruct = DllStructCreate("uint Limit;uint Limes;char Mem[" & $limit + 10 & "]") ;char, dann kann man nachher schön mit den stringfunktionen suchen
DllStructSetData($tStruct, "Mem", "001") ;die ersten 3 Zahlen setzen, 0=0 1=0 2=1 , 2 ist die erste Primzahl
DllStructSetData($tStruct, "Limit", $limit);limit in die Struct schreiben
DllStructSetData($tStruct, "Limes", Floor(Sqrt($limit)) + 1);wurzel aus limit in die struct schreiben
[/autoit] [autoit][/autoit] [autoit]
$Ret = MemoryFuncCall("int:cdecl", FasmGetFuncPtr($ASM), "ptr", DllStructGetPtr($tStruct)); Assembler aufrufen
$pstring = "2" & @CR & "3" & @CR ;2 und 3 sind die ersten Primzahlen
$pstring &= DllStructGetData($tStruct, "Mem") ;alle Primzahlen aus der struct in den string schreiben
[/autoit] [autoit][/autoit] [autoit]
Return $pstring ;und zurückgeben
[/autoit] [autoit][/autoit] [autoit]
EndFunc ;==>_PrimeAsm
[/autoit]

Und natürlich für den Wettbewerb der AutoItcode, leider sind unter AutoIt alle "schnellen" Algorithmen langsamer als ein simples Bruteforce... ..oder überrascht mich^^
autoit.de/wcf/attachment/8457/

Alles anzeigen

Wo gibt es denn die FASM-Include?

Edit: Gefunden

**eukalyptus**

Hier ist mein Beitrag.

sind insg. 4 Versionen, wobei ich eigentlich nur die erste für den Contest relevant halte.

Version 1:
Algo zum ermitteln beliebig vieler Primzahlen ohne vorher definierte Obergrenze.
Eine Zahl, welche durch keine der kleineren Primzahlen teilbar ist, ist eine Primzahl.
Normalerweise bedient man sich hierbei der Mod-Funktion, es gibt aber auch die sogenannte Summierungsmethode, die etwas schneller ist weil sie nur mit Additionen rechnet.
Leider ist die Summierungsmethode in AutoIt langsamer als Modulo!
Durch Tests hab ich herausgefunden, daß IsInt($iN / $aP[$i]) schneller ist als Not Mod($iN , $aP[$i])

Spoiler anzeigen

[autoit]

Global $iCnt = InputBox("Wieviele Primzahlen?", "Wieviele Primzahlen sollen gefunden werden?", "100000")

[/autoit] [autoit][/autoit] [autoit]

Global $Timer = TimerInit()
_Loesungsfunktion($Timer, $iCnt)

[/autoit] [autoit][/autoit] [autoit]

Func _Loesungsfunktion(ByRef $Timer, $iM = 100000)
Local $aP[16777215], $iC = 1, $iN = 3, $iS, $iDiff
$aP[0] = 2
$aP[1] = 3
While $iC < $iM
$iN += 2
$iS = Sqrt($iN)
For $i = 1 To $iC
If $aP[$i] > $iS Then ExitLoop
If IsInt($iN / $aP[$i]) Then ContinueLoop 2
Next
$iC += 1
$aP[$iC] = $iN
WEnd
$iDiff=TimerDiff($Timer)
MsgBox(0, "", "Zeit: " & $iDiff & @LF & "Ausgabe erfolgt in Console")
For $i = 0 To $iM - 1
ConsoleWrite($aP[$i] & @CRLF)
Next
EndFunc ;==>_Loesungsfunktion

[/autoit]

Version 2:
Stinknormales Sieb des Eratosthenes mit wohl definierter Obergrenze
Eigentlich sinnlos für die gestellte Aufgabe "finde die ersten 100000 Primzahlen", aber für "finde alle Primzahlen bis 1299710" super geeignet.
Diese Version hab ich optimiert, wo es nur geht.
Auch das "Auslesen" des Arrays findet erst bei der Ausgabe statt

Spoiler anzeigen

[autoit]

Global $Timer = TimerInit()
_Loesungsfunktion($Timer)

[/autoit] [autoit][/autoit] [autoit]

Func _Loesungsfunktion(ByRef $Timer)
Local $hF, $aN[1299709 + 1], $iDiff
For $i = 2 To 1141
If Not $aN[$i] Then
For $j = $i * $i To 1299709 Step $i
$aN[$j] = 1
Next
EndIf
Next
$iDiff=TimerDiff($Timer)
MsgBox(0, "", "Zeit: " & $iDiff & @LF & "Ausgabe erfolgt in Console")
For $i = 2 To 1299709
If Not $aN[$i] Then ConsoleWrite($i & @CRLF)
Next
EndFunc ;==>_Loesungsfunktion

[/autoit]

Version 3 und 4 sind nicht für den Contest gedacht!
Version 3 verwendet den gleichen Algo, wie Version 1, allerdings in FreePascal programmiert und via DllCall aufgerufen.
Man sieht eindrucksvoll den Geschwindigkeitsunterschied zwischen Pascal und AutoIt...
Version 4 ist der selbe Algo wie Version 2 als FreePascal-Dll.
Auch nicht für den Contest, aber als direkter Konkurrent zu den ASM-Versionen

ZIP-Passwort:

Code

AP#n6OiHIu4A

E

**Schnitzel**

Und hier noch meine Version.
Leider nicht sonderlich optimiert wegen Zeitmangel aber dabeisein ist alles

Hat echt Spaß gemacht

Passwort gibts morgen früh

Passwort

S1cµhlniigthzte1l

Edit:
Achja zu werten ist egtl die Version1. Nur falls die in euren augen nicht regelkonform ist dann gilt version 2

**Andy**

Hi,
2 weitere "langsame" Funktionen...
Beide nutzen komprimierte Siebe, leider kann man mit AutoIt damit keinen Blumenpott gewinnen...(Nicht die Schuld von AutoIt, wer mit einem Ferrari zum Einkaufen fährt und sich über den mangelnden Platz für die 4 Kisten Bier beschwert ist selbst schuld^^)
Das "Sieb von Atkin" u.A. ist eine sehr schnelle Implementation zur Ermittlung großer Primen.

Bei anderen Wettbewerben zur Primzahlbestimmung habe ich festgestellt, daß die "Geschwindigkeit" nicht für die gesamte Laufzeit, sondern für die verschiedenen Bereiche des Programms ausgewertet wird, für z.B. Initialisierung, Primzahlbestimmung (Filterung/Berechnung) und der Ausgabe der Zahlen....egal, es hat mir jedenfalls richtig Spass gemacht!
Beispiel für komprimiertes Sieb:
In Assembler gibt es eine wesentlich schnellere Alternative zu MOD und Division, wenn der Teiler (hier bei uns wird durch 30 geteilt) bekannt ist. Da auch relativ wenig Speicher erforderlich ist, können die Siebe im Cache liegen und extrem schnell abgearbeitet werden.

Spoiler anzeigen

[autoit]

#include <String.au3>
#include <Array.au3>
;Sieb von Eratosthenes, komprimiert
;
Global $z
Global $limit = 1299709 ;alle Primzahlen bis zum Limit finden

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$arraysize = (Int($limit / 30) + 1) * 8 ;Array zur Aufnahme der möglichen Primzahlen, alle Vielfachen von 2,3 und 5 werden nicht berücksichtigt
Dim $a[$arraysize]
;der Vorteil ist, man braucht nur 1/4 des Speicherplatzes für das Sieb

[/autoit] [autoit][/autoit] [autoit]

;es werden in diesem komprimierten Sieb alle Vielfachen von 2,3 und 5 nicht berücksichtigt, daraus ergibt sich eine "Matrix" mit möglichen Primzahlen
;Zahlen Spalte
; 0 1 2 3 4 5 6 7
;Zeile
;0 1 7 11 13 17 19 23 29 in dieser Zeile stehen die Spaltenindizes
;1 31 37 41 43 47 49 53 59
;2 61 67 71 73 77 79 83 89
;3 91 97
; Formel zur Berechnung der möglichen Primzahlen:
; Prim = Zeilenanzahl * 30 + Spaltenindex Spaltenindex(0)=1 usw...
Dim $spaltenindex[8] ;
$spaltenindex[0] = 1
$spaltenindex[1] = 7
$spaltenindex[2] = 11
$spaltenindex[3] = 13
$spaltenindex[4] = 17
$spaltenindex[5] = 19
$spaltenindex[6] = 23
$spaltenindex[7] = 29

[/autoit] [autoit][/autoit] [autoit]

;dann folgt ein Array, in dem die Spaltenindizes(+1) den Primzahlen von 0-30 zugeordnet werden
Dim $b[31] = [0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 4, 0, 0, 0, 5, 0, 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 8, 0]
;jede Vielfache der Primzahl soll aus der Matrix eliminiert werden, in der Matrix stehen aber nur Vielfache der Primen von 7 bis 29
;also wird nur die Zahl aus der Matrix eliminiert, bei der gilt:
;$b[Rest] <> 0 wobei Rest = mod ( Vielfaches der Prim , 30 )
;
;die Vielfachen der Primzahlen werden eliminiert, indem an ihre Position in der Matrix eine Zahl (zur Verdeutlichung das Vielfache) geschrieben wird
;Ist das Sieb fertiggestellt, sind die Arrayelemente mit 0 die Primzahlen, alle anderen sind eliminierte Vielfache

[/autoit] [autoit][/autoit] [autoit]

$tt = TimerInit()

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$a[1]=1
$flag = 0
$primstring = ""

[/autoit] [autoit][/autoit] [autoit]

For $x = 0 To $arraysize ;Anzahl aller möglichen Primzahlen in der Matrix
For $y = 0 To 7 ;jedes Element in der Zeile
If $a[$y + 1 + ($x * 8)]<>0 Then ContinueLoop ;nur Elemente mit 0 sind Primzahlen
$prim = $x * 30 + $spaltenindex[$y] ;das ist die Primzahl
$qprim = $prim ^ 2 ;alle Vielfachen ab dem Quadrat dieser Primzahl eliminieren...
If $qprim > $limit Then ExitLoop 2 ;wenn Quadrat der Primzahl > Wurzel aus limit, dann besteht das sieb nur noch aus Primzahlen
$r = Mod($qprim, 30) ;mod der Zahl liefert den Rest
$d = Int($qprim / 30) ;int/30 liefert die Zeile der Zahl
If $b[$r] <> 0 Then ;wenn Zahl ein Vielfaches eines der Spaltenindizes, dann alle weiteren Vielfachen eliminieren
$a[$b[$r] + ($d * 8)] = $prim ;Im Arraydisplay sieht man sehr schön die eliminierten Vielfachen
$t=timerinit()
$w=0
For $m = $qprim To $limit Step $prim ;alle Vielfachen aus der Matrix eliminieren
$r = Mod($m, 30)
$d = Int($m / 30)
If $b[$r] <> 0 Then
$a[$b[$r] + ($d * 8)] = $prim
EndIf
$w+=1 ;anzahl eliminierter Zahlen = Vielfache der Prim
Next
$m=timerdiff($t)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $m = ' &$prim&" "&$w&" "& $m & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
endif
Next
Next

[/autoit] [autoit][/autoit] [autoit]

$m = TimerDiff($tt)
Msgbox(0,"Komprimiertes Sieb von Eratosthenes"," Primzahlen in "&int($m)&" Millisekunden!" & @CRLF &"Bitte im Anschluss kurz auf das Arraydisplay warten....")
_ArrayDisplay($a)
$primstring = "2" & @CRLF & "3" & @CRLF & "5" & @CRLF
$n = 3
For $i = 1 To $arraysize - 2
If $a[$i + 1] = 0 Then ;Primzahl im Sieb gefunden
$r = Mod($i,
$d = Int($i /
$n += 1
$primstring &= $d * 30 + $spaltenindex[$r] & " " & $n & @CR ;Ausgabe der Primzahlen
EndIf
Next
ConsoleWrite($primstring)
Exit

[/autoit]

Sieb von Atkin:

Spoiler anzeigen

[autoit]

;Sieb von Atkin

[/autoit] [autoit][/autoit] [autoit]

$limit=1299709;10^8
global $struct=dllstructcreate("byte["&$limit&"]")
$t=timerinit()

[/autoit] [autoit][/autoit] [autoit]

$q=int(sqrt($limit))
for $x=1 to $q
for $y=1 to $q
$n=4*$x*$x+$y*$y
if $n<$limit and (mod($n,12)=1 or mod($n,12)=5) Then _flip($n)
$n=3*$x*$x+$y*$y
if $n<$limit and (mod($n,12)=7) Then _flip($n)
$n=3*$x*$x-$y*$y
if $x>$y and $n<$limit and (mod($n,12)=11) Then _flip($n)
Next
Next
$a=2
For $i=5 to $limit step 2
if dllstructgetdata($struct,1,$i)=1 Then
$e=$i*$i
$a+=1
for $z=$e to $limit step $i
dllstructsetdata($struct,1,0,$z)
next
EndIf
next
$m=timerdiff($t)
Msgbox(0,"Sieb von Atkin","Zeit für die Primzahlen bis "&$limit & @CRLF & int($m) &" Millisekunden")

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

for $i=1 to $limit
if dllstructgetdata($struct,1,$i)=1 Then consolewrite ($i & @CRLF )
next

[/autoit] [autoit][/autoit] [autoit]

func _flip($z)
if dllstructgetdata($struct,1,$z)=1 Then
dllstructsetdata($struct,1,0,$z)
else
dllstructsetdata($struct,1,1,$z)
EndIf
endfunc

[/autoit]

**UEZ**

Hier der Atkin's Code in einer nicht optimierten Version:

Spoiler anzeigen

[autoit]

Func Atkin_Prim_Calc($limes) ;using Atkin's algorithm
$limes += 1
Local $prime[$limes]
Local $i, $k, $n, $nn, $w, $x, $xx, $y, $yy, $prime_numbers
$w = Sqrt($limes)
For $x = 1 To $w
$xx = $x * $x ;x^2
For $y = 1 To $w

[/autoit] [autoit][/autoit] [autoit]

$yy = $y * $y ;y^2
$n = $xx + $xx + $xx + $xx + $yy ;4 * x^2 + y^2
If ($n < $limes) And (Mod($n, 12) = 1 Or Mod($n, 12) = 5) Then
If $prime[$n] Then
$prime[$n] = 0
else
$prime[$n] = 1
EndIf
EndIf

[/autoit] [autoit][/autoit] [autoit]

$n = $xx + $xx + $xx + $yy ;3 * x^2 + y^2
If $n < $limes And Mod($n, 12) = 7 Then
If $prime[$n] Then
$prime[$n] = 0
else
$prime[$n] = 1
EndIf
EndIf

[/autoit] [autoit][/autoit] [autoit]

$n = $xx + $xx + $xx - $yy ;4 * x^2 - y^2
If $x > $y And $n < $limes And Mod($n, 12) = 11 Then
If $prime[$n] Then
$prime[$n] = 0
else
$prime[$n] = 1
EndIf
EndIf

[/autoit] [autoit][/autoit] [autoit]

Next
Next

[/autoit] [autoit][/autoit] [autoit]

For $n = 5 To $w Step 2 ; Only odd numbers can be prime, no point in testing even numbers
If $prime[$n] Then
$nn = $n * $n
$k = 1
While $k * $nn < $limes
$prime[$k * $nn] = 0
$k += 1
WEnd
EndIf
Next

[/autoit] [autoit][/autoit] [autoit]

For $n = 3 To $limes - 1 Step 2
If $prime[$n] Then $prime_numbers &= $n & " "
Next
Return "2 " & $prime_numbers
EndFunc

[/autoit]

Der ist für AutoIt leider langsam!

Gruß,
UEZ

MatthiasG.

So! Der Wettbewerb ist beendet! Zum Schluss wurde das ja sogar Teamwork

Die Auswertung kann etwas dauern, dass mit dem ASM ist für mich neu.

Ich gebe dann noch bescheid und erstelle noch eine Liste mit allen Codes!

Vielen Dank für die doch recht große Teilnahme und frohe Ostern!

**Andy**

Hallo zusammen,

Ich möchte NICHT, daß die von mir vorgestellte Version mit dem "Embedded-Assembler" im Wettbewerb gewertet wird. Ich habe die Variante nur vorgestellt um zu zeigen, was mit einigen Zeilen Code auch in AutoIt Geschwindigkeitsmäßig machbar ist (obwohl es nach Optimierung auch noch ca. 100x schneller geht!).

Generell bin ich mit Blick auf die Zielgruppe des µIt-Light dafür, daß ausschliesslich die im Orginal AutoIt-Download enthaltenen Funktionen verwendet werden dürfen.Weiterhin sollten "selbstgeschriebene" Funktionen mit DLL-Calls z.B. der API nicht berücksichtigt werden.

Den µIt-Light habe ich immer als Ansporn für die Anfänger/ und "leicht" Fortgeschrittenen gesehen um an der Programmiertechnik und der Implementation von Algorithmen zu feilen (und um von den anderen zu lernen!). Und ich denke, so soll es auch bleiben....

MatthiasG.

Hallo Andy!

Herzlichen Dank für diese Einschätzung! Obwohl ich es wahrscheinlich mitbewertet hätte, da du dir ja immerhin die Mühe gemacht hast. Da habe ich es für falsch gehalten, zu sagen: "Nö, du nicht."

Aber wenn du damit einverstanden bist, lassen wir das natürlich.

Trotz allem nochmal herzlichen Dank!

Grüße aus dem Pott,
Matthias

MatthiasG.

Hallo allerseits!

Endlich ist die Auswertung des Wettbewerbs abgeschlossen. Zunächst herzlichen Dank für die rege Teilnahme! Die Skripte findet ihr im nächsten Post, hier die Awards! Generell zunächst ein paar Hinweise:

Ich habe nicht bei jedem Skript ohne Obergrenze aufgeschrieben, dass es keine gibt. Dies habe ich stellvertretend für alle anderen mal bei eukalyptus gemacht, da er auch so stolz darauf hingewiesen hatte
Ich habe zwar +/- hingeschrieben, hat man aber 2 - heißt das noch lange nicht, dass das Skript Minuspunkte hat. Ich habe dahinter nur Punkte notiert, die mir besonders aufgefallen sind. Ich habe versucht möglichst gute Hilfen zum Besser-Machen zu geben.
Auch wenn in der Wertung Konstrukte mit Pascal & Co aufgeführt werden, gibt es dafür natürlich keine Awards!
Ich habe versucht die Timer-Befehle möglichst passend zu integrieren. Veränderte Stellen sind markiert und ausgewiesen. Bitte Beschwerd euch bei Ungerechtigkeiten
Entschuldigt nochmals die Verzögerung!
Herzlichen dank an L3viathan für die Award-Bilder und den ganzen anderen Kram

So, hier aber nun zur Auswertung:

T1: Zeit bei niedriger Belastung (ms)
T2: Zeit bei durchschnittlicher Belastung (ms)
T3: Zeit bei großer Belastung (ms)
Td: Durschnittszeit (ms)

Andy:
Sieb von Atkin:
T1: 27522 T2: 47501 T3: 91859 Td: 55627
- 2 und 3 als Primzahlen werden nicht aufgeführt

Sieb von Eratosthenes:
T1: 9243 T2: 16261 T3: 30017 Td: 18507
+ gute Kommentierung
- Hält sich nicht an Limit, rechnet darüber hinaus (1 Zahl bei Messung)

eukalyptus:
Algorithmus1:
T1: 70906 T2: 133262 T3: 429165 Td: 211111
+ Keine Obergrenze (außer Grenzen von AutoIt)

Algorithmus2:
T1: 3260 T2: 10633 T3: 21005 Td: 11632

Algorithmus3 - Aus Wertung heraus genommen!:
T1: 733 T2: 1296 T3: 5213 Td: 2414
+ Sehr gute Performance!
- Pascal-Code

Algorithmus4 - Aus Wertung heraus genommen!:
T1: 32 T2: 50 T3: 125 Td: 69
+ Unglaubliche Performance!
- Pascal-Code, das in AutoIt wäre traumhaft

PrideRage:
T1: 130185 T2: 229274 T3: 573274 Td: 310911
- Du verbaust dir Zeit, habe durch Streichen des Dateizugriffs etwas gut gemacht. Generell: Greifst du oft hintereinander auf eine Datei zu, nutze erst FileOpen und abschließend FileClose, das gibt etwas Geschwindigkeit. Ansonsten: Recht simpel und kompakt, ABER: Suche immer nach Alternativen, denn so kommst du auf ressourcensparende, zeitsparende Algorithmen und genau das macht einen guten Algorithmus heute aus: Wenig Zeit und wenig Ressourcen!

RAPTOR-ONE:
Prim6-Algorithmus:
T1: 3481 T2: 6272 T3: 14019 Td: 7924

Prim30-Algorithmus:
T1: 3568 T2: 6530 T3: 13752 Td: 7950

Sprenger120:
T1: 5483 T2: 8925 T3: 16367 Td: 30775
- Der Algorithmus prüft nur, ob die Zahl durch 2, 3, 5 und/oder 7 teilbar ist. Was ist mit dem Rest der Zahlen? Dadurch werden auch Zahlen ausgegeben, die keine Primzahlen sind...

UEZ:
T1: 20609 T2: 31133 T3: 48247 Td: 33329
- 3 wird nicht berücksichtigt (s. Andy)

name22:
T1: > 10 min T2: > 10 min T3: > 10 min Td: > 10 min
- Die Ermittlung bis Sqrt(Mögliche Primzahl) reicht, du rechnest zu weit. Beispiel 25: Rechnung bis 5 reicht, keine Primzahl. Bei dir geht es aber bis 24! Verlust bei Primzahlen mit 6 Stellen...
- Habe das Skript nach 10 min abgebrochen

Schnitzel:
Skript 1:
T1: 1707 T2: 2871 T3: 6283 Td: 3620

Skript 2:
T1: 2830 T2: 6122 T3: 11676 Td: 6876

Schnuffel:
T1: 114305 T2: 184204 T3: 473092 Td: 514400

Preisverleihung:
Schnitzel und RAPTOR-ONE dürfen sich für ihre jeweils ersten Skripte Gewinner im Bezug auf Geschwindigkeit nennen:
autoit.de/wcf/attachment/10322/

Aufgrund seines relativ kompkaten Algorithmus, gewinnt PrideRange in der Kategorie "Kompaktheit":
autoit.de/wcf/attachment/10323/

Für den Rest gilt:
autoit.de/wcf/attachment/10321/
Das heißt nicht, dass Eure Algorithmen schlecht gewesen wären! Im Gegenteil! Ich bin überrascht gewesen, was es alles jenseits der klassischen Siebe gab! Alle Achtung! Vielleicht hat ja jemand Lust weiter zu optimieren um eine möglichst große Primzahl zu bekommen, hier schlage ich eine Datenbank vor. Und vielleicht als Grundlage die Pascal-Lösung von eukalyptus. Oder falls es rein AutoIt sein soll, ein klassisches Sieb nach Andy oder UEZ?

Herzlichen Glückwunsch und Dank an alle Teilnehmer!

Die Skripte werden wie erwähnt im nächsten Post hochgeladen.

Viele Grüße aus dem Pott,
Matthias

MatthiasG.

Da nicht alle Skripts in einen Beitrag passen (Größe + Dateianzahl), hier der erste Teil:

MatthiasG.

Und nun der letzte Teil, entschuldigt bitte die 3 aufeinanderfolgenden Posts!

Viele Grüße,
Matthias

**UEZ**

Hier die Auswertung auf meinem Notebook für feste 100.000 Primzahlen:

Code

100.000 Primzahlen
Schnitzel		3.89 s
Andy (SvA)		25.12 s
Andy (SvE)		9,01 s
Eukalyptus (Alg.2)	3,90 s
RAPTOR-ONE (6)		3,25 s
RAPTOR-ONE (30)		3,92 s
UEZ			3,97 s

Ich weiß nicht, warum du meinen Atkin Alg. genommen hast (war nur eine Variante)

Gruß,
UEZ