Python rechnet uneffizient?

[miracle173]

@Haolong:
Ich gehe davon aus, das das die Gesamtzeit im wesentlichen vom print-Statement bestimmt wird.
Es gibt ungefaehr n/ln(n) Primzahlen zwischen 1 und n, also etwa 138000 Primzahlen die kleiner als 2000000 sind. Dein Freund hat für die Ausgabe dieser Zahlen 25 Minuten gebraucht, das sind etwa 25*60/140000 Sekunden, also etwa 0.0109s=10,9ms.
Du hast 1500000 Zahlen ausgegeben. Würde dein Freund das machen, würde er dazu 1500000*0.0109s = 16350s benoetigen, das sind dann 16350/3600 h= 4.54h, als etwa 4,5 Stunden. Da is also nicht viel unterschied. Da du nach 4,5 Stunden 3/4 der Zahlen ausgedrückt hast, würde ich erwarten, dass du in 4.5*4/3= 6 Stunden fertig bist. Da du aber 7,5 Stunden benötigt hast, stimmten meine Annahmen nicht 100-prozentig.

• Alles in allem sieht man aber, dass man die Programme in verschiedenen Programmiersprachen nur sinnvoll vergleichen kann wenn sie auch wirklich das gleiche tun.
• Umfangreiche Ausgabe sollte man bei solchen Vergleichen vermeiden, da sie meistens die Gesamtausführungszeit dominiert und von vielen Faktoren/Hardwarekomponenten abhängt. Die Ausgabe auf ein Terminal ist dabei meistens noch wesentlich langsamer als die Ausgabe in eine Datei. Ist also eine umfangreiche Ausgabe unvermeidbar, sollte man sie in eine Datei umleiten. Dies kann bei den meisten Betriebssystemsn mit dem '>' Operator geschehen.
• Die Ausgabe von 2000000 Zeilen auf den Bildschirm erscheint sowieso nicht sinnvoll. Wenn du auf das Terminal schreibst, weil du wissen willst, wie weit dein Programm ist, dann gib nicht jede Zahl aus, sondern nur jede k-te Zahl. k sollte so gewählt sein, das nur jede Sekunden (oder noch seltener) eine Zahl ausgedruckt wird. Da eine Ausgabe bei dir etwa 10 ms dauert, hat das nur mehr vernachlässigbaren Einfluss (etwa 1%) auf die Gesamtausführungszeit. Da @BlackJack eine Ausführungszeit von 2 Minuten gemessen hat, kannst Du k=20000 wählen und erhälst dann etwa alle 1,2 Sekunden eine Ausgabe.

[Haolong]

Als ich mein Programm umgeschrieben hatte und so wie mein Kumpel nur die Primzahlen ausgegeben hatte, hat sich die Laufzeit des Programms jedoch nicht großartig verändert. (vielleicht 10 Minuten von 7,5 Stunden)

Ein entscheidender Punkt war das Abbrechen der Überprüfungen, nachdem erkannt wurde, dass die Zahl eine Primzahl ist. Das hat das Programm auf ca. Minuten runtergekürzt.

Wie schnell es bei meinem Kumpel gelaufen wäre, wenn er dasselbe gemacht hätte, weiß ich nicht.

[miracle173]

Hallo @Halong

Dann ist der print Befehl nicht der grösste Zeitfresser pro Iteration.
Ich habe nun beide Programme durchgesehen. Du schreibst "Ein entscheidender Punkt war das Abbrechen der Überprüfungen, nachdem erkannt wurde, dass die Zahl eine Primzahl ist". Ich denke, du meinst aber, "das Abbrechen der Überprüfungen, nachdem erkannt wurde, dass die Zahl keine Primzahl ist". Keine Primzahl ist sie, sobald sie durch eine Zahl aus der Liste teilbar ist. Tatsächlich kannst du aber auch erkennen, dass eine Zahl eine Primzahl ist, bevor du alle Zahlen der Liste durchprobiert hat. Eine Zahl n ist nähmlich dann schon eine Primzahl, wenn es keine Teiler kleiner als sqrt(n) hat. sqrt ist da die Wurzelfunktion , also entweder math.sqrt(n) oder n**.5 . Das verkürzt die Laufzeit noch weiter.
Und natürlich kannst du deinen Schleifen-range mit 3 beginnen und eine Schrittweite 2 nehmen, da du gerade Zahlen nicht überprüfen musst.

Das Javaprogramm hat einige Mängel. Double ist ein ungeeigneter Wert für i. Die Variable i ist eine ganze Zahl, man soll also int nehmen, und wenn das zu klein, was hier nicht der Fall ist, dann ist long eine Möglichkeit. Der Vergleich zahl==x ist auch äusserts schmerzaft, da hiere ein double mittles == verglichen wird. Das sollte nie geschehen. Sinnvollerweise sollte er einen modulus-Operator verwenden und nicht mit double herumspielen.

Intressant wäre es natürlich schon wenn ihr beide das gleichen Verfahren implementieren würdet, die sich wiederholdenden Printbefehle rausnehmt und dann die Laufzeit der Programme vergleicht.

[DerTürke]

