Ich bin gerade auf die Kahan (or compensated) summation algorithm for minimizing roundoff gestoßen, und ich würde gerne wissen, ob es äquivalente Algorithmen für Division und/oder Multiplikation sowie Subtraktion gibt eins sein, ich weiß über Assoziativität). Implementierungsbeispiele in jeder Sprache, Pseudocode oder Links wären großartig!Minimierung der Auswirkung von Rundungsfehlern, die durch wiederholte Operationen verursacht werden
Dank
Subtraction ist in der Regel über die Kahan-Methode behandelt. Für die Multiplikation gibt es Algorithmen, um ein Produkt aus zwei Gleitpunktzahlen in eine Summe von zwei Gleitkommazahlen ohne Rundung zu konvertieren. An diesem Punkt können Sie die Kahan- Addition oder eine andere Methode verwenden, je nachdem, was Sie benötigen als nächstes mit dem Produkt zu tun.
Wenn Sie FMA (fusioniert Multiply-Add) zur Verfügung, kann dies leicht erreicht werden, wie folgt:
p = a*b;
r = fma(a,b,-p);
Nach diesen beiden Operationen, wenn keine Über- oder Unterlauf auftritt, p + r genau gleich a * b ohne Rundung. Dies kann auch ohne FMA erreicht werden, ist jedoch etwas schwieriger. Wenn Sie sich für diese Algorithmen interessieren, können Sie beginnen, indem Sie die crlibmdocumentation herunterladen, die einige von ihnen beschreibt.
Division ... Nun, Division ist am besten zu vermeiden. Die Division ist langsam und die kompensierte Division ist noch langsamer. Sie können es tun, aber es ist brutal schwer ohne FMA und nicht-trivial damit. Besser, deine Algorithmen so zu gestalten, dass sie so weit wie möglich vermieden werden.
Beachten Sie, dass all dies eine verlorene Schlacht ziemlich schnell wird. Es gibt eine sehr kleine Bandbreite von Situationen, in denen diese Tricks nützlich sind - für etwas Komplizierteres ist es viel besser, einfach eine Gleitkomma-Bibliothek mit einer größeren Genauigkeit wie mpfr zu verwenden. Wenn Sie kein Experte auf diesem Gebiet sind (oder einer davon werden wollen), ist es normalerweise am besten, nur eine solche Bibliothek zu erlernen.
Entwerfen von Algorithmen zu numerically stable ist eine akademische Disziplin und Forschungsgebiet an sich. Es ist nicht etwas, was Sie sinnvoll über "Spickzettel" tun (oder lernen können) - es erfordert spezifische mathematische Kenntnisse und muss für jeden spezifischen Algorithmus getan werden. Wenn Sie lernen möchten, wie dies zu tun ist, klingt die Referenz in der Wikipedia-Artikel ziemlich gut: Nicholas J. Higham, Genauigkeit und Stabilität von numerischen Algorithmen, Gesellschaft für industrielle und angewandte Mathematik, Philadelphia, 1996. ISBN 0-89871-355- 2.
Ein relativ einfacher Weg zu Diagnose die Stabilität eines Algorithmus ist interval arithmetic zu verwenden.
Das Ziel der kompensierten Arithmetik verbessert normalerweise nicht die Stabilität. Meistens ist es eine harte Genauigkeit, die an einen stabilen Algorithmus gebunden ist. –
Interessant, danke für die Links, die ich mir ansehen werde, wenn ich eine Chance bekomme! – Geoff
@ Stephen, Ah. Ich wusste nicht, dass es einen Unterschied gab. : S Immer noch interessant. :) – Geoff
Sie könnten Bignums und rationale Brüche anstelle von Fließkommazahlen verwenden. In diesem Fall sind Sie nur durch die begrenzte Verfügbarkeit von Speicher beschränkt, um die erforderliche Genauigkeit zu halten.
Leistung möglicherweise ein Problem obwohl –
Keine Option, der Löser ist bereits Speicher gebunden. Trotzdem danke. – Geoff
AFAIK, mit breiteren Typen ist nur eine schlechte Hilfe und wird sehr wenig helfen, wenn Ihr Problem schlecht konditioniert oder Ihr Algorithmus nicht stabil ist. –
@Michael Borgwardt: Das hängt vom Problem ab. Wenn Ihr Problem schlecht konditioniert ist, dann sind entweder Ihre Eingabedaten exakt (in diesem Fall wird die Erhöhung der Genauigkeit tatsächlich helfen, sobald Sie einen Schwellenwert überschreiten), oder die Antwort ist sowieso bedeutungslos (in diesem Fall spielt es keine Rolle). Wenn Ihr Algorithmus instabil ist, hängt dies von der genauen Art der Instabilität ab. Allgemeiner kann jedoch jedes Problem, das durch die Verwendung von kompensierter Arithmetik behoben werden kann, auch durch Verwendung breiterer Typen gelöst werden. –
So neugierig wie ich bin, so gern ich alles über alles wissen würde, ich weiß, ich werde mich erst einmal mit Bibliotheken und ähnlichem beschäftigen müssen, vielen Dank für Ihre Antwort, ich werde es mir ansehen so schnell wie möglich. :) – Geoff