Schnelle Fixpunkt-Mathematik für Java-Finanzanwendungen

Es ist kein Geheimnis, dass Finanzinformationen (Rechnungen, Transaktionen und andere Buchhaltungen) mit Fließkommazahlen nicht sehr freundlich sind, und viele Artikel empfehlen die Verwendung eines Festpunkts (Festkomma-Arithmetik). In Java wird dieses Format tatsächlich nur durch die BigDecimal-Klasse dargestellt, die aus Leistungsgründen nicht immer verwendet werden kann. Sie müssen nach Alternativen suchen. Dieser Artikel beschreibt eine selbstgeschriebene Java-Bibliothek zum Ausführen von Rechenoperationen mit Zahlen mit fester Genauigkeit. Die Bibliothek wurde für die Verwendung in Finanzanwendungen mit hoher Leistung entwickelt. Sie können mit einer Genauigkeit von bis zu 9 Dezimalstellen arbeiten, während die akzeptable Leistung erhalten bleibt. Ein Link zu Quellcode und Benchmarks finden Sie am Ende des Artikels.


Fließkomma-Arithmetik


Moderne Computer können arithmetische Operationen nur mit begrenzter Genauigkeit ausführen. Dies sind diskrete Geräte, die nicht mit allen möglichen Nummern arbeiten können, sondern nur mit einigen ihrer abzählbaren Teilmengen. Das gebräuchlichste Format für das Arbeiten mit reellen Zahlen im Computerspeicher ist ein Fließkomma-Punkt (Fließkommazahl), wenn Zahlen als M * 2 ^ E gespeichert werden, wobei M und E eine Ganzzahl-Mantisse und die Reihenfolge der Zahlen sind. Einige Zahlen, z. B. 0,1, können in diesem Format jedoch nicht genau dargestellt werden. Bei komplexen Berechnungen häufen sich daher unvermeidlich einige Fehler an. Das heißt, das Ergebnis der Maschinenberechnung, beispielsweise 0,1 + 0,1 + 0,1, stimmt nicht mit dem mathematisch korrekten 0,3 überein. Vor diesem Hintergrund können Sie beim Programmieren komplexer Arithmetik mehreren Strategien folgen:


Strategie 1 - ignorieren. Achten Sie nicht auf den Fehler, betrachten Sie alle Operationen als ideal mathematisch und hoffen Sie, dass die zur Verfügung stehende Genauigkeit für akzeptable Ergebnisse ausreicht. Die häufigste Option.


Strategie 2 - gewissenhaft kalkulieren. Formeln zur Berechnung von Maschinenfehlern sind seit mehr als einem Jahrzehnt bekannt. Sie erlauben uns, den relativen Fehler einer arithmetischen Operation von oben her abzuschätzen. Wahrscheinlich, und es ist notwendig für ernsthafte numerische Modellierungen. Das Problem ist, dass es sehr zeitaufwändig ist. Tatsächlich muss jedes + - * / Zeichen im Code von einer Fehlerberechnung begleitet werden. Es ist notwendig, alle Abhängigkeiten zwischen den Berechnungen zu berücksichtigen und die Prozedur jedes Mal zu wiederholen, wenn sich der Code ändert.


Strategie 3 - Verwenden Sie einen Dezimalpunkt (Fließkomma) anstelle eines binären. Speichern Sie also Zahlen in der Form M * 10 ^ E. Dadurch werden die Probleme mit der Ungenauigkeit nicht gelöst (die Mantisse wird immer noch auf eine endliche Anzahl von signifikanten Stellen gerundet), aber zumindest alle „einfachen“ Zahlen für eine Person (wie 1.1) werden jetzt genau im Speicher dargestellt. Payback wird Leistung sein. Jede Normalisierung von Zahlen (dh eine äquivalente Reduzierung der Mantisse und eine Zunahme der Ordnung) erfordert eine Division nach Grad 10, was im Gegensatz zu einer Division nach Grad 2 nicht sehr schnell ist. Und es gibt viel zu normalisieren - mit jeder Addition oder Subtraktion mit unterschiedlichen Ordnungen.


Strategie 4 - Verwenden Sie einen festen Punkt (fester Dezimalpunkt). Vereinfachung von Strategie 3, wenn wir die Ordnung von E festlegen. In diesem Fall ist eine Normalisierung für die Addition / Subtraktion nicht erforderlich. Außerdem haben alle Berechnungen den gleichen absoluten Fehler. Diese Strategie ist dem Artikel gewidmet.


Feste Arithmetik


