Wie berechnen Programmierungsprachen sqrt, cos, log usw..?

... komplette Frage anzeigen

8 Antworten

Ich benutze am liebsten eine antike Programmiersprache die heute keinen mehr interessiert, ist aber nicht die einzige Programmiersprache die ich kann.

In dieser Programmiersprache ist e ^ 89 , also EXP(89) das Maximum mit dem die e-Funktion berechnet werden kann, offenbar weil 15 Nachkommastellen der Mantisse gewährleistet werden sollen.

Ich habe mir mal aus Spaß ein Unterprogramm geschrieben, welches Taylorreihen mit großer Ordnung ausrechnen kann.

Dabei habe ich das Ausrechnen der Fakultäten über die Beziehung ln(a * b) = ln(a) + ln(b) machen lassen, und die Summe der jeweiligen Fakultät durch ln(10) dividiert, um den logarithmus naturalis auf die 10er-Basis zu transformieren.

Anschließend habe ich Mantisse und Exponent voneinander getrennt.

Der Ganzzahlanteil der Summe bildet den Exponenten und der Nachkommaanteil der Summe bildet mit 10 ^ (Nachkommaanteil) die Mantisse.

Bei der Berechnung der Potenzen x ^ n bin ich ganz genau so vorgegangen.

Das Unterprogramm kann bis zirka e ^ (2500) also EXP(2500) eine Genauigkeit von einer richtigen Vorkommastelle und 10 richtigen Nachkommastellen der Mantisse und für den korrekten Exponenten garantieren.

Das Unterprogramm könnte ich für jede Funktion verwenden, muss nur jeweils angepasst werden, die sich durch eine konvergente Taylorreihe ausdrücken lässt.

Man braucht also nur die Bildungsvorschrift der Koeffizienten der Taylorreihe kennen und dann kann man es auf diese Art und Weise bewerkstelligen.

Ein anderer User hat Tschebyscheff-Polynome erwähnt, die kann man auch benutzen.

Sie gewährleisten eine ziemlich hohe Genauigkeit, wenn jedoch die Approximationsintervalle zu groß werden, dann bricht die Genauigkeit ein. Das macht aber nichts, weil man einfach für verschiedene Approximationsintervalle verschiedene Tschebyscheff-Polynome verwenden kann.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von DepravedGirl
01.01.2016, 16:18

Vielen Dank für den Stern :-)) !

0

Wenns um Genauigkeit geht, dann die von den anderen schon genannten Verfahren.

Wenns um Schnelligkeit geht und die Genauigkeit nicht so hoch sein muss - zB bei schnellen Transformationen von 3D Koordinaten in Computerspielen - dann:

einfach durch Zugriff auf ein Array mit vorberechneten Werten und auf die Schnelle eine kleine lineare Interpolation noch dazu ;-)

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von TeeTier
30.12.2015, 21:27

Sehr schöne pragmatische Lösung! :)

Wenn ich den Sinus selbst berechnen will, nehme ich mir auch immer das Intervall [-1,+1] als Fixpunkt, und interpoliere Linear.

Und anstatt kompliziert eine Wurzel zu ziehen, rechne ich einfach x / 2, was oftmals sogar überraschend genau ist, vor allem wenn x = 4 ist. :)

1

Natürlich gibt es zig Algorithmen. 

Wenn Dich die mathematische Seite interessiert (oder man mehr als die 64 {Datentyp double} oder 80 Bit der FPU {also mehr als 15 Nachkommastellen} benötigt)

gibt es zu jeder der über 300 bekannten Funktionen sogar für jeden Argumenten-Bereich einen optimierten Algorithmus (Iteration, Reihenentwicklung {Taylor... usw.}, hypergeometrische Funktionen, Kettenbrüche, ....).

Als ich den "Umkehrfunktionen Rechner online 300 Funktionen" entwickelte und mich für 36 Nachkommastellen entschied, konnte ich nicht auf fertige Funktionen zurückgreifen, sondern musste alles selbst optimieren. Fast 80 % der Funktionen konnte mit hypergeometrischen Funktionen realisiert werden:

sin(x) = x*hyg0F1(3/2, -x²/4)

cos(x)=hyg0F1(1/2, -x²/4)

usw.

Bei 90% aller Programmiersprachen kennt man jedoch nur fertige Funktionen, die mit Datentyp double rechnen (64 Bit etwa 15 Stellen). Diese greifen auf fertige Funktionen der FPU (damals extra Co-Prozessor -> heute Teil der CPU) zurück. Unter

https://runtimebasic.net/Assembler:Funktionen:OpCodes-FPU

sind die wichtigsten Funktionen (ASM-OpCode Maschinenbefehl) aufgelistet.

