Es ist kein Geheimnis, dass Finanzinformationen (Konten, Buchungen und andere Buchhaltung) mit Gleitkommazahlen nicht sehr freundlich sind, und viele Artikel empfehlen die Verwendung einer Festkomma-Arithmetik. In Java wird dieses Format tatsächlich nur durch die BigDecimal-Klasse dargestellt, die aus Leistungsgründen nicht immer verwendet werden kann. Wir müssen nach Alternativen suchen. Dieser Artikel beschreibt eine selbstgeschriebene Java-Bibliothek zum Ausführen von arithmetischen Operationen für Zahlen mit fester Genauigkeit. Die Bibliothek wurde für die Verwendung in leistungsstarken Finanzanwendungen erstellt und ermöglicht es Ihnen, mit einer Genauigkeit von 9 Dezimalstellen zu arbeiten und dabei eine akzeptable Leistung beizubehalten. Ein Link zu den Quellen und Benchmarks befindet sich am Ende des Artikels.

Gleitkomma-Arithmetik

Moderne Computer können arithmetische Operationen nur mit begrenzter Genauigkeit ausführen. Dies sind diskrete Geräte, die möglicherweise nicht mit allen möglichen Zahlen arbeiten, sondern nur mit einer abzählbaren Teilmenge davon. Das gebräuchlichste Format für die Arbeit mit reellen Zahlen im Computerspeicher ist Gleitkomma (Binärpunkt) - Gleitkomma (Binärpunkt), wenn Zahlen in der Form M * 2 ^ E gespeichert sind, wobei M und E eine ganzzahlige Mantisse und die Reihenfolge der Zahl sind. Einige Zahlen, wie z. B. 0,1, können in diesem Format jedoch nicht genau dargestellt werden. Daher häufen sich bei komplexen Berechnungen zwangsläufig einige Fehler an. Das heißt, das Ergebnis der Maschinenberechnung, beispielsweise 0,1 + 0,1 + 0,1, stimmt nicht mit der mathematisch korrekten 0,3 überein. In Anbetracht des oben Gesagten können Sie beim Programmieren komplexer Arithmetik verschiedene Strategien verfolgen:

Strategie 1 - ignorieren. Ignorieren Sie den Fehler, betrachten Sie alle Operationen als ideal mathematisch und hoffen Sie, dass die verfügbare Genauigkeit für akzeptable Ergebnisse ausreicht. Die häufigste Option.

Strategie 2 - akribisch berechnen. Formeln zur Berechnung von Maschinenfehlern sind seit Jahrzehnten bekannt. Sie ermöglichen es, den relativen Fehler einer arithmetischen Operation von oben abzuschätzen. Wahrscheinlich ist dies das, was Sie für eine ernsthafte numerische Simulation tun müssen. Das Problem ist, dass es sehr zeitaufwändig ist. Tatsächlich muss jedem + - * / Zeichen im Code eine Fehlerberechnung beigefügt sein. Sie müssen alle Abhängigkeiten zwischen den Berechnungen berücksichtigen und den Vorgang jedes Mal wiederholen, wenn Sie den Code ändern.