Hi fallst du in der Lage bist Assembler Prozeduren ein zu binden, ich habe da leider keine Ahnung ob dies in Python möglich ist,
kannst du folgende Prozedur verwenden mit dieser Prozedur[codebox=asm file=Unbenannt.asm][/code] habe ich alle Primzahlen von 1-2.000.000 in weniger als 1 Sekunden ermitteln können.


[codebox=asm file=Unbenannt.asm];;; Checks if Value is PrimeValue
;;; Params: 1=Value
;;; RetValue = 0 false; 1 = true;
prcIsPrime PROC
PROLOG ; Makro ersetzen durch enter 0,0
push rdx

MOVE_PARAM r10, 1 ; Makro ersetzen durch mov r10, [rbp+8+1*8]
cmp r10, 01h
jz @NoPrime
cmp r10, 02h
jz @IsPrime
cmp r10, 03h
jz @IsPrime
cmp r10, 05h
jz @IsPrime
cmp r10, 07h
jz @IsPrime
mov r10, 2

@Weiter:
xor rdx, rdx
MOVE_PARAM rax, 1 ; ; Makro ersetzen durch mov rax, [rbp+8+1*8]
div r10
cmp rdx, 0
jz @NoPrime
inc r10
cmp r10, rax
jb @Weiter

@IsPrime:
mov rax, 01h ; IsPrime=true;
jmp @ExitProc

@NoPrime:
xor rax, rax

@ExitProc:
pop rdx
pop r10
EPILOG ; Makro ersetzen durch leave
ret
prcIsPrime ENDP[/code]

[DerTürke]

Sorry nochmal im ersten script, war der push r10 verschwunden hätte natürlich gravierende folgen gehapt
[codebox=asm file=Unbenannt.asm];;; Checks if Value is PrimeValue
;;; Params: 1=Value
;;; RetValue = 0 false; 1 = true;
prcIsPrime PROC
PROLOG
push r10
push rdx

MOVE_PARAM r10, 1
cmp r10, 01h
jz @NoPrime
cmp r10, 02h
jz @IsPrime
cmp r10, 03h
jz @IsPrime
cmp r10, 05h
jz @IsPrime
cmp r10, 07h
jz @IsPrime
mov r10, 2

@Weiter:
xor rdx, rdx
MOVE_PARAM rax, 1
div r10
cmp rdx, 0
jz @NoPrime
inc r10
cmp r10, rax
jb @Weiter

@IsPrime:
mov rax, 01h ; IsPrime=true;
jmp @ExitProc

@NoPrime:
xor rax, rax

@ExitProc:
pop rdx
pop r10
EPILOG
ret
prcIsPrime ENDP


;;; Converts HexValue into string LATIN_BASIC
;;; Params: 1=HexValue
;;; RetValue = Pointer to string
prcHexToString PROC
PROLOG

push rcx
push rdx
push r8
push rdi

xor rcx, rcx
mov r8, 0ah
MOVE_PARAM rax, 1
@Weiter:
xor rdx, rdx
idiv r8
add rdx, 0030h
push rdx
inc rcx
cmp rax, 0
jnz @Weiter

lea rdi, offset asmPtrHexToStringValue
@Weiter2:
pop rdx
mov word ptr[rdi], dx
inc rdi
inc rdi
dec rcx
cmp rcx, 0
jnz @Weiter2
mov rax, offset asmPtrHexToStringValue

pop rdi
pop r8
pop rdx
pop rcx
EPILOG
ret
prcHexToString ENDP[/code]

[BlackJack]

@DerTürke: Ist aber auch ineffizient. Halt nur schneller weil der Prozessor diesen ineffizienten Teil trotzdem sehr schnell erledigt. Je langsamer die CPU desto kleiner wird der Abstand zu einem Sieb in Python werden.

[DerTürke]

Im Unterschied zum Sieb des Eratosthenes,
muss man bei diesem Algorithmus nicht erst ein Feld von x Byte allokieren, sondern kann ganz gezielt eine Schleife von x-y durchlaufen und nur die ermittelten Primzahlen speichern.

Nur damit ich dass verstehe wo liegt denn hier genau die Ineffizienz ?
Vielleicht habe ich das Problem auch gar nicht verstanden

VG
DT

[DerTürke]

@BlackJack: Halt nur schneller weil der Prozessor diesen ineffizienten Teil trotzdem sehr schnell erledigt
Diesen Satz habe ich leider nicht ganz verstanden, hört sich fast wie ein Paradoxon an oder ?

VG
DT

[BlackJack]

@DerTürke: Die Ineffizienz liegt in der Anzahl der Divisionen die durchgeführt wird wenn man damit alle Primzahlen bis 2 Mio berechnet. Das ist deutlich mehr Arbeit als zum Beispiel beim Sieb des Eratosthenes. Oder auch bei dem Ansatz vom OP, wo nicht mehr durch alle, sondern nur durch die bisher gefundenen Primzahlen geteilt wird. *Der* Ansatz hat den Vorteil, dass man die Obergrenze bis zu der man berechnen möchte, nicht vorher kennen muss.

