Algorithmen für mathematische Operationen

hustbaer

Computer rechnen meist auch nicht anders, als Mathematiker im Zeitalter vor dem Computern gerechnet haben.
OK, manche Algorithmen werden durch das Binärsystem einfacher.
Andere wurden vermutlich angepasst, weil etwas was auf dem Papier komplizierter wäre in Hardware trotzdem schneller ist.

Im Prinzip bleibt es aber das selbe.

@ SeppJ: Danke, die kannte ich noch nicht.
Ich habe nach ein paar Begriffen gegooglet und insgesamt einen Forenbeitrag mit einer Formel zur ln-Annäherung gefunden.
Diese wurde aber "schnell" (für sechsstellige Zahlen) ungenau. Außerdem geht es mir nicht darum, irgendeine Methode zu finden, sondern die beste bzw. genauste.

@ hustbear: Und diese Algorithmen aus der untergegangenen Kultur suche ich. Ich habe z.B. schonmal etwas von Logarithmentafeln gelesen. Sind diese aber klein, ist das Ergebnis falsch, sind sie zu groß, wäre viel Speicher benötigt.

SeppJ

Wurst schrieb:

@ SeppJ: Danke, die kannte ich noch nicht.

Das merkt man .

Diese wurde aber "schnell" (für sechsstellige Zahlen) ungenau. Außerdem geht es mir nicht darum, irgendeine Methode zu finden, sondern die beste bzw. genauste.

Und wieso sollte man im Computer die genaueste benutzen? Und wie definierst du beste?

volkard

Wurst schrieb:

sondern auch Logarithmen, Wurzeln und andere, die mir gerade nicht einfallen

Vielleicht ist http://de.wikipedia.org/wiki/Bitalgorithmen auch ein guter Suchanfang.

audacia

Trigonometrische Funktionen kann man z.B. schon mit wenigen Gliedern ihrer Taylorreihe recht genau berechnen. Allerdings muß man meist etwas tricksen, damit der Algorithmus überall gleichermaßen stabil bleibt (etwa: bei Sinus und Cosinus das Argument auf [-π/2,π/2] normieren; bei ln nicht um die 0 entwickeln etc.).

Leider kann man die Implementation meist nicht im Quelltext der Laufzeitbibliothek nachlesen, da die meisten Compiler einfach die entsprechenden Features von FPU oder SSE-Einheit benutzen. Wie moderne CPUs das implementieren, weiß ich daher nicht.

Allerdings könntest du einfach im Quelltext von arbitrary-precision-Bibliotheken nachlesen, wie die das machen. Beispielsweise der arcsin in apfloat:

// LGPL-Code (ApfloatMath.java, l. 1610ff)
    public static Apfloat asin(Apfloat x)
        throws ArithmeticException, ApfloatRuntimeException
    {
        Apfloat one = new Apfloat(1, Apfloat.INFINITE, x.radix());
        Apcomplex i = new Apcomplex(Apfloat.ZERO, one);

        return ApcomplexMath.log(sqrt(one.subtract(x.multiply(x))).subtract(i.multiply(x))).imag().negate();
    }

(Oh, und es wäre so viel schöner, wenn Java Operatorüberladung erlauben würde )

Dein Suchwort ist CORDIC

SeppJ

audacia schrieb:

Trigonometrische Funktionen kann man z.B. schon mit wenigen Gliedern ihrer Taylorreihe recht genau berechnen. Allerdings muß man meist etwas tricksen, damit der Algorithmus überall gleichermaßen stabil bleibt (etwa: bei Sinus und Cosinus das Argument auf [-π/2,π/2] normieren; bei ln nicht um die 0 entwickeln etc.).

Die trigonometrischen Funktionen sind doch eher Beispiele für Funktionen die nicht so gut funktionieren. Überhaupt ist die Taylorentwicklung eher akademisch und wird vermutlich nirgends praktisch benutzt um Funktionswerte zu berechnen. Konvergiert einfach viel zu lahm und zu unzuverlässig im Vergleich zu spezialisierteren Verfahren.

audacia

Ja, den ln taylort wohl niemand ernsthaft; aber bei trigonometrischen Funktionen sind die Eigenschaften doch eigentlich nicht so schlecht, zumindest konvergiert die sin-/cos-Reihe doch recht fix?

Allerdings sagt die Wikipedia-Seite zu CORDIC (guter Verweis, das kannte ich noch nicht) auch, daß Taylorreihen in der Praxis selten sind. CORDIC scheint überhaupt ein prominenter Kandidat für solche Berechnungen zu sein.

Andererseits werden Taylorreihen durchaus für das Berechnen von Funktionen benutzt, wenn auch aufgrund der Defizite, die du erwähnst, eher als Zwischenschritt. Beispielsweise da: http://mesa.ece.wisc.edu/publications/cp_1995-04.pdf