Gute Programmiersprachen/Compiler wie ASM oder c++ erlauben es dem Programmierer, das beste aus der aktuellen CPU herauszuholen. So bieten neuere CPUs wie der i7 neue Befehlssätze an, mit denen man zig mal schneller als die alten FPU-Befehle ist. AVX erlaubt bis zu 4 mal 64 Bit parallel zu berechnen...

Interessant fand ich, dass die Browser von InternetExplorer und Google Chrome trotz gleicher Programmiersprache "JavaScript" den sin(x) unterschiedlich berechnen:

Während IE den ungenauen ASM-Befehl FSIN nimmt, hat Google was eigenes und genaueres entwickelt. Wenn Du mehr darüber wissen möchtest, frage nach... (ich darf  nur 1 LINK pro Antwort angeben)

Antwort bewerten Vielen Dank für Deine Bewertung

Das hängt von der Programmiersprache und der Funktion ab. Einige Prozessoren implementieren Funktionen wie sin direkt in Hardware, dann muss in Software gar nichts mehr gemacht werden.

In der Regel - wenn es in Software gemacht wird - läuft es bei trigonometrischen Funktionen auf Polynomapproximationen heraus. Z.B. die Taylorserie (als Beispiel, wird aber soweit ich weiß nicht genutzt, da zu ungenau) oder Tschebyscheff-Polynome (die werden tatsächlich verwendet).

Wurzelziehen oder Logarithmus kann z.B. mit dem Newtonverfahren berechnet werden.

Eine andere ALternative wäre z.B. https://en.wikipedia.org/wiki/CORDIC -wird auch manchmal verwendet

Antwort bewerten Vielen Dank für Deine Bewertung

Die von dir genannten Funktionen sind meist schon Teil der Standard-Bibliothek zur gewählten Programmiersprache.

Für C und C++ siehe https://de.wikipedia.org/wiki/Math.h .

Ich denke nicht, dass es wichtige Programmiersprache gibt, in denen man all das selbst zu implementieren hat. 

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von TeeTier
30.12.2015, 21:44

In Java muss man das z. B. selber machen! Und zwar:

Die Funktionen aus Math unterstützen ausschließlich double-Werte, und mit einem float (also halber Genauigkeit) ist man aber im Schnitt um den Faktor 4 schneller.

Deshalb gibt es bei Android auch FloatMath. :)

Das Problem ist, dass hier eine reine JNI / JNA Implementierung für die JVM extremst viel Overhead mit sich bringt, der jeden Geschwindigkeitsvorteil zunichte macht.

Reines C90 unterstützt ja auch "nur" die double-Version, wobei man hier ohne größeren Fingerabdruck natürlich auch noch andere Mathebibliotheken hinzuziehen kann, bzw. ab C99 ja sowieso sinf() verfügbar ist.

Das ist einer der ganz großen Vorteile von C++: Dank Überladung gibt es sin(float), sin(double) und sin(long double). Das gleiche gilt für sqrt, cos, atan und alle anderen "Familienmitglieder". :)

Faktor 4 ist schon gewaltig, wenn man wirklich auf ein gewisses Maß an Genauigkeit verzichten kann.

2
Kommentar von hypergerd
30.12.2015, 22:45

Doch, selbst einbauen, wenn:

  • man mehr als double (15 Stellen) benötigt
  • komplexe Zahlen berechnen will (nur wenige Sprachen haben zig Funktionen mit komplexen Zahlentypen)
  • mehr als die 10 "Schulfunktionen" benötigt (es gibt über 300)
  • richtige Ergebnisse bei exotischen Argumenten benötigt (teste mal Deine Programmiersprache auf sin(9.3e18)
2

So eine Taylorentwicklung hier zu entwickeln, ist ein Ding der Unmöglichkeit. Einen Eindruck bekommst du hier und auch an anderen Stellen im Internet. Der Vorteil ist, dass sie je nach Kapazität des Rechners abgebrochen werden können und dann für die Anzeigemöglichkeit genügend genau sind.

http://www.uni-magdeburg.de/exph/mathe_gl/taylorreihe.pdf

Antwort bewerten Vielen Dank für Deine Bewertung

Das Handbook of Mathematical Functions von Abramowitz und Stegun nennt Iterationen und Reihenentwicklungen, die leicht zu programmieren sind, und mit denen man solche Funktionen rasch approximieren kann. Das Buch ist vollständig online. Für die Wurzel schau in Abschnitt 3.9.6. auf S. 18. Für cos und log schau in Kapitel 4 (Elementary Transcendental Functions) nach.

https://de.wikipedia.org/wiki/Abramowitz-Stegun

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?