Arcsin und Arccos berechnen
Werner Mayer
Wie wird normalerweise in Taschenrechnern/auf dem Computer die
Berechnung von Arcussinus und Arcuscosinus implementiert?
Im Internet bin ich bisher nur auf Taylorreihenentwicklung gestossen
und frage mich, ob es nicht auch einfacher/schneller geht.
Wie stellt man den Zusammenhang her zwischen der Anzahl der
zu berechnenden Glieder der Reihe und der im schlechtesten Fall
dadurch erreichbaren Genauigkeit?
Angenommen, ich habe etwas Zeit übrig und ich will, dass die
Differenz zwischen errechnetem Wert und "genauem Wert" immer
kleiner ist als 2^(-2048) - Wie würdet Ihr da rangehen?
Werner
Helmut Richter
> Wie wird normalerweise in Taschenrechnern/auf dem Computer die
> Berechnung von Arcussinus und Arcuscosinus implementiert?
>
> Im Internet bin ich bisher nur auf Taylorreihenentwicklung gestossen
> und frage mich, ob es nicht auch einfacher/schneller geht.
Es gibt auch die CORDIC-Algorithmen, aber ich bin zu faul, mir zu
überlegen, ob die hier was bringen.
> Wie stellt man den Zusammenhang her zwischen der Anzahl der
> zu berechnenden Glieder der Reihe und der im schlechtesten Fall
> dadurch erreichbaren Genauigkeit?
Der Fehler ist das sogenannte Restglied; steht z.B. in
http://de.wikipedia.org/wiki/Taylor-Formel .
Das Problem bei Taylorreihen ist, dass sie umso schlechter sind, je weiter
man von der Entwicklungsstelle weg ist. Dem kann man dadurch begegnen,
dass man das Intervall verkleinert, zum Beispiel auf [0..sqrt(2)/2] und
für größere x statt arcsin(x) lieber arccos(sqrt(1-x²)) rechnet. Das
Intervall kann man auch verkleinern, indem man es in mehrere Intervalle
unterteilt und dort verschiedene Entwicklungen hernimmt. Um die senkrechte
Tangente bei x=1 würde ich aber auf jeden Fall einen Bogen machen,
weil die durch kein Polynom anständig approximiert wird.
Außerdem verlangt ja keiner, dass man mit genau den Koeffizienten der
Taylorpolynome arbeitet. Ich hab mal für den Sinus ein wenig mit den
Koeffizienten gespielt:
Das richtige Taylorpolynom 5. Grades für den Sinus sieht so aus:
Koeffizienten des Polynoms:
n a_n
5 0.008333333333
4 0.000000000000
3 -0.166666666667
2 0.000000000000
1 1.000000000000
0 0.000000000000
Ergebnis:
x sin x f(x) Fehler
0.00 0.000000000000 0.000000000000 0.00
0.04 0.039989334187 0.039989334187 0.03
0.08 0.079914693969 0.079914693973 4.16
0.12 0.119712207289 0.119712207360 71.08
0.16 0.159318206614 0.159318207147 532.42
0.20 0.198669330795 0.198669333333 2538.27
0.24 0.237702626427 0.237702635520 9092.87
0.28 0.276355648564 0.276355675307 26742.55
0.32 0.314566560616 0.314566628693 68077.22
0.36 0.352274233275 0.352274388480 155204.91
0.40 0.389418342309 0.389418666667 324358.02
0.44 0.425939465066 0.425940096853 631787.33
0.48 0.461779175541 0.461780336640 1161098.52
0.52 0.496880137844 0.496882170027 2032182.93
0.56 0.531186197921 0.531189609813 3411892.45
0.60 0.564642473395 0.564648000000 5526604.96
0.64 0.597195441362 0.597204118187 8676824.27
0.68 0.628793024018 0.628806277973 13253954.86
0.72 0.659384671971 0.659404431360 19759388.53
0.76 0.688921445111 0.688950271147 28826036.12
0.80 0.717356090900 0.717397333333 41242433.81
Der Fehler ist dabei in letzten Stellen gemessen, also mit 10^12
multipliziert, damit man nicht nur Nullen sieht.
Das Taylor-Polynom ist also rund um die Stelle, um die es entwickelt
wurde, ganz genau und wird dann rasch schlechter. Dreht man an den
Koeffizienten ein wenig, kann man viel besser werden.
Koeffizienten des Polynoms:
n a_n
5 0.007669047222
4 0.000753837933
3 -0.166991029145
2 0.000056568772
1 0.999997030077
0 0.000000000000
Ergebnis:
x sin x f(x) Fehler
0.00 0.000000000000 0.000000000000 0.00
0.04 0.039989334187 0.039989287002 -47184.24
0.08 0.079914693969 0.079914681047 -12922.65
0.12 0.119712207289 0.119712244847 37558.56
0.16 0.159318206614 0.159318275911 69296.39
0.20 0.198669330795 0.198669400769 69973.89
0.24 0.237702626427 0.237702669220 42793.04
0.28 0.276355648564 0.276355648564 -0.00
0.32 0.314566560616 0.314566517840 -42776.20
0.36 0.352274233275 0.352274162063 -71211.80
0.40 0.389418342309 0.389418266464 -75844.90
0.44 0.425939465066 0.425939410722 -54344.10
0.48 0.461779175541 0.461779163207 -12334.83
0.52 0.496880137844 0.496880175213 37368.79
0.56 0.531186197921 0.531186275197 77275.95
0.60 0.564642473395 0.564642563017 89621.97
0.64 0.597195441362 0.597195504168 62805.38
0.68 0.628793024018 0.628793024018 -0.00
0.72 0.659384671971 0.659384602050 -69921.20
0.76 0.688921445111 0.688921366093 -79017.11
0.80 0.717356090900 0.717356186565 95665.06
Dass hier dreimal der Fehler Null ist, ist kein Zufall: ich habe das
Polynom 5. Grades genommen, das an den willkürlich gewählten Stellen 0,
0.09, 0.28, 0.49 und pi/4 mit dem Sinus übereinstimmt. 0 und pi/4 sind
dabei, damit es beim Anstückeln keinen Ärger gibt; die anderen Stellen
sind durch Probieren gefunden. Die besten Resultate bekommt man, wenn man
Tschebyschew-Polynome verwendet, aber die sind an den Rändern gerade nicht
so gut.
Voraussetzung für solche Spielchen ist natürlich, dass man die genauen
Werte irgendwoanders schon herhat, bevor man an den Koeffizienten zu
drehen anfängt.
> Angenommen, ich habe etwas Zeit übrig und ich will, dass die
> Differenz zwischen errechnetem Wert und "genauem Wert" immer
> kleiner ist als 2^(-2048) - Wie würdet Ihr da rangehen?
Sportlich!
--
Helmut Richter
kilian heckrodt
> Hallo!
>
> Wie wird normalerweise in Taschenrechnern/auf dem Computer die
> Berechnung von Arcussinus und Arcuscosinus implementiert?
>
> Im Internet bin ich bisher nur auf Taylorreihenentwicklung gestossen
> und frage mich, ob es nicht auch einfacher/schneller geht.
>
als nur "plain taylor"). Allerdings wird man da wohl auf
Spezialitertatur bzw. Fachveroeffentlichungen zurueckgreifen muessen -
z.B.:
http://links.jstor.org/sici?sici=0891-6837(195407)8%3A47%3C132%3AAMFCIT%3E2.0.CO%3B2-3
http://ads.nao.ac.jp/jp/pub/vol8/015/PNAOJvol8p015.pdf
Eine einfache Beschleunigung (solange man sich vorher auf
fixe Genauigkeit festlegt) erhaelt man auch, indem man einige
wenige Punkte in [0,1] mit Taylor berechnet und dann einen Spline
oder eine andere Naeherungskurve hindurchlegt und diese fuer
weitere Berechnungen benutzt.
> Wie stellt man den Zusammenhang her zwischen der Anzahl der
> zu berechnenden Glieder der Reihe und der im schlechtesten Fall
> dadurch erreichbaren Genauigkeit?
>
Das erhaelt man durch Abschaetzen des Restgliedes.
Helmut Richter
> Der Fehler ist das sogenannte Restglied; steht z.B. in
> http://de.wikipedia.org/wiki/Taylor-Formel .
Wenn die Glieder immer kleiner werden und alternierende Vorzeichen haben,
kann man einfach aufhören, wenn sich am Ergebnis nichts mehr ändert.
Sonst meistens auch, aber dann muss man nachdenken, ob es berechtigt war.
In beiden Fällen hat man natürlich die schon aufgesammelten
Rundungsfehler behalten. Deswegen sind Reihem, die sehr viele Glieder
brauchen (die einfache Reihe für den Logarithmus) unbrauchbar.
> > Angenommen, ich habe etwas Zeit übrig und ich will, dass die
> > Differenz zwischen errechnetem Wert und "genauem Wert" immer
> > kleiner ist als 2^(-2048) - Wie würdet Ihr da rangehen?
>
> Sportlich!
Du brauchst vor allem eine Arithmetik mit um soviel höherer Stellenzahl
als deine gefordeten 2048 Binär- oder 617 Dezimalstellen, dass die
Rundungsfehler sich in den übrigen Stellen verstecken können. Ganz sauber
arbeitet man mit Intervallarithmetik: immer die größte und die kleinste
Zahl ausrechnen, die trotz Rundungsfehler noch richtig sein kann.
--
Helmut Richter
Peter Niessen
>> Im Internet bin ich bisher nur auf Taylorreihenentwicklung gestossen
>> und frage mich, ob es nicht auch einfacher/schneller geht.
>
> Es gibt auch die CORDIC-Algorithmen, aber ich bin zu faul, mir zu
> überlegen, ob die hier was bringen.
AFAIK wird das wirklich so gemacht.
Googel liefert auf Anhieb:
CORDIC-Algorithmen gehören zur Klasse der shift and add Algorithmen. Mit
der Verwendung von CORDIC-Algorithmen wird beabsichtigt, viele verschiedene
Standardfunktionen mit Hilfe derselben Hardware-Struktur berechnen zu
können.
Aus Geschwindigkeits- und Kostengründen werden CORDIC-Prozessoren möglichst
einfach aufgebaut. CORDIC-Technik wurde erfolgreich in Taschenrechnern
(z.B. HP-35) und arithmetischen Coprozessoren (z.B. intel8087)
implementiert.
--
Mit freundlichen Grüßen
Peter Nießen