Danke für den Link, Carsten!
Sehr komplex und sehr umfangreich. Ich denke für echte mathematische Berechnungen incl. Fließkomma braucht man die Routinen. Für Spiele reichen wahrscheinlich Näherungen mit Look-Up Tabellen aus.
Der menschlichen Kreativität auch hinsichtlich effektiven Näherungen scheint dabei keinen Grenzen gesetzt zu sein. Gestern bin ich bei meinen Recherchen auf einen recht neuen Algorithmus gestossen: Dem "fast inverse square root" Algorithmus. Der scheint recht kompakt und klein, ist aber wohl fast bahnbrechend für 3D-Spiele und wurde entsprechend gefeiert. Dieser Algorithmus liefert die Berechnung von 1/Wurzel x und damit werden Vektoren normalisiert. Das ist für jede 3D Berechnung notwendig, wenn man bei heutigen komplexen 3D Spielen von Millionen Berechnungen ausgeht, dann sind solche schnellen Algorithmen sofort spürbar. Dieser neue Algorithmus soll schneller sein, als Look-up Tabellen.
Und so sieht er aus:
float q_rsqrt(float number)
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
Das "Wunder" ist dabei die Konstante 0x5f3759df in Dezimal 1,597,463,007
Die vollbringt wohl das notwendige Bit-Shifting für die 1/Wurzel x Berechnung....
Und nun doch noch eine kleine aber feine Routine für sin und cos von Lee Davison:
Code: Alles auswählen
; SIN/COS Tabelle - liefert Werte zwischen $0000 und $7FFF
sintab
.word $0000,$0324,$0647,$096A,$0C8B,$0FAB,$12C8,$15E2
.word $18F8,$1C0B,$1F19,$2223,$2528,$2826,$2B1F,$2E11
.word $30FB,$33DE,$36BE,$398C,$3C56,$3F17,$41CE,$447A
.word $471C,$49B4,$4C3F,$4EBF,$5133,$539B,$55F5,$5842
.word $5A82,$5CB4,$5ED7,$60EC,$62F2,$64EB,$66CF,$68A6
.word $6A6D,$6C24,$6DC4,$6F5F,$70E2,$7255,$73B5,$7504
.word $7641,$776C,$7884,$798A,$7A7D,$7B5D,$7C2A,$7CE3
.word $7D8A,$7E1D,$7E9D,$7F09,$7F62,$7FA7,$7FD8,$7FF6
.word $7FFF
.proc main
;----------------------------------------------------------------
;
; SIN(A) COS(A) routines. A full circle is represented by $00 to
; $00 in 256 1.40625 degree steps. returned value is signed 16
; bit with X being the high byte and ranges over +/-0.99997
; The routine never returns +1.0 as it is out of the range of the
; returned value. The routine also never returns -1.0 as, although
; it is in range, the calculation is symetrical for both positive
; and negative results.
;....................... Sin/Cos .......
; COS(A) in AX
cos_A
CLC ; clear carry for add
ADC #$40 ; add 1/4 rotation
;----------------------------------------------------------------
;
; get SIN(A) in AX. enter with the Z flag reflecting the contents
; of A
sin_A
BPL sin_cos ; just get SIN/COS and return if +ve
AND #$7F ; else make +ve
JSR sin_cos ; get SIN/COS
; now do twos complement
EOR #$FF ; toggle the low byte
CLC ; clear carry for add
ADC #$01 ; add 1 to the low byte
PHA ; save the low byte
TXA ; copy the high byte
EOR #$FF ; toggle the high byte
ADC #$00 ; add the carry from the low byte
TAX ; copy back to X
PLA ; restore the low byte
RTS
;----------------------------------------------------------------
;
; get AX from SIN/COS table
sin_cos
CMP #$41 ; compare with max+1
BCC quadrant ; branch if less
EOR #$7F ; wrap $41 to $7F ..
ADC #$00 ; .. to $3F to $00
quadrant
ASL ; * 2 bytes per value
TAX ; copy to index
LDA sintab,X ; get SIN/COS table value low byte
PHA ; save it
LDA sintab+1,X ; get SIN/COS table value high byte
TAX ; copy to X
PLA ; restore the low byte
RTS
