Langsamer Skript

[BlackJack]

@Septimus: Okay, mich hatte der Name `primzahl` verwirrt, denn da werden ganz offensichtlich keine Primzahlen dran gebunden oder wenn, dann nur zufällig. Solltest Du vielleicht ändern den Namen.

Und dann solltest Du die innere Schleife nur so oft durchführen wie nötig. So wie es im Pastebin steht wird die bei Dir 2,8 *Milliarden* mal durchlaufen. Wenn etwas was ”nur” 50 Millionen mal durchlaufen wird, bei Dir schon mehr als 2 Stunden dauert, dann dürftest Du hier das Ergebnis noch nicht gesehen haben. So etwas um die 4 bis 4½ Millionen Durchläufe des Codes in der innersten Schleife sollten für Primzahlen bis 2 Millionen nicht überschritten werden müssen.

Mir ist schon klar *das* Du den Elementen in der Liste die Werte 1 bis 2.000.000 zuordnest, nur nicht *warum* Du das machst. Denn nur deswegen musst Du beim `enumerate()` einen Startwert von 1 angeben und beim Indexzugriff auf die Liste immer 1 von der Zahl abziehen. *Beides* könnte man sich sparen. Man verbraucht einen Listenplatz mehr, muss den mit `False` belegen, und beim letzten Schritt eine Nicht-Primzahl mehr einfach überlesen. Dem Gegenüber stehen ca. vier Millionen mal eine 1 vom Index abziehen wenn man es richtig macht, oder eben 2,8 Milliarden mal in Deinem Fall, die man sich an Rechenzeit sparen kann.

[Septimus]

Hmm jo hast schon recht, aber ich bezweifle mal, dass die eine Position sehr viel Unterschied macht. Ich würde ja nur die Summe am Anfang 1 setzen und dann den einen Eintrag der Liste weglassen, der sowieso übersprungen wird bei der Berechnung.
Ist wirklich unnötig, aber für mich ist das jetzt nicht so signifikant, dass ich es unbedingt weglassen würde. Die Idee hinter dem Algorithmus ist so besser erhalten, so kann ich wenn ich später darauf zurückgreifen muss, besser nachvollziehen, was ich gemacht hab.

Ich hab auch mal die Zeit für die Berechnung gestoppt:
2066.5651290876353 Sekunden oder 34.44 Minuten hat's gedauert. Wieso das so viel weniger dauert, kann ich aber auch nicht feststellen.

[BlackJack]

@Septimus: Ich habe es ja schon geschrieben: Du tauschst ein gespartes Element und minimale, konstante Zeit für dessen Initialisierung und überspringen, gegen die Zeit für sehr viele Rechenoperationen.

Die Idee des Algorithmus verändert sich doch dadurch kein bisschen, im Gegenteil es ist sogar etwas klarer wenn man sagen kann der Index in die Liste entspricht genau der Zahl für den der Wahrheitswert angibt ob es eine Primzahl ist oder nicht. Statt das der Index plus 1 dieser Zahl entspricht, weswegen man von der Zahl 1 abziehen muss um den Index zu erhalten.

Wieso *was* so viel weniger dauert? Warum 2,8 Milliarden innere Schleifendurchläufe lange dauern kann ich Dir sagen: Weil das verdammt viele sind. Und zwar um Grössenordnungen *zu* viele. Die Frage ist eher warum die 50 Millionen Durchläufe bei Euler9 bei Dir angeblich so lange brauchen.

Schau Dir hier doch mal an wie oft Du die innere Schleife durchläufst obwohl ``primzahl * h`` schon deutlich über `n` liegen, also völlig unnötig. Wenn man sich das Siebverfahren anschaut, dann wird das ja eigentlich immer so beschrieben, dass man die nächste Primzahl sucht, und dann alle Vielfachen davon streicht. Du suchst aber nicht nach Primzahlen sondern streichst Vielfache von allen möglichen Zahlen, auch von solchen die keine Primzahlen sind, aber durch das streichen von Primzahlen sowieso schon eliminiert wurden. Plus die Obergrenze die Du so ungünstig hoch festsetzt. Man kann die innere Schleife schon direkt über Vielfache von einer Zahl bis `n` laufen lassen — `range()` kennt auch drei Argumente. Dann hätte man ausserdem die Multiplikation durch Additionen ersetzt, was eventuell schneller abgearbeitet wird.

[Septimus]

Ja ich sehe jetzt, was du meinst mit viel zu viele Berechnungen.
Ich hab bei der inneren Schleife jetzt ein else: break eingefügt, die Berechnung dauert jetzt nurnoch 22 Sekunden.

Vorher war mir nicht so wirklich klar, wo ich einsparen sollte, aber da hatte ich wohl einfach nen Brett vor'm Kopp u_u'