Im Gegensatz zur Physik, wo der relative Fehler wichtig ist, brauchen wir im Finanzwesen ein absolutes. Wenn einem Kunden nach einer komplexen Finanztransaktion 1.000.000,23 US-Dollar in Rechnung gestellt werden, während er 1.000.000 US-Dollar erwartet.18, kann es zu Schwierigkeiten kommen. Eine Erklärung für das "Ja, warum benötigen Sie eine Genauigkeit von 8 signifikanten Stellen ??", kann nicht rollen. Und es ist kein Verlust von 5 Cent (um einen Fehler zu machen, ist "zugunsten" des Kunden nicht viel besser), sondern in den Inkonsistenzen der Buchhaltung. Daher sind die Regeln für die Berechnung und die Rundung zwischen den Parteien eindeutig festgelegt, und Artefakte aus der Verwendung von Doppel- und Float-Variablen machen das Leben manchmal komplizierter.


In Java gibt es eine Standardklasse für Festkomma-Arithmetik - BigDecimal. Es gibt zwei Probleme: Es ist langsam (wegen seiner Universalität) und es ist nicht veränderbar. Nicht-Verwirrung bedeutet, dass bei jeder Operation ein Objekt auf dem Heap zugewiesen wird. Die Auswahl und Freigabe in Bezug auf das Objekt dauert etwas Zeit, aber intensive Berechnungen im Hot-Code führen zu einer ordentlichen Belastung des GC, was in einigen Fällen nicht akzeptabel ist. Sie können auf Fluchtanalyse und Skalarisierung hoffen, aber sie sind sehr instabil in dem Sinne, dass selbst eine geringfügige Änderung im Code oder in der JIT (z. B. das langsame Laden einer neuen Schnittstellenimplementierung) die gesamte Inline-Struktur auf den Kopf stellen kann. beginnen Sie plötzlich, wahnsinnig Speicher zuzuweisen.
UPD aufgrund von Fragen in den Kommentaren: Hauptgrund Die Ablehnung von BigDecimal und BigInteger ist nicht die schlechte Leistung von Berechnungen, sondern die Unbequemlichkeit und Auswahl von Objekten.


Die beschriebene Bibliothek ist das Ergebnis der Tatsache, dass ich es müde war, die nicht zuordenbaren Speicher-Festarithmetik für jeden neuen Arbeitgeber von Grund auf neu zu schreiben, und ich beschloss, meine eigene Bibliothek für das nachfolgende Insourcing zu schreiben.


Zeigen Sie sofort ein Anwendungsbeispiel, bevor Sie mit den Details der Implementierung fortfahren:


publicclassSample{
    privatefinal Decimal margin;
    privatefinal Quantity cumQuantity = new Quantity();
    privatefinal Quantity contraQuantity = new Quantity();
    privatefinal Quantity cumContraQuantity = new Quantity();
    privatefinal Price priceWithMargin = new Price();
    privatefinal Price avgPrice = new Price();
    publicSample(int marginBp){
        // 1 + margin / 10000this.margin = Decimal.create(marginBp).divRD(10000L).add(1);
    }
    public Price calculateAvgPrice(Quantity[] quantities, Price[] prices){
        cumQuantity.set(0);
        contraQuantity.set(0);
        // avg = sum(q * p * margin) / sum(q)for (int i = 0; i < quantities.length; i++) {
            cumQuantity.add(quantities[i]);
            priceWithMargin.set(prices[i]).mulRD(margin);
            contraQuantity.set(quantities[i]).mulRD(priceWithMargin);
            cumContraQuantity.add(contraQuantity);
        }
        return avgPrice.quotientRD(cumContraQuantity, cumQuantity);
    }
    publicstaticvoidmain(String[] args)throws ParseException {
        Price p1 = Price.create("1.5");
        Price p2 = Price.create(1.6);
        Quantity q1 = Quantity.create("100");
        Quantity q2 = Quantity.create(200);
        // apply 0.05% margin to the prices
        Sample sample = new Sample(5); 
        System.out.println(sample.calculateAvgPrice(new Quantity[]{q1, q2}, new Price[]{p1, p2}));
    }
}

Ideenimplementierung


Wir brauchen also einen veränderbaren Wrapper für ein Ganzzahl-Primitiv, genauer gesagt, einen Long-Wert, der uns fast 19 signifikante Ziffern ergibt (genug für den ganzen und den gebrochenen Teil). In lang meinen wir N Dezimalstellen. Wenn beispielsweise N = 2 ist, wird die Zahl 2,56 als 256 (binär 100000000) gespeichert. Negative Zahlen werden im Standard im Zusatzcode gespeichert:


