Schnelle Hypot Methode für kleine a b (a<=10,b<=10)

[LarsImNetz]

Moin,

Peter hatte AFAIK letztens erst eine flotte Methode ausgeknobelt für SQRT(a*a + b*b), um z.B. die genauere Entfernung zu messen.

Für Pacmen war ich faul und habe einfach abs(a)+abs(b) verwendet.

Für mein neuestes Projekt brauche ich es aber etwas genauer, soll ja besser aussehen. Allerdings ist mir Peters Methode viel zu langsam und meine x,y Werte sind recht klein (<=10)

Hier also mal meine Version von sqr(x*x + y*y), die Tabellen verwendet und damit sehr flott arbeitet. Kann auch als Idee verstanden werden, wie man so etwas machen könnte.

Code: Alles auswählen

; schnelle "Berechnung" von SQR(x*x + y*y)
; x und y dürfen von -10 bis +10 angegeben werden.
; ist x oder y zu groß(zu klein) wird $FF zurückgegeben.

reg=212 ; irgendeine freie zero-page Adresse.

FAST_HYPOT
 cpy #0
 bpl y_positiv

  sty reg
  SEC             ;Ensure carry is set
  LDA #0          ;Load constant zero
  SBC REG        ;... subtract the least significant byte
  TAY             ;... and store the result

y_positiv
 cpy #11
 bge fail        ; bge ist branch greater equal (bcs?)

 cpx #0
 bpl x_positiv

  stx reg
  SEC             ;Ensure carry is set
  LDA #0          ;Load constant zero
  SBC REG        ;... subtract the least significant byte
  TAX             ;... and store the result

x_positiv
 cpx #11
 bge fail

 clc
 txa
 adc hypot_mult_11,y
 tax
 ldy hypot_10x10,x
 ldx #0
 rts

fail
 ldy #$ff
 ldx #$00
 rts

hypot_mult_11
 .byte 0,11,22,33,44,55,66,77,88,99,110

hypot_10x10
 .byte 0,1,2,3,4,5,6,7,8,9,10
 .byte 1,1,2,3,4,5,6,7,8,9,10
 .byte 2,2,3,4,4,5,6,7,8,9,10
 .byte 3,3,4,4,5,6,7,8,9,9,10
 .byte 4,4,4,5,6,6,7,8,9,10,11
 .byte 5,5,5,6,6,7,8,9,9,10,11
 .byte 6,6,6,7,7,8,8,9,10,11,12
 .byte 7,7,7,8,8,9,9,10,11,11,12
 .byte 8,8,8,9,9,9,10,11,11,12,13
 .byte 9,9,9,9,10,10,11,11,12,13,13
 .byte 10,10,10,10,11,11,12,12,13,13,14

Hier noch der Basic Code, um die hypot_10x10 Tabelle zu erstellen.

Code: Alles auswählen

 for x = 0 to 10
   for y = 0 to 10
     ?sqr(x*x + y*y);",";
   next y
   ?
 next x

Überflüssige Kommas müssen selbst entfernt werden.
Wer den MADS Assembler nutzt, muss wohl statt .byte etwas anderes schreiben.

LG
Lars

[LarsImNetz]

Sorry ich meinte in Basic natürlich:

Code: Alles auswählen

 ? int(0.5 + sqr(x*x + y*y));",";

[Dr. Irata]

Hallo Lars,
für den Raycaster brauchte ich auch die Entfernung (zu berechnen durch Pythagoras). Beim Raycaster ist man ja immer extrem zeitkritisch und da habe ich dann folgende Näherung benutzt, die wirklich sehr gut funktioniert:

SQR(x*x + y*y) = x+y/2 für y<x

[LarsImNetz]

Betrachtung der Näherung für y<x x+y/2 sonst y+x/2

Basic-Code, um die Tabelle zu erstellen, nur für den Vergleich

Code: Alles auswählen

10 FOR Y=0 TO 10
20   FOR X=0 TO 10
30     IF Y<X
40       VALUE=X+Y/2
50     ELSE
60       VALUE=Y+X/2
70     ENDIF
80     ? INT(VALUE);",";
90   NEXT X
91   ?
99 NEXT Y

Der Basic-Code gibt folgende Tabelle aus:

Code: Alles auswählen

0,1,2,3,4,5,6,7,8,9,10,
1,1,2,3,4,5,6,7,8,9,10,
2,2,3,4,5,6,7,8,9,10,11,
3,3,4,4,5,6,7,8,9,10,11,
4,4,5,5,6,7,8,9,10,11,12,
5,5,6,6,7,7,8,9,10,11,12,
6,6,7,7,8,8,9,10,11,12,13,
7,7,8,8,9,9,10,10,11,12,13,
8,8,9,9,10,10,11,11,12,13,14,
9,9,10,10,11,11,12,12,13,13,14,
10,10,11,11,12,12,13,13,14,14,15,

Wenn man die mit meiner Tabelle vergleicht (siehe oben), sieht die doch verdammt ähnlich aus, ich bin begeistert.

Ich habe das jetzt mal nur so grob runtergetippert und nicht genauer getestet. Scharfes Auge sagt: "sieht brauchbar aus".

Code: Alles auswählen

[...]
; der Code für x=abs(x) und y=abs(y) und die Kontrolle ob x<11 und y<11 siehe oben.
; x und y sind hier zero page Register
; die Funktion liefert das Ergebnis im X und Y-Register, es gilt (Y+X*256)
; die Zahlen hinter dem Semikolon sind Zyklen.

 stx x          ; 3
 cpy x          ; 3 imaginaer x - y
 blt y_less_then_x ; 2 or 3

 sty y          ; 3 y sichern
 ; y + x/2
 txa            ; 2
 lsr            ; 2   accu := x / 2
 clc            ; 2
 adc y          ; 3
 tay            ; 2
; 22 Zyklen + overhead
 ldx #0
 rts

y_less_then_x
; x + y/2
 tya            ; 2
 lsr            ; 2  accu := y/2
 clc            ; 2
 adc x          ; 3
 tay            ; 2

; 19 Zyklen + overhead
 ldx #0
 rts

Der ASM-Code ist etwas länger, spart trotzdem 118 Bytes, weil die Tabelle wegfällt.
Ist allerdings ein paar Zyklen (4 bis 7) langsamer, aber die kann man verschmerzen, dafür spart man etliche Bytes.

@Peter TOP!!!

[Dr. Irata]

@Lars: gracias

aber: ... blt y_less_then_x ; 2 or 3
meinst du bit y_less_then_x ; 2 or 3 ??

[LarsImNetz]

atasm hat die Assemblerbefehle BLT (branch if less than) und BGE (branch if greater or equal).

Ich dachte MADS hat die auch.

Siehe: http://www.6502.org/tutorials/compare_beyond.html

Die entsprechen BCC und BCS, sind aber leichter verständlich.

Probiere es einfach mal aus.