Strategie 3 - Verwenden Sie einen Dezimalpunkt (Gleitkomma) anstelle eines Binärpunkts. Speichern Sie die Zahlen in der Form M * 10 ^ E. Dies löst nicht die Fehlerprobleme (die Mantisse ist 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. Die Rückzahlung wird Leistung sein. Jede Normalisierung von Zahlen (dh eine äquivalente Abnahme der Mantisse und eine Zunahme der Ordnung) erfordert eine Division durch eine Potenz von 10, was im Gegensatz zu einer Division durch eine Potenz von 2 nicht sehr schnell ist. Und Sie müssen viel normalisieren - bei jeder Addition oder Subtraktion mit unterschiedlichen Ordnungen.

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

Festkomma-Arithmetik

Im Gegensatz zur Physik, in der relative Fehler wichtig sind, wird im Finanzbereich nur das Absolute benötigt. Wenn dem Kunden nach einer komplexen Finanztransaktion 1.000.000,23 USD in Rechnung gestellt werden, während er 1.000.000,18 USD erwartet, können einige Schwierigkeiten auftreten. Erklärungen wie "Warum brauchen Sie Genauigkeit in 8 signifikanten Stellen?" darf nicht reiten. Dabei geht es nicht um 5 Cent Verlust (im Gegenteil, „zugunsten“ des Kunden ist nicht viel besser), sondern um Inkonsistenzen in der Rechnungslegung. Daher sind die Regeln für Berechnungen und Rundungen zwischen den Parteien klar festgelegt, und Artefakte aus der Verwendung von Double- und Float-Variablen erschweren manchmal das Leben.

Java hat eine Standardklasse für Festkomma-Arithmetik - BigDecimal. Es gibt zwei Probleme: Es ist langsam (aufgrund seiner Universalität) und es ist nicht stabil. Nichtstabilität bedeutet, dass jede Operation ein Objekt auf dem Heap zuweist. Das Auswählen und Freigeben eines Objekts dauert etwas, aber intensive Berechnungen im „heißen“ Code führen zu einer angemessenen Belastung des GC, was in einigen Fällen nicht akzeptabel ist. Sie können sich auf Escape-Analyse und Skalierung verlassen, aber sie sind sehr instabil in dem Sinne, dass selbst eine geringfügige Änderung des Codes oder der JIT (z. B. das verzögerte Laden einer neuen Schnittstellenimplementierung) die gesamte Inline-Struktur auf den Kopf stellen kann und die Methode vor einer Minute einwandfrei funktioniert hat. plötzlich beginnt wütend Erinnerung zuzuweisen.
UPD aufgrund von Fragen in den Kommentaren: Der Hauptgrund für den Verzicht auf BigDecimal und BigInteger ist keineswegs eine geringe Rechenleistung, sondern mangelnde Stabilität und Auswahl von Objekten.

Die beschriebene Bibliothek ist das Ergebnis der Müdigkeit, die Festkomma-Nicht-Speicher-Arithmetik für jeden neuen Arbeitgeber von Grund auf neu zu schreiben, und ich habe beschlossen, meine eigene Bibliothek für das spätere Insourcing zu schreiben.

Ich werde sofort ein Anwendungsbeispiel zeigen, bevor ich mit den Implementierungsdetails fortfahre:

public class Sample { private final Decimal margin; private final Quantity cumQuantity = new Quantity(); private final Quantity contraQuantity = new Quantity(); private final Quantity cumContraQuantity = new Quantity(); private final Price priceWithMargin = new Price(); private final Price avgPrice = new Price(); public Sample(int marginBp) { // 1 + margin / 10000 this.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); } public static void main(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})); } } 

Implementierungsidee

Wir brauchen also einen veränderlichen Wrapper eines ganzzahligen Grundelements, genauer gesagt eines Long'a, der uns fast 19 signifikante Stellen gibt (genug für die Ganzzahl und den Bruchteil). Langfristig meinen wir N Dezimalstellen. Beispielsweise wird bei N = 2 die Zahl 2,56 als 256 (binär 100000000) gespeichert. Negative Zahlen werden standardmäßig in zusätzlichem Code gespeichert:

-2,56
-256

(Im Folgenden werden kursiv „mathematische“ Zahlen und Berechnungen und in Fettdruck ihre interne Darstellung angegeben.)

Es erschien mir auch nützlich, NaN als separaten Wert einzugeben, der bei Rechenfehlern (anstelle einer Ausnahme oder eines Mülls) zurückgegeben wird. NaN wird intern als Long.MIN_VALUE dargestellt , durch alle Operationen "weitergegeben" und ermöglicht die Bestimmung der Vorzeichenumkehr für alle verbleibenden Zahlen.

Versuchen wir, die Algorithmen der arithmetischen Operationen für den Fall zu schätzen, in dem 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 Aufteilung ist nicht die schnellste Operation. In diesem Fall ist dies jedoch eine Division durch eine Konstante, da wir zuvor N = 2 und 10 ^ N = 100 festgelegt haben. Die Division durch Konstante, insbesondere durch „schön“ (Typ 10), wird in der CPU intensiv optimiert und ist viel schneller als die Division durch eine Zufallszahl. Wir dividieren jedes Mal durch 10, wenn wir eine Zahl in eine Zeichenfolge konvertieren (z. B. in den Protokollen), und die CPU-Hersteller wissen davon ( weitere Einzelheiten zu Optimierungen finden Sie unter "Division durch eine Konstante").

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

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

Nun, obwohl alles recht einfach ist, versuchen wir, die Details zu untersuchen.

Rundung

Versuchen wir eine andere Zahl zu ziehen:

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 uns nicht genau vorstellen. Welchen Weg umrunden? Normalerweise auf 0 gerundet, und dies ist der schnellste Weg (Hardware unterstützt). Zurück zu den tatsächlichen finanziellen Problemen ist dies jedoch nicht immer der Fall. Bei der Verarbeitung von Transaktionen mit einem Kunden erfolgt die Rundung in der Regel "zugunsten des Kunden". Das heißt, der Preis wird aufgerundet, wenn der Kunde verkauft, und gesenkt, wenn der Kunde kauft. Es können jedoch auch andere Optionen erforderlich sein, z. B. das arithmetische Runden auf die nächste Zahl mit Untertypen (halb hoch, halb runter, halb gerade), um Buchhaltungsinkonsistenzen zu minimieren. Oder für negative Preise auf ± unendlich runden (für einige Finanzinstrumente). Java BigDecimal enthält bereits eine Liste der Standardrundungsmodi, und die beschriebene Bibliothek unterstützt alle. UNNECESSARY gibt NaN zurück, wenn der Vorgang unerwartet gerundet werden muss.

Im Aufrundungsmodus sollte unsere Berechnung Folgendes ergeben:

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

Wie finde ich heraus, was Sie zum Hinzufügen einer Einheit benötigen? Sie benötigen den Rest der Division 10.000% 300 = 100. Das ist so langsam wie die Division selbst. Wenn Sie in einer Zeile in den Code "a / b; a% b" schreiben, erkennt JIT glücklicherweise, dass keine 2 Unterteilungen erforderlich sind, sondern nur ein Assembler-Div-Befehl, der 2 Zahlen zurückgibt (Quotient und Rest).

Andere Rundungsoptionen sind etwas komplizierter, können aber auch anhand des Rests und des Divisors berechnet werden.

In der API habe ich absichtlich die Rundung erwähnt, wo immer sie auftritt, entweder als Parameter oder als Rund- D- eigenes Suffix in Methoden, bei denen der Standardwert Null ist.

Überlauf

Wir kommen zum schwierigsten Teil. Erinnern Sie sich noch einmal an unsere Multiplikation:

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

Stellen Sie sich jetzt vor, wir sind in den 1980er Jahren und haben 16-Bit-Prozessoren. Das heißt, es steht uns nur Short mit einem Maximalwert von 65535 zur Verfügung. Die erste Multiplikation läuft über und ist gleich 240000 & 0xFFFF = 44392 (wenn sie nicht vorzeichenbehaftet ist, mit einem Vorzeichen ist sie auch negativ), was das Ergebnis für uns bricht.

Es wird nicht funktionieren. Wir haben 2 normale Argumente (passen in unseren Wertebereich) und das gleiche normale erwartete Ergebnis, aber wir laufen zur Hälfte über. Genau die gleiche Situation ist mit einem 64-Bit-Long'om möglich, nur Zahlen brauchen mehr.

In den 1980er Jahren würden wir eine Multiplikation benötigen, die ein 32-Bit-Ergebnis ergibt. Heute brauchen wir eine Multiplikation mit einem 128-Bit-Ergebnis. Am ärgerlichsten ist, dass beide Multiplikationen in den Assemblern 8086 und x86-64 verfügbar sind, aber wir können sie nicht von Java aus verwenden! JNI verursacht selbst bei einem Hack mit schnellem JavaCritical einen Overhead von mehreren zehn Nanosekunden, führt zu Schwierigkeiten bei der Bereitstellung und Kompatibilität und friert den GC für die Dauer des Aufrufs ein. Außerdem müssten wir irgendwie ein 128-Bit-Ergebnis von der nativen Methode zurückgeben, und das Schreiben unter Bezugnahme auf ein 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 des festen Multiplikationspunktes A * B.
2. N (32) * A (64) = T (96); T (96) / B (64) = Q (64), R (64) - als Teil der Festpunktteilung A / B.
   (In Klammern wird die Dimension der Daten in Bits angegeben. T ist eine temporäre Variable, die nicht überlaufen darf.)

Beide Operationen geben den Quotienten und den Rest zurück (eine als Ergebnis der Methode, die zweite im Objektfeld). Sie können auch überlaufen, aber nur im letzten Schritt, wenn dies unvermeidlich ist. Hier ein Beispiel (aus den 1980er Jahren):

500,00 / 0,50 = 1000,00
100 * 50.000 / 50 = 100.000 - Überlauf!

Die Spaltenteilung a la Knut ist nicht der einfachste Algorithmus. Außerdem sollte es auch relativ schnell sein. Daher besteht der Code beider Operationen aus Hunderten von Zeilen ziemlich strenger Bitmagie. Ich werde viel Zeit brauchen, um mich wieder daran zu erinnern, was genau dort passiert. Ich zog sie in eine separate Klasse und kommentierte sie ausführlich, so gut ich konnte.

Der Multiplikationsalgorithmus ist nicht auf das Aufrufen von Operation 1 beschränkt, aber der verbleibende Code ist nicht so kompliziert und fügt nur Unterstützung für negative Zahlen, Rundungen und NaN hinzu.

Normalerweise (außer in besonderen Fällen) enthalten beide Operationen 4 Multiplikationen und 2 Divisionen. Operation 1 ist deutlich schneller als 2, da diese Unterteilungen darin durch eine Konstante sind.

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

Mehrere unterschiedliche Präzision

Manchmal ist es notwendig, eine Operation für Argumente mit einer anderen Anzahl von Dezimalstellen auszuführen. Geben Sie mindestens Operationen mit der üblichen Länge ein.

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 + 20.000 / 100 = 500

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

Die Anzahl der Dezimalstellen 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 größer die Genauigkeit, desto kleiner der Bereich der gespeicherten Werte, desto kleiner ist der Dezimalbereich 9: ± 9223372036. Es wird davon ausgegangen, dass eine oder zwei Klassen ausreichen, um die erforderliche Funktionalität abzudecken. In diesem Fall wird die abstrakte Methode getScale höchstwahrscheinlich devirtualisiert und inline. Mit Unterklassen (anstelle eines zusätzlichen Felds) können Sie die Genauigkeit der Argumente und des Ergebnisses genau angeben und auf mögliche Rundungen in der Kompilierungsphase hinweisen.

Die Bibliothek ermöglicht Operationen mit maximal 2 (aber nicht 3) unterschiedlicher Genauigkeit. Das heißt, entweder muss die Genauigkeit der beiden Argumente übereinstimmen, oder die Genauigkeit eines der Argumente und des Ergebnisses. Auch hier würde die Unterstützung von 3 verschiedenen Genauigkeiten den Code erheblich verlangsamen und die API komplizieren. Als Argumente können Sie ein reguläres Long übergeben, für das eine Genauigkeit von N = 0 angenommen wird.

2,0000 / 3,0 = 0,6667 - ok (2 unterschiedliche Präzision)
2/3 = 0,6667 - ok (lange Argumente, Dezimalergebnis)
2 / 3.0 = 0.6667 - unmöglich! (3 verschiedene Präzision)

Vor- und Nachteile

Offensichtlich ist das von der Bibliothek durchgeführte High-Bit-Computing langsamer als das von der Hardware unterstützte. Der Overhead ist jedoch nicht so groß (siehe Benchmarks unten).

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

Auf dieser Grundlage wird die Bibliothek normalerweise an Orten verwendet, an denen der Verlust der absoluten Genauigkeit kritisch ist. Zum Beispiel die Berechnung genauer Finanzstatistiken unter Berücksichtigung aktueller Finanzindikatoren (Handelspositionen, PnL, ausgeführte Aufträge). Beim Netzwerkaustausch von Finanzinformationen zwischen Systemen ist es auch bequemer, Formate mit einem Dezimalpunkt (anstelle von binär) zu verwenden.

Komplexe mathematische Algorithmen (Modellierung, Statistik, Prognose) lassen sich in der Regel standardmäßig doppelt doppelt ausführen, da ihr Ergebnis auf jeden Fall nicht absolut genau ist.

Code und Benchmarks

Code

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