Fast ACOS - Impelementiert wie?

[Michael H. (overthere)]

Hallo,

ich habe eine schöne acos Implementierung gefunden, und würde mir gerne 
die Herleitung anschauen. Eine Referenz ist angegeben, aber wie finde 
ich das im Buch?

Implementierung:
http://http.developer.nvidia.com/Cg/acos.html

Buch:
http://people.math.sfu.ca/~cbm/aands/abramowitz_and_stegun.pdf

Hoffe, Ihr habt eine Idee, denn ich würde gerne nach dem Schema noch 
Cos, Sin und so realisieren.

-Michael

[THOR (Gast)]

Seite 76ff, Polynom-Annäherungen.

Du könntest natürlich auch ne Taylor-Annäherung machen, ab 10 Termen ist 
das sehr genau. Multiplikation kann deine CPU vermutlich in Hardware.

[THOR (Gast)]

Ich glaub das sind sogar Taylorreihen, das e(x) kommt mir bekannt vor, 
das ist der Fehlerterm.

[Michael H. (overthere)]

Gefunden: 4.4.45, nur stark vereinfacht fürs rechnen bei NVidia.

[(º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· (Gast)]

Polynomiale Reihenentwicklungen konvergieren für die
inversen trigonometrischen Funktionen viel zu langsam.

C.O.R.D.I.C. heisst das Zauberwort.

Das steht aber nicht in Büchern aus dem Mittelalter.

[THOR (Gast)]

(º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· schrieb im Beitrag 
#4811650:
> Polynomiale Reihenentwicklungen konvergieren für die
> inversen trigonometrischen Funktionen viel zu langsam.
>
> C.O.R.D.I.C. heisst das Zauberwort.
>
> Das steht aber nicht in Büchern aus dem Mittelalter.

Jack E. Volder: The CORDIC Trigonometric Computing Technique. In: IRE 
Transactions on Electronic Computers. September 1959.

Neu ist das jetzt nicht.

Und in dem Nvidia Link aus dem Eingangspost sehe ich 8 Multiplikationen 
und ein paar Additionen, das ist jetzt auch nicht extrem teuer.

Wenns rasend schnell gehen muss, kann man auch weniger Polynome nehmen 
und  interpolieren oder Lookup + Interpolation.

[Michael H. (overthere)]

Genau desshalb verwende ich auch den Algo.
Ich habe mir jetzt ähnliche für die Trigo-Functions gebaut.
Für meinen Bedarf reicht das.

Cordic glaube ich nicht das das schneller ist, da ne Multiplikation 1 
Tackt braucht...

[Nils P. (torus)]

Disagree

CORDIC ist toll für Hardware Implementierungen, weil man ohne 
Multiplikationen auskommt. Das spart Energie, Chipfläche und ist auch 
schneller weil ein kompletter CORDIC Schritt in einem Cycle ausgeführt 
werden kann.


In Software ist CORDIC fast immer langsamer als eine auf Polynome 
basierende Funktion. Ausnahmen hab ich lediglich bei CPU Architekturen 
gesehen, die spezielle Befehle für CORDIC haben. Bei einigen DSP 
Architekturen von Texas Instruments ist das z. B. der Fall.

Am schnellsten in Software wird wohl eine simple Lookup-Table mit 
Interpolation sein. Alternativ zu Taylor: Minimax Approximation. Da 
kommt man mit weniger Rechenschritten zu einem genaueren Ergebnis.

[W.S. (Gast)]

Michael H. schrieb:
> Hoffe, Ihr habt eine Idee, denn ich würde gerne nach dem Schema noch
> Cos, Sin und so realisieren.

Sinus nach Pedersen. hab ich vor einiger Zeit her mal gepostet.

W.S.