Wenn Du Deinen Ansatz in Python schreiben würdest, dann wäre der langsamer als die anderen Ansätze in diesem Thema. Deins ist nur schneller weil es nicht Bytecode ist, der von CPythons VM ausgeführt wird, sondern Maschinencode der vom Prozessor ausgeführt wird. Im Grunde hast Du da den schlechtesten Algorithmus umgesetzt, den man sich hierfür denken kann. So etwas kann man sich heutzutage oft erlauben, weil die Prozessoren in PCs schneller sind, als die meisten Leute das überhaupt brauchen, aber wenn man Deinen Ansatz für langsame Prozessoren in Assembler schreibt, kann es durchaus passieren, dass er von einem Sieb in einer dynamisch typisierten und ausgeführten Hochsprache überholt wird.

[DerTürke]

Hi BlackJack,

ich hatte nicht vor hier einen (neuen) Algorithmus dar zu legen, vielmehr wollte ich mit meinem Ansatz zeigen, das man auch sehr effizient ohne Speicher allokieren zu müssen ohne weiteres Primzahlen generieren kann.
Daher bitte ich um Nachsicht falls ich den Eindruck erweckt habe das meine Algorithmus besser sei, dies war nicht meine Absicht, dennoch habe ich mal mir die Mühe gemacht und folgendes herausgefunden.

Primzahlen bis hundert ermitteln:

Durch das Sieb = 270 Schritte erforderlich ( Adressbildung, Prüfung auf Marke ( true/false) ob bereits durch Ermittlung von Vielfachen dieser Wert quasi gelöscht wurde, falls nein müssen dann die Vielfachen ermittelt werden und quasi auf gelöscht setzten )

Durch meinen Algo. = 525 Schritte. ( Schleife 2-100; Jede zu Überprüfende Zahl hat -> SQRT(Zahl)-1 Divisionen).

D.h. mein Algo. ist also doppelt so langsam ( was die Schritte angeht ), dennoch was die Effizienz angeht momentan unschlagbar

Mann kann das Sieb des Eratosthenes natürlich auch in Assembler realisieren, habe ich aber Aufgrund der Speicherlast nicht gemacht,
falls für den Unwahrscheinlichsten Fall jemand mal die Primzahlen "Achtung aufgepasst" zwischen 5.000.000.000.000 und 5.000.000.000.100 ermitteln möchte,

dann muss das Sieb erst einmal folgendes erstellen

1.
Im optimalsten Fall würde man 1 Array erstellen welche exakt die Größe von 5.000.000.000.100 Byte ( Byte ist nun mal die kleinste Einheit die der Prozessor lesen kann ( Der Datenbus ist in x86 Architektur auf 32 Bit ausgelegt d.h. falls er 1 Byte lesen möchte macht er dies durch entsprechende Unterdrückungssignale an den Leitungen BE1-4, d.h. er liest eigentlich immer 4 Byte ein , und bei x64 ist der Datenbus dann schon auf 64 Bit vergrößert daher ist es sehr ratsam den Speicher auf DWORD / QWORD grenzen aus zu richten )
Das wären dann so ca. 5 GB Speicher die das Sieb benötigen würde.
Erschwerend kommt dann noch hinzu, dass man lediglich die Information gelöscht oder nicht gelöscht hinterlegen kann und man später beim einsammeln der Primzahlen den Schleifenindex verwenden muss um den Wert der Primzahl zu erhalten, ist aber durchaus einfach realisierbar.

2.
Im Ungünstigsten Fall wenn man den Wert im Array speichern möchte so muss man schon bis zu Zahl 2,xxx Milliarden 4 Byte und ab 2,xxx Milliarden 8 Byte ( Value Int32 / Value Int64) da die Grenze für Int32 bei etwas mehr als 2 Milliarden liegt muss man dann schon auf den nächst gößeren Int zurückgreifen. Hier würde man dann einfach den Wert im Array komplett auf 0 setzen und wüsste damit "keine Primzahl / keine Vielfachen zu ermitteln ".
Für dieses Vorgehen wären dann schon etwa 20GB für Int32 Werte + 40GB für Int64 Werte macht eine Summe von 60GB Gesamt.
Dies würde allerdings 2 Arrays benötigen da man ein Array nicht mit 2 verschiedenen Datentypen erstellen kann. D.h. zu Laufzeit kommt dann noch hinzu, dass man prüfen muss auf welches Array man zu zugreifen hat, oder man verwendet von Anfang an Int64 und hätte dann gerade mal 20 GB obendrauf also 80GB Gesamt.

3.
Noch ungünstiger wäre es wenn man eine dynamische Liste (CList, TList, List<Int64> usw.... ) verwenden würde hier hätte man zwar den Vorteil der dynamic aber am Anfang müsste noch mehr Speicher allokiert werden, des weiteren würde bei Streichungen die große Gefahr bestehen schnell aus dem Index der Liste heraus zu laufen usw.... ) Der Speicher würde allerdings (wenn man natürlich auch Freigabe (List.delete(), List->Delete() (HeapDestroy, VirtualFree) verbunden mit lästigem hin und her kopieren usw...) verwenden würde) am Ende nur noch aus den Primzahlen bestehen.

Man könnte natürlich auch eine MAP (Dictionary<Int64, Bool>) verwenden usw........

Bei meiner Variante entfällt das alles da oben und von der Geschwindigkeit kann ich sagen: Es war mir mit meinen rudimentären Möglichkeiten nicht möglich zu messen wie schnell dies erledigt war (unter einer sek. ) ( Ich hätte mir natürlich auch die Arbeit machen können und den RTSC programmieren , aber ich muss ja niemandem etwas beweisen. )