-2,56
-256


(Im Folgenden werden „mathematische“ Zahlen und Berechnungen kursiv dargestellt und ihre interne Darstellung ist fett dargestellt. )


Es erschien mir auch sinnvoll, NaN als separaten Wert einzugeben, der bei arithmetischen Fehlern (anstelle von Beseitigung oder Müll) zurückgegeben wird. NaN wird intern als Long.MIN_VALUE dargestellt , propagiert alle Operationen und gibt Ihnen die Möglichkeit, die Vorzeicheninversion für alle verbleibenden Zahlen zu bestimmen.


Versuchen wir, die Algorithmen arithmetischer Operationen für den Fall zu schätzen, wenn N = 2 ist.


Addition und Subtraktion erfordern keine zusätzlichen Gesten, verwenden Sie einfach die Werte wie sie sind:


1,20 + 2,30 = 3,50
120 + 230 = 350


Multiplikation und Division erfordern eine zusätzliche Normalisierung, dh Multiplikation / Division mit 10 ^ N (in unserem Beispiel mit 100)


1,20 * 2,00 = 2,40
120 * 200/100 = 240


1,20 / 2,00 = 0,60
100 * 120/200 = 60


Zusätzliche Abteilung ist nicht die schnellste Operation. In diesem Fall ist diese Division jedoch eine Konstante, weil wir N = 2 und 10 ^ N = 100 im Voraus festgelegt haben. Die Division durch eine Konstante, insbesondere das „Schöne“ (Typ 10), ist in der CPU intensiv optimiert und viel schneller als die Division durch eine Zufallszahl. Jedes Mal, wenn wir eine Zahl in eine Zeichenfolge konvertieren (z. B. in Protokollen), machen wir viele Divisionen um 10, und die CPU-Hersteller wissen dies ( weitere Informationen finden Sie unter "Division durch eine Konstante" zur Optimierung ).


Um das Verständnis dessen, was wir tun, zu festigen, möchte ich noch eine weitere Operation machen: unäre Umkehrung einer Zahl, dh 1 / x. Dies ist ein Sonderfall der Division, Sie müssen nur 1,00 in unserem Format einreichen und vergessen Sie nicht, zu normalisieren:


1,00 / 2,00 = 0,50
100 * 100/200 = 50


Nun, während alles ziemlich einfach ist, versuchen wir, in die Details zu gehen.


Rundung


Versuchen wir eine andere Zahl zu zeichnen:


1,00 / 3,00 = 0,33
100 * 100/300 = 33


Ein ehrliches mathematisches Ergebnis liegt zwischen 0,33 und 0,34, aber wir können es nicht genau darstellen. Welchen Weg zu runden? Normalerweise auf 0 gerundet, und dies ist der schnellste (von der Hardware unterstützte) Weg. Um auf die realen finanziellen Probleme zurückzukommen, ist dies jedoch nicht immer der Fall. Bei der Abwicklung von Transaktionen mit einem Kunden erfolgt die Rundung in der Regel "zu Gunsten des Kunden". Das heißt, der Preis wird gerundet, wenn der Kunde verkauft, und er sinkt, wenn der Kunde kauft. Es können jedoch andere Optionen erforderlich sein, z. B. eine arithmetische Rundung auf die nächste Zahl mit Untertypen (Half Up, Half Down, Half Even), um Inkonsistenzen in der Buchhaltung zu minimieren. Oder für negative Preise (für einige Finanzinstrumente) auf ± unendlich. Java BigDecimal enthält bereits eine Liste mit Standardrundungsmodi, und die beschriebene Bibliothek unterstützt alle. Der UNNECESSARY-Modus gibt NaN zurück.


Im Aufrundungsmodus sollte unsere Berechnung ergeben:


1,00 / 3,00 = 0,34
100 * 100/300 + 1 = 34


Woher weiß ich, ob ich eine hinzufügen muss? Sie benötigen den Rest der Division von 10000% 300 = 100. Das ist so langsam wie die Division selbst. Glücklicherweise schreibt JIT, wenn Sie nacheinander in den Code "a / b; a% b" schreiben, dass 2 Divisionen nicht erforderlich sind, nur ein Assembler-Befehl div, der 2 Zahlen zurückgibt (Quotient und Rest).


Andere Rundungsoptionen sind etwas komplizierter, können aber auch basierend auf dem Rest und dem Divisor berechnet werden.


In der API, I erwähnt Rundung bewusst gemacht, wo es entweder als Parameter oder als Suffix tritt die R ound D selbst in der Art, wie sie standardmäßig auf Null auftritt.