Das Problem, das ich beim anpassen der inneren Schleife im Moment habe ist, dass sich das Ergebnis verändert, wenn ich in h-Schritten laufen lasse oder die obere Grenze niedriger setze. Ich blick da glaub ich noch nicht ganz durch, was ich da verändere. Ich setz mich mal morgen Abend nochmal dran, dann kann ich vielleicht besser arbeiten.

[BlackJack]

Zum Thema langsam und Euler 9: Dein erster hier gezeigter Ansatz als BASIC-Programm für den C64:
[codebox=locobasic file=Unbenannt.txt]10 TI$="000000":X=500:Y=1000
20 FOR A=1 TO X:FOR B=1 TO X:FOR C=1 TO X:IF A+B+C=Y AND A*A+B*B=C*C THEN 40
30 NEXT:NEXT:NEXT
40 PRINT A,B,C
50 PRINT TI$[/code]
Lief über Nacht, und ich habe es heute morgen mal unterbrochen um zu sehen wie weit es gekommen ist. Die äussere Schleife ist in 14 Stunden und 42 Minuten gerade einmal 12 mal durchlaufen worden. Hochgerechnet auf den gesamten Suchraum wären das cirka 25½ Tage. Da wir das Ergebnis ja schon kennen, kann man abschätzen, dass der C64 ”schon” nach cirka 10 Tagen das Ergebnis ausspucken wird. Oder würde — ich lasse das jetzt mal nicht weiterlaufen.

Eine Variante die gezielt nur A, B, und Cs generiert die zusammenaddiert 1000 ergeben kommt schon nach 46½ Minuten zum Ergebnis. Mit Basic-Boss kompiliert läuft es nur noch 24 Minuten.
[codebox=locobasic file=x]1 REM@ £PROTOCOL:£FASTFOR:£FASTARRAY:£SHORTIF
2 REM@ £CONSTANT X,Y,Z
10 TI$="000000":X=1000:Y=999:Z=998
20 FOR A=1 TO Z:FOR B=A+1 TO Y-A:C=X-A-B:IF A*A+B*B=C*C THEN 40
30 NEXT:NEXT
40 PRINT A,B,C
50 PRINT TI$[/code]
Man kann A, B, und C für den Compiler leider nicht einfach als WORD deklarieren, weil dann die Berechnung der ``IF``-Bedingung nicht mehr korrekt berechnet wird, da die Zwischenergebnisse der Rechnung die 16-Bit-Grenze sprengen.