Das wollte ich nur noch mal kurz zur Effizienz bei der Ermittlung zu Primzahlen erwähnen, natürlich ist das Sieb gemessen an der Anzahl Schritte doppelt schnell aber alles andere ist Grotten schlecht.

Im übrigen mal nur so am Rande:
Wenn es um Primzahlen bis 50 geht, dann ist selbst bei Anzahl Schritte ( Vorgänge ) mein Algo. schneller
Sieb = 210 Schritte
Mein Algo. = 168 Schritte

Kippen tut dies alles erst ab der Zahl 66 ( also aller Primzahl von 2 - 66 ) ist mein Algo. schneller

Wie dem auch sei, es geht nicht um ein Wettbewerb ich wollte eigentlich nur zeigen das man sich nicht auf eine Sache versteifen sollte, ich persönlich bin seit mehr als 10 Jahre im .Net Umfeld und unter Win32 unterwegs, aber habe großen Spaß daran zu sehen was Compiler und Frameworks an bremsen sind gemessen zu direkter Hardware naher Programmierung.

Unser Trainer (Fußball in der Jugend) schimpfte immer mit uns wenn wir verloren hatten, er sagte immer das das Resultat entscheiden sei, es wäre überhaupt nichts Wert ,das wir super schönen Fußball gespielt hätten, damals fand ich das blöd von unserem Trainer, später habe ich verstanden.

VG
DT

[BlackJack]

@DerTürke: Du sagst Dein Algorithmus ist doppelt so langsam und was die Effizienz angeht momentan unschlagbar? Äh, jetzt sehe ich da einen Widerspruch. Und dann definierst Du einfach mal das Problem so um das es um Speichereffizienz geht. Tolle Wurst. Die zu lösende Aufgabe war Summe der Primzahlen bis 2.000.000.

5.000.000.000.100 Bytes sind nicht 5 GB sondern 5 TB. Hast Du Dich da jetzt bei den Nullen verzählt, oder den falschen SI-Präfix verwendet?

Das Array kann trotzdem kleiner gewählt werden. Ausser der Zwei ist jede gerade Zahl sicher nicht prim und in ein Byte passen 8 Ja/Nein-Informationen. Man käme also mit 0,3125 TB oder 312,5 GB hin. Oder gar nur 312,5 MB falls Du Dich bei der Zahl und nicht beim Präfix vertan hast.

Man sollte bei der Aufgabe ein 100-Zahlen-Fenster zu prüfen aber auch mit zwei deutlich kleineren Arrays auskommen können. Nämlich in dem man erst die Primzahlen bis zur Wurzel aus 5.000.000.000.100 siebt und die dann verwendet um aus den huntert grossen Zahlen die Primzahlen auszusieben. Das wären dann wenn man es einfach halten will und ein Byte pro Ja/Nein-Information verwendet knapp über zwei Megabyte für das erste Array und 100 Bytes für das zweite.

Was Du zur Geschwindigkeit sagen kannst, ist wie schon gesagt, dass Dein Prozessor einfach schnell genug ist, so dass die ineffiziente Lösung immer noch schnell genug ist. Lass das auf einem deutlich langsamen Rechner laufen, vielleicht auch auf einem Prozessor der keine Division in Hardware gegossen hat, und Du wirst merken, dass ein Sieb dort schneller ist.

Was Compiler als bremsen angeht: Deinen Algorithmus würde man in C oder Pascal oder einer ähnlichen Compilersprache schreiben. Da wird ziemlich sicher was rauskommen was deutlich schneller geschrieben ist, und auf Deinem Prozessor von der Laufzeit her ziemlich sicher nur schwer vom handgeschriebenen Assembler zu unterscheiden ist. Da hätte man dann schon eher anfangen müssen Befehle zu verwenden die die üblichen Compiler nicht nehmen. Beispielsweise SIMD-Befehle. Eine weitere, im Grunde einfache möglichkeit Deinen Ansatz zu beschleunigen ist verteilen auf mehr als einen Prozessor/Kern. Auch dass dürfte beispielweise in C oder Hochsprachen schneller und leichter formuliert sein als in Assembler.

Wenn es um Primzahlen bis 50, und ums Erbsen zählen geht, ist Dein Algorithmus trotzdem langsamer. Denn da sind Divisionen und Prozessoren wie der Motorola 6510 oder der Zilog 80 haben keine Division an Bord. Das muss mit den vorhandenen Befehlen ausprogrammiert werden, und ist deutlich langsamer als ein Sieb wo nur Additionen vorkommen. An den Randbedingungen solange drehen bis eine Lösung besser oder schlechter ist, kann ich auch. Ausgangsfrage bleibt trotzdem die Summe der Primzahlen bis 2 Millionen.

Dafür das es kein Wettbewerb ist, versuchst Du aber ziemlich krampfhaft zu gewinnen.

[Sirius3]