@ SeppJ:

Und wieso sollte man im Computer die genaueste benutzen?

Was ist das für eine Frage?
Ich sollte sie benutzen, weil ich es will.

Und wie definierst du beste?

Möglichst genau und schnell. Ersteres ist wichtiger. Wenn möglich natürlich einfach zu verstehne

@ volkard:
Ich werde es mir mal genauer ansehen, wenn ich Zeit finde (Schule hat ja wieder angefangen ).
Beim Überfliegen ist mir aufgefallen: 1 < Argument < 4,768
Ist das generell für diesen Algorithmus so oder lässt sich das einfach ändern?

@ audacia:
"Taylorreihe" - noch ein schöner Begriff, den ich mir ansehen muss, wenn ich Zeit habe.
Die Bibliothek sieht interessant aus und da es sie wohl auch in C++ gibt, muss ich nichtmal Java lernen

@ DirkB:
Es gilt dasselbe wie für volkard und audacia - ich werde versuchen, mir CORDIC genauer anzusehen, sobald ich Zeit dafür finde.

SeppJ

Wurst schrieb:

@ SeppJ:

Und wieso sollte man im Computer die genaueste benutzen?

Was ist das für eine Frage?
Ich sollte sie benutzen, weil ich es will.

Deine Frage war nach dem, wie das im Computer gemacht wird und da macht es keinen Sinn, auf extreme Genauigkeit zu gehen.

Möglichst genau und schnell. Ersteres ist wichtiger. Wenn möglich natürlich einfach zu verstehne

Wenn du mittendrin deine Frage änderst, kann man dir nicht optimal helfen. Ist deine Frage also "Welche einfach zu verstehenden Algorithmen könnt ihr mir nennen, um damit Logarithmen und Wurzeln numerisch zu berechnen?" ?

"Taylorreihe" - noch ein schöner Begriff, den ich mir ansehen muss, wenn ich Zeit habe.

Ehrliche Antwort: Du bist mathematisch noch nicht weit genug, um die anderen Verfahren zu verstehen.

Deine Frage war nach dem, wie das im Computer gemacht wird und da macht es keinen Sinn, auf extreme Genauigkeit zu gehen.

Ich hatte dabei nicht nur floats und doubles im Sinn, sondern auch Taschenrechner und noch komplexere Zahlen.
Vielleicht hätte ich den Thread auch im Mathe-Forum posten sollen, aber da wäre die Frage nach Geschwindigkeit nicht unbedingt sinnvoll gewesen.

Wenn du mittendrin deine Frage änderst, kann man dir nicht optimal helfen. Ist deine Frage also "Welche einfach zu verstehenden Algorithmen könnt ihr mir nennen, um damit Logarithmen und Wurzeln numerisch zu berechnen?" ?

Ich dachte, der Clownsmiley wäre ein eindeutig verstandenes Zeichen für einen Scherz.
Ich suche einen Algorithmus, der Logarithmen, Wurzeln, trigonometrische Funktionen u.ä. berechnet. Die Eigenschaften, die er erfüllen soll, sind folgendermaßen nach Wichtigkeit geordnet:
1. Genauigkeit
2. Geschwindigkeit, Speicherverbrauch
3. Verständlichkeit

Jetzt klar?

Ehrliche Antwort: Du bist mathematisch noch nicht weit genug, um die anderen Verfahren zu verstehen.

Ich kann es trotzdem probieren.
Wenn du Recht hast, lege ich mir die Begriffe einfach zurück und versuche es in zwei Jahren nochmal.

crt32

Wurst schrieb:

Ich suche einen Algorithmus, der Logarithmen, Wurzeln, trigonometrische Funktionen u.ä. berechnet.

Das sind jeweils völlig verschiedene Ansätze.

Wurzeln berechnen kannst du dir zB mal reinziehen, da macht man idR ne Newton Iteration um x^2 - a = 0 zu lösen.
Das kannst du auch leicht mit deiner Schulmathematik (?) verstehen.
In dem Zusammenhang ist der bekannte "invsqrt" Algorithmus von Quake3 ganz lustig anzusehen.

Wenns dich wirklich interessiert, kannst du auch versuchen mal irgendwas Einführendes in den Bereich Numerik zu lesen. Da kannst du dir erstmal die mathematischen Grundbegriffe aneignen. Taylor-Entwicklung musst du dir da aber vorher anschauen; das wird recht häufig gebraucht, für Fehlerabschätzungen und ähnliches.

Ich suche jeweils einen Algorithmus, der Logarithmen, Wurzeln, trigonometrische Funktionen u.ä. berechnet.

Verbessert.