Nur mit ganzen Zahlen geht es in C mit dem cc65-Cross-Compiler:
[codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>

int main(void)
{
register uint16_t a, b, c;

for (a = 1; a < (1000 - 2); ++a) {
for (b = a + 1; b < (1000 - 1) - a; ++b) {
c = 1000 - a - b;
if ((uint32_t) a * a + (uint32_t) b * b == (uint32_t) c * c) {
printf("%u, %u, %u\n", a, b, c);
return 0;
}
}
}
return 1;
}[/code]
Damit schafft es der C64 in etwas unter 18 Minuten.

[Septimus]

Ich glaub ich weiß was du meinst, aber ich hab im Moment nicht sehr viel Zeit.
Wenn ich mich mal in Ruhe hinsetzen kann, mach ich mich an die Umsetzung.

[BlackJack]

Und noch mal etwas zu den Laufzeiten auf dem C64. Es wird ja noch ziemlich oft quadriert und zwar die selben Werte mehrfach, also dachte ich mir ich berechne das mal vor der Schleife die alle Zahlentripel durchgeht die zusammen 1000 ergeben:
[codebox=locobasic file=x]10 REM@ £PROTOCOL:£FASTFOR:£FASTARRAY:£SHORTIF
20 REM@ £WORD A,B=FAST,C=FAST:£CONSTANT X,Y,Z
30 TI$="000000":DIM S(999):X=1000:Y=999:Z=998
40 FOR B=1 TO 999:D=B:S(B)=D*D:NEXT
50 FOR A=1 TO Z:FOR B=A+1 TO Y-A:C=X-A-B:IF S(A)+S(B)=S(C) THEN 70
60 NEXT:NEXT
70 PRINT A,B,C:PRINT TI$[/code]
Unkompiliert bringt das kaum etwas, weil der Arrayzugriff anscheinend nahezu genau so langsam ist wie das quadrieren, aber kompiliert kommt das auf unter 7½ Minuten.

Und das entsprechende C-Programm läuft auf der alten Kiste in unter 3 Minuten durch:
[codebox=c file=x]#include <stdint.h>
#include <stdio.h>

static uint32_t squared[1000];

int main(void)
{
register uint16_t a, b, c;

for (a = 1; a < 1000; ++a) {
squared[a] = (uint32_t) a * a;
}
for (a = 1; a < (1000 - 2); ++a) {
for (b = a + 1; b < (1000 - 1) - a; ++b) {
c = 1000 - a - b;
if (squared[a] + squared == squared[c]) {
printf("%u, %u, %u\n", a, b, c);
return 0;
}
}
}
return 1;
}[/code]

[BlackJack]

Für alle die noch DOS einsetzen eine Assemblerlösung:
[codebox=asm file=Unbenannt.asm] cpu 386
org 100h

start:

segment .bss
.squares: resd 1000

segment .code
;
; Precalculate squares.
;
mov di,.squares+4
mov cx,1
.L1:
mov ax,cx
mul ax
stosw
mov ax,dx
stosw

inc cx
cmp cx,999
jne .L1
;
; Search a (dx), b (cx), c (bx)
;
xor ebx,ebx
xor ecx,ecx
xor edx,edx

mov dx,1
.L2:
mov cx,dx
inc cx
.L3:
mov eax,[.squares+edx*4]
add eax,[.squares+ecx*4]
mov bx,1000
sub bx,dx
sub bx,cx
cmp eax,[.squares+ebx*4]
je .heureka

inc cx
cmp cx,999
jne .L3

inc dx
cmp dx,998
jne .L2

ret

.heureka:
push bx
push cx
mov ax,dx
call print_number
pop ax
call print_number
pop ax
jmp print_number


print_number:

segment .data
.buffer db ' $'

segment .code
mov bx,4
mov [.buffer+4], byte '0'

mov cx,10
.L1:
test ax,ax
jz .converted
xor dx,dx
div cx
or dl, '0'
mov [.buffer+bx],dl
dec bx
jmp .L1

.converted:
mov ah, 9
lea dx,[.buffer+bx+1]
int 21h

ret[/code]

[Hyperion]

@BlackJack: Ich liebe Deine Alternativlösungen - insbesondere natürlich immer wieder gerne die für den C64 Da werd ich so schön nostalgisch... außerdem zeigt es, wie viele mit dem kleinen Brotkasten wirklich schon möglich "war"

[BlackJack]

@Hyperion: Bei der Summe der Primzahlen kleiner 2 Millionen wird es dann aber problematisch. Wenn man ein Bit pro ungerader Zahl speichert ist das Sieb immer noch zu gross für den Arbeitsspeicher vom C64. Man müsste das Sieb also in mehrere Teile zerlegen und in einer Speichererweiterung ablegen. Sofern man eine Speichererweiterung zur Verfügung hat. Interessanterweise hat man das gleiche Problem auch bei einem 16-Bit-DOS-Programm, zumindest was das Aufteilen des Siebs angeht, weil ja nur 64 KiB pro Segment möglich sind.

[Sirius3]

@BlackJack: da die Bit-Manipulation schon recht aufwendig ist, ist ein zusätzlicher segmentübergreifender Speicherzugriff für ein Sieb eine Kleinigkeit (reiner 8086-Code):

Code: Alles auswählen

; Primzahlvielfaches in dx:ax
set_bit:
    mov cl,al
    and cl,7
    mov bx,1
    shl bx,cl
    shr dx,1
    rcr ax,1
    shr dx,1
    rcr ax,1
    shr dx,1
    rcr ax,1
    mov di,ax
    mov cl,12
    shl dx,cl
    add dx, sieve_seg
    mov es,dx
    or es:[di], bl
    ret

Für get_bit einfach das "or" in der letzten Zeile durch "test" ersetzen.
Ein bis unters Dach mit Speicher gefüllter Rechner dürfte bei der Primzahlensumme bis ungefähr 8Mio an seine Grenzen stoßen. (Tipp: in Video-Modus 13h schalten und den Grafikkartenspeicher mitbenutzen)

[BlackJack]

@Sirius3: Meine DOS-Zeit habe ich mit einem 386er begonnen, also gehe ich irgendwie immer davon aus, dass es 32-Bit-Register gibt. Mein `get_bit` sieht im Moment so aus:

Code: Alles auswählen

;----------------------------------------------------------
; in:   EAX bit offset.
;       sieve_segments:word - table of segment adresses
; out:  CF = bit value.
;       AL byte value.
;       ES:BX address of byte value.
;       CX bit offset within byte.
get_bit:
    mov cx,ax
    and cx,00000111b
    shr eax,3
    mov ebx,eax
    shr ebx,16
    shl bx,1
    mov bx,[sieve_segments+bx]
    mov es,bx
    mov bx,ax
    mov al,[es:bx]
    bt ax,cx
    ret

Ich arbeite mit einer Tabelle mit den Segmentadressen, für den Fall das man die Segmente nicht direkt aufeinander folgend haben kann. Obwohl das bei meiner aktuellen Teillösung der Fall ist.

Das `reset_bit` baut auf `get_bit` auf, und da es nur an einer Stelle im Code vorkommen würde, gibt es das nicht als extra Unterroutine, sondern steht „inline”:

Code: Alles auswählen

    call get_bit
    btr ax,cx
    mov [es:bx],al

[BlackJack]

Okay, nun ist es endlich fertig. Problem #10 in Assembler für einen 386er mit mathematischem Coprozesor und einem Speicherbedarf von ca. 192 KiB als DOS .COM-Datei: http://pastebin.com/6JyJtJKm