@DerTürke: es hat ja niemand behauptet, dass ein Sieb immer die beste Wahl wäre. Dein Assembler-Algorithmus geht übrigens immer bis n und nicht bis Wurzel n. Und auch wenn Du nur bis Wurzel n gehen würdest, hättest Du bei den Primzahlen bis 100 allein schon 50 mal Wurzel ziehen und 87 Divisionen. Beim Sieb sind das 0 mal Wurzel, 0 mal Division.

Wie Du auf die Schritte kommst und was die definiert sind, weiß ich nicht. Meine Messungen sind jedenfalls eindeutig:
Alles in allem braucht die primitive Primzahlsuche 1090 Takte, das Sieb nur 351.
Bei Primzahlen bis 50 sieht das auch nicht besser aus: 457 zu 124 Takte.
5000: 214.936 zu 23.846
5000000: 2.630.638.732 zu 135.426.641

[DerTürke]

Ok Leute also mir macht's super viel Spaß darüber zu sprechen

@BlackJack: du hasst recht ich habe mich um 3 Nullen vertan ( aber ich habe dies auch bei meiner Probe der Prozedur verwendet )

6510, 6502, 8510, und der Z80 stammen noch aus C64/C128 und "CPM Mallard" Zeiten die hatten tatsächlich nur ADC (Add with carry ) und SBC (subtract with carry) Befehle. Diese Prozessoren habe ich allerdings schon Ewigkeiten ( Ich hatte damals ein C116 kleiner Bruder von C64 und habe auch schon in ASM programmiert) nicht mehr gesehen, dennoch bin ich der Meinung solange ein Compiler BASIC, C, oder C++ nicht optimal in Maschinencode umsetzen kann wird die ASM Prozedur das Optimum sein. Und trotzdem konnte man auf 6502/6510 Prozessoren Multiplikationen ( mit Bitverschiebung ASL (arithmetic shift left) und bei Multiplikatoren welche nicht ein Vielfaches von 2 waren durch zusätzl. Addition des Restes) effizient durchführen. Das gleich galt auch für Divisionen LSR (Logical shift right) ( Programming 6502 von Rodnay Zaks Sybex Verlag ( nicht mehr erhältlich , falls jedoch jemand Interesse haben sollte ich habe auf jeden Fall noch ein Exemplar).

Also wie gehabt ich wollte keinen Algorithmus euch vorschlagen, wenn ich das z.B. in Python, wovon ich absolut keine Ahnung habe, hätte machen müssen dann hätte ich mit hoher Wahrscheinlichkeit auch das Sieb verwendet, allerdings hätte ich dann eine dyn. List<Int32> (Gibt's so was in Python ?)verwendet und diese quasi zur Laufzeit mit jedem gestrichenen Wert verkleinert das ich am Ende nur noch die Primzahlen hätte. Und wie du auch schon erwähnt hasst hätte ich von vornherein alle Zahlen dessen LSB = 0 einfach garnicht erst in die Liste genommen ( ausser der 2 natürlich ) Vom Algorithmus her wäre das dann noch eine Verbesserung zum normalen Sieb wo die Werte nur markiert werden und man prüfen muss ob dieser Wert in Frage kommt oder nicht. Aus dem Blickwinkel der Geschwindigkeit wäre dieses Vorgehen aber höchst wahrscheinlich langsamer als das ursprüngliche Sieb.

@Sirus3
Dadurch das sich bei jedem Schleifen durchlauf der Divisor (r10) gegenläufig zum Quotienten(rax) verhält und eine abbruch bei Divisor > Quotient erfolgt ergibt nach meiner Analyse ( muss ja nicht richtig sein du könntest mir ja deine mal aufschreiben wie du die Sache sieht ) für jede Zahl die zu überprüfen ist habe ich (Wurzel aus Zahl)-1 Divisionen durch zu führen. D.h ich ziehe nirgends im Code eine Wurzel.

Code: Alles auswählen

@Weiter:
	xor			rdx, rdx
	MOVE_PARAM	rax, 1
	div			r10
	cmp			rdx, 0
	jz			@NoPrime
	inc			r10
	cmp			r10, rax
	jb			@Weiter

Schritte beim Sieb

ÜZ Vielfache Gesamt Schritte
1 Schritt. 2 50 Schritte 51
2 Schritt. 3 33 Schritte 85
3 Schritt. 4 0 Schritte 86
4 Schritt. 5 20 Schritte 107
5 Schritt. 6 0 Schritte 108
6 Schritt. 7 14 Schritte 123
7 Schritt. 8 0 Schritte 124
8 Schritt. 9 0 Schritte 125
9 Schritt. 10 0 Schritte 126
10 Schritt. 11 9 Schritte 136
11 Schritt. 12 0 Schritte 137
12 Schritt. 13 7 Schritte 145

Schritt bedeutet : Index auf Array bilden, Prüfen ob Gelöscht oder nicht ( also ob man Vielfache ermitteln muss ), vielfache ermitteln (Wenn nötig).
Jetzt könntest du natürlich sagen Moment mal die Zahl 3 hat gar nicht so viele Schritte weil ja das Produkt 2x3 und das vielfache bereits durch die Vorherige Ermittlung gelöscht wurden, wie willst du das aber deiner Prozedur mitteilen das er diese nicht mehr prüfen muss. ( wenn du keine dyn. List verwendest ) Es sei denn du baust ein 2 Array mit allen bisher ermittelten vielfachen auf und prüfst vor deiner Prüfung ob die zu prüfende Zahl bereits in deinem Vielfach Array vorhanden ist ( wäre absolut super effizient da könnte dann auch 8-Core Parallel Threads in asm nichts mehr gegen ausrichten ) jetzt wirst du sagen warum brauche ich den bei der zu prüfenden Zahl 2 -> 50 Vielfache ? ganz einfach weil deine Abbruchbedingung > 100 sein muss nicht wegen der 2 sondern wegen der noch folgenden Zahlen welche nicht ohne Rest teilbar sind und welche wenn auch nur knapp vor der 100 und gültig und knapp nach der 100 und ungültig sind. Aber warum 51 Schritte Gesamt weil auch die Schleife ein Schritt darstellt die du für das Sieb benötigst.

ÜZ = zu überprüfende Zahl im Array
Vielfache = Anzahl Schritte Vielfache Ermittlung und Markierung
Gesamtschritte = Anzahl aus Schleifendurch und Anzahl Vielfache

Nochmal dies ist nur meine Sicht der Dinge, und keinerlei Anmaßung etwas besseres (Algorithmus) gemacht zu haben ( was ich ja auch noch nie behauptet habe ). Ich möchte nur einfach darauf hinweisen das selbst eine ineffiziente Art ( divison i.ü. bis zu 200 Taktzyklen pro DIV / IDIV ) in Maschinensprache wenn es um Geschwindigkeit geht das Maß der Dinge sein kann.

Ich bitte um Stellungnahme ( für mich ist es sehr interessant darüber zu sprechen )

Danke und Gruß
DerTürke

[DerTürke]

@BlackJack

Eins noch ich hatte tatsächlich daran gedacht SIMD ( also SSE, AVX) Befehle zu nutzen diese sind hocheffizient ( also auch was die Taktzyklen angeht )
jedoch muss hier wenn verwendet der Speicherzugriff auf 256 Bit ausgerichtet werden und die Effizienz dieser Befehle liegt in der Parallelen Berechnung d.h. ich müsste quasi YMM0 Register ( 256 Bit ) in QWORD gepackte Zahle ( 4 stück ) immer neu parallel laden, das ist bestimmt auch machbar aber dazu war ich dann doch zu faul.

Gruß
DT

[BlackJack]

@DerTürke: 6510 & Co sind deutlich älter als der C64. Und davon werden heute noch Varianten hergestellt und in allem möglichen verbaut. Und meinen C64 sehe ich fast täglich, der steht nämlich hier neben mir am Schreibtisch.

Die Frage ist wie man Optimum definiert. Assembler per Hand schreiben ist wahrscheinlich das Optimum an Zeitverschwendung des Programmierers für 99,999% der Anwendungen auf einem Desktoprechner. Und ich denke bei Deinem Code wird nicht wirklich etwas gemacht was so aussergewöhnlich ist, als dass es ein moderner Compiler nicht auch hinbekommen würde. Wie gesagt, das lohnt sich im allgemeinen erst wenn man spezielle Befehle benutzt, die Compiler nicht einsetzen.

Das Zaks-Buch habe ich im Regal stehen. Eventuell findet man das im Netz. Sein Z80-Buch findet man dort auf jeden Fall. Mit seinem Segen, also legal.

In Python gibt es dynamische Listen, das ist *der* Sequenztyp. Allerdings frage ich noch wie Du da dynamisch Zahlen draus entfernen willst und trotzdem ein Sieb umsetzen willst das effizienter als das von Eratosthenes ist‽ Nochmal: Es geht in dem Thema darum das dem OP Python zu langsam vorkam. Du definierst die Effizienz hier schon wieder über den Speicherverbrauch. Man würde wohl eher neben dem Sieb des Eratosthenes noch eine zweite Liste anlegen und sich dort die gefundenen Primzahlen notieren sobald man sie gefunden hat. Oder eine Generatorfunktion schreiben, damit der Aufrufer entscheiden kann, ob er eine komplette Liste braucht, oder ob er die nach und nach abarbeiten will, und eventuell auch vorher abbrechen möchte.

Das Argument mit dem gegenläufigen Verhalten verstehe ich nicht? Was verhält sich da gegenläufig? `r10` wird in jedem Durchlauf erhöht und `rax` bleibt doch wohl hoffentlich immer gleich, nämlich der Kandidat der auf prim getestet wird. Und für den Fall, dass er das *ist*, wird `r10` bis zur Primzahl und nur bis zur Wurzel hochgezählt, was unnötig ist. Das Hochzählen um 1 ist auch nicht besonders glücklich, weil man die Anzahl der Divisionen für einen Kandidaten locker mal halbieren kann, wenn man erst auf Teilbarkeit durch 2 testet, und dann nur noch ungerade Testdivisionen rechnet.

Jetzt möchtest Du also endlich auch darauf hinweisen was ich ja schon am Anfang gesagt habe: Bei einem schnellen Prozessor kommt auch ein ineffizienter Algorithmus häufig schnell genug zum Ziel. Allerdings ist *dafür* dann Assembler unsinnig, denn ineffiziente Algorithmen die auf einem schnellen Prozessor schnell genug zum Ziel kommen, kann man auch in anderen Programmiersprachen schreiben, die weniger umständlich, dafür aber portabler sind. C zum Beispiel.

[DerTürke]

Hallo BlackJack,

ich sah mich nun gezwungen das Sieb des Eratosthenes in einem von mir veränderten Algorithmus in c++ zu erstellen, hierbei wollte ich auch kurz demonstrieren was ich mit dynamischer Liste ( in der STL ist dies ein TemplateClass welche vector<T> heisst )
ich habe Testhalber mal versucht Primzahlen bis 200.000 zu erstellen nach ein paar Minuten habe ich dann einfach abgebrochen, weil es einfach zu lange dauert. Ich habe wie du siehst von vornherein die geraden Zahlen gemieden, und dann habe ich alle 2
verschachtelete Schleifen welche die Vielfachen ermitteln und diese aus der List ( vecotr<int> ) entfernen somit habe ich mit jedem äußeren durchlauf immer weniger elemente in der List (vector<int>). So das zu letzt die Liste (vector<int>)
nur noch die Primzahlen enthält.
Und dennoch muss ich sagen auch wenn der algorithmus nun dem Sieb entspricht und auch einige Modifikationen daran gemacht wurden, muss ich sagen das mir die Assembler variante einfach besser gefällt da diese extrem schnell ist.

Code: Alles auswählen

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	
	vector<int> m_Sieb = vector<int>(5000);

	// Explizites initialisieren des ersten Elements mit der ersten Primzahl
	m_Sieb[0] = 2;
	
	// Initialisiere vector(array) mit alle ungeraden Zahlen von 3 bis xxx
	for (int i = 1; i < 5000; m_Sieb[i] = i++ * 2 + 1){}

	vector<int>::iterator m_CurrentIndex = m_Sieb.begin();
	
	m_CurrentIndex++; ///erfordelich da die Vielfachen von 2 nicht enthalten sind 

	while (m_CurrentIndex < m_Sieb.end())
	{
		if (*m_CurrentIndex != 0)
		{
			/// Dann bitte finden und eliminieren
			vector<int>::iterator m_VielfacheIndex = m_CurrentIndex;
			while (++m_VielfacheIndex < m_Sieb.end())
			{
				
				if (*m_VielfacheIndex%*m_CurrentIndex == 0)
				{
					//*m_VielfacheIndex = 0;
					vector<int>::iterator tmpIterator = m_VielfacheIndex - 1;
					m_Sieb.erase(m_VielfacheIndex);
					m_VielfacheIndex = tmpIterator;
				}
			}
		}
		m_CurrentIndex++;
	}

	// *********************************** an diesem Punkt
	m_CurrentIndex = m_Sieb.begin();
	while (++m_CurrentIndex < m_Sieb.end())
	{
		cout << "Primzahl : " << *m_CurrentIndex << endl;
	}

	int m_Value;
	cin >> m_Value; /// Total sinnlos einfach nur um die Konsole nicht sofort zu schliessen;
	return 0;
}

ok die Zeile

if (*m_CurrentIndex != 0) ist unnötig da alle Felder bei dieser Zeile auf jeden Fall einen Wert haben, dies war ein Überbleibsel aus der Markierung mit 0 wo ich noch nicht die Liste (vector<int>) gelöscht hatte, aber diese unnötige Zeile sollte nicht allzuviel zusätzl. Taktzyklen erzeugen.

das sieb hat // *********************************** an diesem Punkt
nur noch eine Größe von 1229 elemente
dauer bis ca. 5 sekunden

Ich habe auch einfach mal etwas aus dem compilat (des c++ compilers ) rausgesucht.

Es geht schlichtweg nur um das initialisieren der Liste (vector<int>)

// Explizites initialisieren des ersten Elements mit der ersten Primzahl
m_Sieb[0] = 2;
00A16F0E push 0
00A16F10 lea ecx,[m_Sieb]
00A16F13 call std::vector<int,std::allocator<int> >::operator[] (0A115CDh)
00A16F18 mov dword ptr [eax],2

// Initialisiere vector(array) mit alle ungeraden Zahlen von 3 bis xxx
for (int i = 1; i < 5000; m_Sieb = i++ * 2 + 1){}
00A16F1E mov dword ptr [ebp-30h],1
00A16F25 jmp main+95h (0A16F45h)
00A16F27 mov eax,dword ptr [ebp-30h]
00A16F2A lea esi,[eax+eax+1]
00A16F2E mov ecx,dword ptr [ebp-30h]
00A16F31 push ecx
00A16F32 lea ecx,[m_Sieb]
00A16F35 call std::vector<int,std::allocator<int> >::operator[] (0A115CDh)
00A16F3A mov dword ptr [eax],esi
00A16F3C mov edx,dword ptr [ebp-30h]
00A16F3F add edx,1
00A16F42 mov dword ptr [ebp-30h],edx
00A16F45 cmp dword ptr [ebp-30h],1388h
00A16F4C jge main+0A0h (0A16F50h)

soviel zur optimalen umsetzung des compilers in Maschinensprache.

Ich glaube da musst du mir doch hoffentlich Recht geben, wenn ich sage das mit jeder Erkennung eines Vielfachen auch die Gesamtmenge der Liste(vector<int>) verringert wird, das das vom Sinn ( der heran gehensweise ) optimal sein müsste, darum ging es dir doch das
der Algorithmus im Vordergrund stand, mir ging es lediglich um die Geschwindigkeit.

Achso weil du ja nochmal nachgehakt hattest

Das Argument mit dem gegenläufigen Verhalten verstehe ich nicht? Was verhält sich da gegenläufig? `r10` wird in jedem Durchlauf erhöht und `rax` bleibt doch wohl hoffentlich immer gleich,
nämlich der Kandidat der auf prim getestet wird. Und für den Fall, dass er das *ist*, wird `r10` bis zur Primzahl und nur bis zur Wurzel hochgezählt, was unnötig ist.
Das Hochzählen um 1 ist auch nicht besonders glücklich, weil man die Anzahl der Divisionen für einen Kandidaten locker mal halbieren kann, wenn man erst auf Teilbarkeit durch 2 testet, und dann nur noch ungerade Testdivisionen rechnet.

hier nochmal die Sequenz

@Weiter:
xor rdx, rdx
MOVE_PARAM rax, 1
div r10
cmp rdx, 0
jz @NoPrime
inc r10
cmp r10, rax
jb @Weiter

kurze Erklärung:

divident ist im Registerpaar rdx:rax
divisor ist im Register r10
nach efolgter divison (div r10)
ist Quotient im Reigster RAX ( den ich dann als Prüfbedingung im cmp Befehl verwenden werde )
und Remainder (Rest) im Register RDX
jetzt prüfe ich ob es keinen Rest gegeben hat und falls die Bedingung zutrifft springe ich zu NoPrime
ansonsten erhöhe ich r10
und prüfe ob divisor < als Quotient ( denn die Vielfachen des Quotienten brauchen ja nicht mehr geprüft zu werden daher zähle ich nie bis n komplett hoch )
wenn das so ist dann springe auf Weiter, falls nein ist es eine Primzahl

Beispiel:
die Zahle 101 = Primzahl

zuvor
r10 = 2

1. Schleifendurchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 50
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 3
-> cmp r10, rax (3 < 50)
-> jb @Weiter ( sprung wird ausgeführt )

2. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 2
rax = 33
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 4
-> cmp r10, rax (4 < 33)
-> jb @Weiter ( sprung wird ausgeführt )

3. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 25
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 5
-> cmp r10, rax (5 < 25)
-> jb @Weiter ( sprung wird ausgeführt )

4. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 20
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 6
-> cmp r10, rax (6 < 20)
-> jb @Weiter ( sprung wird ausgeführt )

5. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 5
rax = 16
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 7
-> cmp r10, rax (7 < 16)
-> jb @Weiter ( sprung wird ausgeführt )

6. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 3
rax = 14
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 8
-> cmp r10, rax (8 < 14)
-> jb @Weiter ( sprung wird ausgeführt )

7. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 5
rax = 12
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 9
-> cmp r10, rax (9 < 12)
-> jb @Weiter ( sprung wird ausgeführt )

8. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 2
rax = 11
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 10
-> cmp r10, rax (10 < 11)
-> jb @Weiter ( sprung wird ausgeführt )

9. Schleifen durchlauf
rdx = 0
rax = 101
-> div r10
rdx = 1
rax = 10
-> cmp rdx, 0
-> nein also nicht springen
-> inc r10
r10 = 11
-> cmp r10, rax (11 < 10
-> jb @Weiter ( sprung wird NICHT ausgeführt )

-> Ende der Prüfungen die Zahl 101 ist eine Primzahl ( dazu habe ich insgesamt 9 mal die Schleife durchlaufen und wenn man dann analysiert kommt folgende Formel heraus : (Wurzel aus N)-1 divisionen ( im max. Fall )

Ich hoffe jetzt ist es ein bisschen transparenter

Viele Grüße
DT

[Sirius3]

@DerTürke: Du hast es wirklich geschafft, Deinen langsamen Primzahlsucher noch um eine lineare Suche in einer Liste und n^2 Kopieroperationen zu kombinieren. Setze doch mal das Sieb in seiner ursprünglichen Form um und lass Deine »Optimierungen« weg.
Noch einen Nachtrag zu meinen Messungen:
Primzahlen zwischen 5000000000000 und 5000000000100:
- per is_prime: 20ms
- per Sieb: 14ms

Egal wie ich es versuch, das Sieb ist immer schneller.

[DerTürke]

@Sirius

Da kann ich jetzt wirklich nur noch passen
Schade hat viel Spass gemacht

Viele Grüße
DT

[Sirius3]

PS: man sollte dem Compiler sagen, dass er optimieren soll:
[codebox=asm file=Unbenannt.asm]
## m_Sieb[0] = 2;
movl $2, (%r14)
## for (int i = 1; i < 5000; m_Sieb = i++ * 2 + 1){}
leaq 20000(%r14), %r13
movl $4, %ecx
.align 4, 0x90
LBB0_2:
leal -1(%rcx), %eax
movl %eax, (%r14,%rcx,2)
addq $2, %rcx
cmpl $10002, %ecx
jne LBB0_2
[/code]
Da bleibt nicht viel Luft, zum händischen Rumschrauben.

[DerTürke]

@Sirius:

ok was ist dass jetzt ?