Überlauf


Wir kommen zum schwierigsten Teil. Erinnere dich noch einmal an unsere Multiplikation:


1,20 * 2,00 = 2,40
120 * 200/100 = 240


Stellen Sie sich nun vor, wir befinden uns in den 80er Jahren und wir haben 16-Bit-Prozessoren. Das heißt, es steht uns nur ein Short mit einem Maximalwert von 65535 zur Verfügung. Die erste Multiplikation wird überlaufen und entspricht 240000 & 0xFFFF = 44392 (dies ist, wenn ohne Vorzeichen, mit einem Vorzeichen auch negativ), was das Ergebnis unterbricht.


Das geht nicht. Wir haben zwei normale Argumente (Werte, die in unseren Bereich passen) und das gleiche normal erwartete Ergebnis, aber wir sind auf halbem Wege überfüllt. Genau die gleiche Situation ist mit einer 64-Bit-Länge möglich, nur die Zahlen werden mehr benötigt.


In den achtziger Jahren würden wir eine Multiplikation benötigen, um ein 32-Bit-Ergebnis zu erhalten. Heute benötigen wir eine Multiplikation mit einem 128-Bit-Ergebnis. Das Ärgerlichste ist, dass beide Multiplikationen in den Assemblern 8086 und x86-64 verfügbar sind, aber von Java nicht verwendet werden können! JNI verursacht selbst bei einem Hack mit schnellem JavaCritical den Overhead in Dutzenden von Nanosekunden, führt zu Problemen bei der Bereitstellung und Kompatibilität und friert den GC für die Dauer des Anrufs ein. Außerdem müssten wir irgendwie ein 128-Bit-Ergebnis von der systemeigenen Methode zurückgeben, und das Schreiben per Verweis auf das Array (im Speicher) ist eine zusätzliche Verzögerung.


Im Allgemeinen musste ich manuelle Multiplikation und Division schreiben. Spalte Ich brauchte 2 Hilfsoperationen:


  1. A (64) * B (64) = T (128); T (128) / N (32) = Q (64), R (32) - als Teil der Festkommamultiplikation A * B
  2. N (32) * A (64) = T (96); T (96) / B (64) = Q (64), R (64) - als Teil des Fixpunkts der Division A / B
    (Datengröße in Bits ist in Klammern angegeben, T ist eine temporäre Variable, die nicht überlaufen sollte)

Beide Operationen geben einen Quotienten und einen Rest zurück (eine - als Ergebnis der Methode, die zweite - im Feld des Objekts). Sie können auch überlaufen, aber nur im letzten Schritt, wenn es unvermeidlich ist. Hier ist ein Beispiel (aus den 1980ern):


500,00 / 0,50 = 1000,00
100 * 50000/50 = 100000 - Überlauf!


Die Aufteilung der Spalte a la Knut ist nicht der einfachste Algorithmus. Außerdem sollte alles relativ schnell sein. Daher besteht der Code beider Operationen aus Hunderten von Zeilen mit ziemlich hartem Bitmaking. Es wird lange dauern, bis ich mich daran erinnere, was genau dort vor sich geht. Ich zog sie in eine separate Klasse und kommentierte sie so detailliert wie möglich.


Der Multiplikationsalgorithmus ist nicht auf die Aufrufoperation 1 beschränkt, der verbleibende Code ist jedoch nicht so kompliziert und fügt lediglich die Unterstützung für negative Zahlen, Rundungen und NaN hinzu.


Normalerweise (mit Ausnahme von Sonderfällen) enthalten beide Operationen 4 Multiplikationen und 2 Divisionen. Operation 1 ist deutlich schneller als 2, da diese Spaltungen eine konstante sind.


Wenn jemand bemerkt hat, ist N (32) übrigens unser 10 ^ N für die Normalisierung. Es ist 32 Bit, was bedeutet, dass N maximal 9 sein kann. In den realen Anwendungen, die ich gesehen habe, wurden 2, 4 oder 8 Dezimalstellen verwendet. Mehr als 9 habe ich noch nicht getroffen, also sollte das reichen. Wenn Sie 10 ^ N 64-Bit erstellen, wird der Code noch komplizierter (und verlangsamt sich).


Mehrere unterschiedliche Genauigkeit


Manchmal ist es erforderlich, eine Operation mit Argumenten mit einer anderen Anzahl von Dezimalstellen auszuführen. Geben Sie mindestens Transaktionen ein, die die übliche Länge beinhalten.


Z.B:


