Langsamer Skript

[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