2,0000 (N = 4) + 3,00 (N = 2) = 5,0000 (N = 4)
20 000 + 300 * 100 = 50 000


3,00 (N = 2) + 2,0000 (N = 4) = 5,00 (N = 2)
300 + 20000/100 = 500


In diesem Fall ist eine zusätzliche Normalisierung eines der Argumente erforderlich. Beachten Sie, dass mathematisch beide Operationen gleichwertig sind, aber aufgrund der anderen Genauigkeit des Ergebnisses anders berechnet werden. Es ist auch erwähnenswert, dass die zweite Operation im Allgemeinen eine Rundung erfordert.


Die Anzahl der Nachkommastellen wird NICHT im Objekt gespeichert. Stattdessen wird für jede Genauigkeit eine separate Unterklasse angenommen. Klassennamen können geschäftsorientiert sein, z. B. Preis (N = 8), Menge (N = 2). Und sie können verallgemeinert werden: Dezimal1, Dezimal2, Dezimal3, ... Je höher die Genauigkeit, desto kleiner ist der Bereich der gespeicherten Werte, der Mindestbereich hat Dezimal9: ± 9223372036. Es wird angenommen, dass eine oder zwei Klassen ausreichen, um die erforderliche Funktionalität abzudecken. In diesem Fall wird die abstrakte getScale-Methode höchstwahrscheinlich devirtualisiert und inline sein. In Unterklassen (anstelle eines zusätzlichen Feldes) können Sie die Genauigkeit der Argumente und des Ergebnisses genau angeben und mögliche Rundungen in der Übersetzungsphase signalisieren.


Die Bibliothek ermöglicht Operationen, an denen maximal 2 (aber nicht 3) unterschiedlicher Genauigkeit beteiligt sind. Das heißt, entweder muss die Genauigkeit der beiden Argumente übereinstimmen oder die Genauigkeit eines der Argumente und das Ergebnis. Die Unterstützung für 3 verschiedene Genauigkeiten würde den Code verlangsamen und die API komplizieren. Als Argumente können Sie die gewöhnliche Länge übergeben, für die eine Genauigkeit von N = 0 angenommen wird.


2.0000 / 3.0 = 0.6667 - ok (2 unterschiedliche Genauigkeit)
2/3 = 0.6667 - ok (lange Argumente, Dezimalergebnis)
2 / 3.0 = 0.6667 - unmöglich! (3 unterschiedliche Genauigkeit)


Stärken und Schwächen


Offensichtlich sind die Berechnungen mit erhöhter Bittiefe, die von der Bibliothek ausgeführt werden, langsamer als die unterstützte Hardware. Der Overhead-Projektor ist jedoch nicht so groß (siehe Benchmarks unten).


Aufgrund der fehlenden Überladung von Operatoren in Java wird die Wahrnehmung von Code durch die Verwendung von Methoden anstelle von arithmetischen Operatoren kompliziert.


Auf dieser Grundlage wird die Bibliothek normalerweise an Orten verwendet, an denen der Verlust der absoluten Genauigkeit von entscheidender Bedeutung ist. Zum Beispiel die Berechnung genauer Finanzstatistiken, die Berücksichtigung aktueller Finanzkennzahlen (Handelspositionen, PnL, Ausführungsaufträge). Im Falle eines Netzwerkaustauschs von Finanzinformationen zwischen Systemen ist es auch praktischer, Formate mit Dezimalzeichen (anstelle von binär) zu verwenden.


Komplizierte mathematische Algorithmen (Modellierung, Statistik, Prognose) sind in der Regel einfacher doppelt auszuführen, da ihr Ergebnis auf jeden Fall nicht absolut genau ist.


Code und Benchmarks


Code


BenchmarkModusCntScoreFehlerEinheiten
DecimalBenchmark.controlDurchschn20010.072± 0,074ns / op
DecimalBenchmark.multiplyNativeDurchschn20010.625± 0,142ns / op
DecimalBenchmark.multiplyMyDecimalDurchschn20035.840± 0,121ns / op
DecimalBenchmark.multiplyBigDecimalDurchschn200126.098± 0,408ns / op
DecimalBenchmark.quotientNativeDurchschn20070.728± 0,230ns / op
DecimalBenchmark.quotientMyDecimalDurchschn200138.581± 7,102ns / op
DecimalBenchmark.quotientBigDecimalDurchschn200179.650± 0,849ns / op

Im Allgemeinen ist die Multiplikation viermal schneller als BigDecimal, die Division ist 1,5. Die Teilungsrate hängt stark von den Argumenten ab, daher von der Streuung der Werte.


Jetzt auch beliebt: