Ce n'est un secret pour personne que les informations financières (comptes, écritures et autres livres comptables) ne sont pas très conviviales avec les nombres à virgule flottante, et de nombreux articles recommandent d'utiliser une arithmétique à virgule fixe. En Java, ce format n'est en fait représenté que par la classe BigDecimal, qui ne peut pas toujours être utilisée pour des raisons de performances. Nous devons chercher des alternatives. Cet article décrit une bibliothèque Java auto-écrite pour effectuer des opérations arithmétiques sur des nombres à précision fixe. La bibliothèque a été créée pour fonctionner dans des applications financières hautes performances et vous permet de travailler avec une précision de 9 décimales tout en conservant des performances acceptables. Un lien vers les sources et les références est donné à la fin de l'article.

Arithmétique en virgule flottante

Les ordinateurs modernes ne peuvent effectuer des opérations arithmétiques qu'avec une précision limitée. Ce sont des appareils discrets qui peuvent ne pas fonctionner avec tous les nombres possibles, mais seulement avec certains sous-ensembles dénombrables d'entre eux. Le format le plus courant pour travailler avec des nombres réels dans la mémoire de l'ordinateur est un point flottant (binaire) - flottant (binaire), lorsque les nombres sont stockés sous la forme M * 2 ^ E, où M et E sont des mantisses entières et l'ordre du nombre. Mais certains nombres, tels que 0,1, ne peuvent pas être représentés avec précision dans ce format. Par conséquent, au cours de calculs complexes, certaines erreurs s'accumulent inévitablement. Autrement dit, le résultat du calcul de la machine, par exemple 0,1 + 0,1 + 0,1, ne coïncide pas avec le 0,3 mathématiquement correct. Compte tenu de ce qui précède, lors de la programmation d'une arithmétique complexe, vous pouvez suivre plusieurs stratégies:

Stratégie 1 - ignorer. Ne faites pas attention à l'erreur, considérez toutes les opérations comme mathématiques idéales et espérez que la précision disponible est suffisante pour des résultats acceptables. L'option la plus courante.

Stratégie 2 - calculer méticuleusement. Les formules de calcul des erreurs machine sont connues depuis des décennies. Ils permettent d'estimer par dessus l'erreur relative de toute opération arithmétique. C'est probablement ce que vous devez faire pour une simulation numérique sérieuse. Le problème est que cela prend beaucoup de temps. En effet, chaque caractère + - * / du code doit être accompagné d'un calcul d'erreur. Vous devez prendre en compte toutes les dépendances entre les calculs et répéter la procédure à chaque fois que vous modifiez le code.

Stratégie 3 - utilisez un point décimal (point décimal flottant) au lieu du binaire. Autrement dit, stockez les nombres sous la forme M * 10 ^ E. Cela ne résout pas les problèmes d'erreur (la mantisse est toujours arrondie à un nombre fini de chiffres significatifs), mais au moins tous les nombres «simples» pour une personne (comme 1.1) sont maintenant représentés avec précision dans la mémoire. Le retour sur investissement sera la performance. Toute normalisation des nombres (c'est-à-dire une diminution équivalente de la mantisse et une augmentation de l'ordre) nécessite une division par une puissance de 10, ce qui n'est pas très rapide, contrairement à une division par une puissance de 2. Et vous devez normaliser beaucoup - à chaque addition ou soustraction avec des ordres différents.

Stratégie 4 - utilisez un point fixe (point décimal fixe). Simplification de la stratégie 3, lorsque nous fixons l'ordre E. Dans ce cas, la normalisation n'est pas nécessaire pour l'addition / soustraction. De plus, tous les calculs auront la même erreur absolue. Cet article est consacré à cette stratégie.

Arithmétique à virgule fixe

Contrairement à la physique, où l'erreur relative est importante, un absolu suffit en finance. Si, après une transaction financière complexe, le client est facturé 1 000 000,23 $ alors qu'il attend 1 000 000,18 $, des difficultés peuvent survenir. Des explications telles que "pourquoi avez-vous besoin d'une précision à 8 chiffres significatifs ??" ne peut pas rouler. Et il ne s'agit pas ici de 5 centimes de perte (à se tromper au contraire, «en faveur» du client n'est pas beaucoup mieux), mais des incohérences comptables. Par conséquent, les règles de calcul et d'arrondi sont clairement spécifiées entre les parties, et les artefacts liés à l'utilisation de variables doubles et flottantes compliquent parfois la vie.

Java a une classe standard pour l'arithmétique à virgule fixe - BigDecimal. Elle présente deux problèmes: elle est lente (en raison de son universalité) et elle n'est pas stable. La non-stabilité signifie que toute opération alloue un objet sur le tas. La sélection et la libération en termes d'un objet prennent un peu de temps, mais des calculs intensifs dans le code «chaud» créent une charge décente sur le GC, ce qui est inacceptable dans certains cas. Vous pouvez compter sur l'analyse d'échappement et la scalarisation, mais elles sont très instables dans le sens où même un léger changement dans le code ou dans le JIT (tel que le chargement paresseux d'une nouvelle implémentation d'interface) peut bouleverser la structure en ligne entière, et la méthode a bien fonctionné il y a une minute, commence soudainement à allouer furieusement la mémoire.
UPD en raison de questions dans les commentaires: La principale raison de l' abandon de BigDecimal et BigInteger n'est pas du tout les faibles performances de calcul, mais le manque de stabilité et de sélection des objets.

La bibliothèque décrite est le résultat d'être fatigué de réécrire à partir de zéro l'arithmétique non mémoire à virgule fixe pour chaque nouvel employeur, et j'ai décidé d'écrire ma propre bibliothèque pour une externalisation ultérieure.

Je vais immédiatement montrer un exemple d'utilisation avant de passer aux détails d'implémentation:

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})); } } 

Idée de mise en œuvre

Donc, nous avons besoin d'un wrapper mutable d'une primitive entière, plus précisément, d'un long'a, qui nous donnera près de 19 chiffres significatifs (assez pour l'entier et la partie fractionnaire). En long, nous entendons N décimales. Par exemple, avec N = 2, le nombre 2,56 est stocké sous la forme 256 (binaire 100000000). Les nombres négatifs sont stockés en standard, dans un code supplémentaire:

-2,56
-256

(Ci-après, l' italique indique les nombres et calculs «mathématiques», et en gras leur représentation interne)

Il m'a également semblé utile de saisir NaN en tant que valeur distincte, qui est renvoyée en cas d'erreurs arithmétiques (au lieu d'une exception ou d'ordures). NaN est représenté en interne par Long.MIN_VALUE , «propagé» à travers toutes les opérations et permet de déterminer l'inversion de signe pour tous les nombres restants.

Essayons d'estimer les algorithmes d'opérations arithmétiques pour le cas où N = 2.

L'addition et la soustraction ne nécessitent aucun geste supplémentaire, utilisez simplement les valeurs telles qu'elles sont:

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

La multiplication et la division nécessitent une normalisation supplémentaire, c'est-à-dire une multiplication / division par 10 ^ N (par 100 dans notre exemple)

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

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

La division supplémentaire n'est pas l'opération la plus rapide. Mais dans ce cas, il s'agit d'une division par une constante, car nous avons précédemment fixé N = 2 et 10 ^ N = 100. La division par constante, notamment par «belle» (type 10), est intensivement optimisée dans le CPU et beaucoup plus rapide que la division par un nombre aléatoire. Nous effectuons beaucoup de divisions par 10 chaque fois que nous convertissons un nombre en chaîne (par exemple, dans les journaux), et les fabricants de CPU le savent ( pour plus de détails sur l'optimisation, voir "Division par une constante").

Pour consolider la compréhension de ce que nous faisons, je donnerai une opération de plus: l'inversion unaire d'un nombre, c'est-à-dire 1 / x. Ceci est un cas particulier de division, il vous suffit de soumettre 1,00 dans notre format et n'oubliez pas de normaliser:

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

Eh bien, alors que tout est assez simple, essayons de plonger dans les détails.

Arrondi

Essayons de tirer un autre nombre:

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

Un résultat mathématique honnête se situe entre 0,33 et 0,34, mais nous ne pouvons pas l'imaginer exactement. Quelle façon d'arrondir? Généralement arrondi à 0, et c'est le moyen le plus rapide (matériel pris en charge). Mais, revenant à de vrais problèmes financiers, ce n'est pas toujours le cas. En règle générale, lors du traitement des transactions avec un client, l'arrondi est "en faveur du client". Autrement dit, le prix est arrondi vers le haut si le client vend, et vers le bas si le client achète. Mais d'autres options peuvent être nécessaires, par exemple, l'arrondissement arithmétique au nombre le plus proche avec des sous-types (mi-haut, mi-bas, mi-pair) pour minimiser les incohérences comptables. Ou arrondi à ± infini pour les prix négatifs (pour certains instruments financiers). Java BigDecimal contient déjà une liste de modes d'arrondi standard, et la bibliothèque décrite les prend en charge tous. UNNECESSARY renvoie NaN si l'opération nécessite de manière inattendue l'arrondi.

En mode arrondi, notre calcul devrait donner:

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

Comment savoir ce dont vous avez besoin pour ajouter une unité? Vous avez besoin du reste de la division 10 000% 300 = 100. Ce qui est aussi lent que la division elle-même. Heureusement, si vous écrivez dans une ligne dans le code "a / b; a% b", alors JIT se rendra compte que 2 divisions ne sont pas nécessaires, juste une commande div d'assembleur qui retourne 2 nombres (quotient et reste).

Les autres options d'arrondi sont un peu plus compliquées, mais peuvent également être calculées en fonction du reste et du diviseur.

Dans l'API, j'ai fait intentionnellement une mention d'arrondi partout où il se produit, soit en tant que paramètre, soit en tant que suffixe Round D dans les méthodes où il est défini par défaut sur zéro.

Débordement

Nous arrivons à la partie la plus difficile. Rappelons encore notre multiplication:

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

Imaginez maintenant que nous sommes dans les années 80 et que nous avons des processeurs 16 bits. Autrement dit, seul le short est à notre disposition avec une valeur maximale de 65535. La première multiplication débordera et sera égale à 240000 & 0xFFFF = 44392 (si elle n'est pas signée, avec un signe, elle sera également négative), ce qui cassera le résultat pour nous.

Ça ne marchera pas. Nous avons 2 arguments normaux (adaptés à notre plage de valeurs) et le même résultat normal attendu, mais nous débordons à mi-chemin. La même situation exacte est possible avec un long'om 64 bits, seuls les nombres ont besoin de plus.

Dans les années 80, nous aurions besoin d'une multiplication donnant un résultat 32 bits. Aujourd'hui, nous avons besoin d'une multiplication avec un résultat de 128 bits. Le plus ennuyeux est que les deux multiplications sont disponibles dans les assembleurs 8086 et x86-64, respectivement, mais nous ne pouvons pas les utiliser depuis Java! JNI, même dans le cas d'un hack avec JavaCritical rapide, donne un surcoût de dizaines de nanosecondes, introduit des difficultés de déploiement et de compatibilité, fige le GC pendant la durée de l'appel. De plus, il nous faudrait en quelque sorte renvoyer un résultat 128 bits à partir de la méthode native, et l'écriture par référence à un tableau (en mémoire) est un délai supplémentaire.

En général, je devais écrire la multiplication et la division manuelles. Colonne J'avais besoin de 2 opérations auxiliaires:

1. A (64) * B (64) = T (128); T (128) / N (32) = Q (64), R (32) - dans le cadre du point de multiplication fixe A * B
2. N (32) * A (64) = T (96); T (96) / B (64) = Q (64), R (64) - dans le cadre de la division des points fixes A / B
   (entre parenthèses indique la dimension des données en bits, T est une variable temporaire qui ne doit pas être débordée)

Les deux opérations renvoient le quotient et le reste (l'un résultant de la méthode, le second dans le champ objet). Ils peuvent également déborder, mais uniquement à la dernière étape, lorsque cela est inévitable. Voici un exemple (des années 1980):

500,00 / 0,50 = 1000,00
100 * 50 000/50 = 100 000 - débordement!

La division des colonnes à la Knut n'est pas l'algorithme le plus simple. De plus, il devrait également être relativement rapide. Par conséquent, le code des deux opérations est des centaines de lignes de magie un peu sévère, il me faudra beaucoup de temps pour me rappeler à nouveau ce qui se passe exactement là-bas. Je les ai amenés dans une classe séparée et j'ai commenté en détail autant que possible.

L'algorithme de multiplication n'est pas limité à l'appel de l'opération 1, mais le code restant n'est pas si compliqué et ajoute simplement la prise en charge des nombres négatifs, de l'arrondi et de NaN.

Habituellement (sauf cas particuliers), les deux opérations contiennent 4 multiplications et 2 divisions. L'opération 1 est nettement plus rapide que 2, car en elle ces divisions se font par une constante.

Soit dit en passant, si quelqu'un l'a remarqué, N (32) est notre 10 ^ N pour la normalisation. Il est de 32 bits, d'où il résulte que N peut être un maximum de 9. Dans les applications réelles que j'ai vues, 2, 4 ou 8 décimales ont été utilisées. Je n'en ai pas vu plus de 9, cela devrait donc suffire. Si vous faites 10 ^ N 64 bits, le code devient plus compliqué (et ralentit) encore plus.

Plusieurs précision différentes

Parfois, il est nécessaire d'effectuer une opération sur des arguments avec un nombre différent de décimales. Saisissez au minimum les opérations impliquant la durée habituelle.

Par exemple:

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

3,00 (N = 2) + 2 000 (N = 4) = 5,00 (N = 2)
300 + 20 000/100 = 500

Dans ce cas, une normalisation supplémentaire de l'un des arguments est requise. Notez que mathématiquement les deux opérations sont équivalentes, mais en raison de la précision différente du résultat, elles sont calculées différemment. Il convient également de noter que la deuxième opération nécessite généralement un arrondi.

Le nombre de décimales n'est PAS stocké dans l'objet. Au lieu de cela, une sous-classe distincte est supposée pour chaque précision. Les noms de classe peuvent être orientés métier, par exemple Prix (N = 8), Quantité (N = 2). Et ils peuvent être généralisés: Decimal1, Decimal2, Decimal3, ... Plus la précision est grande, plus la plage de valeurs stockées est petite, la plage minimale a Decimal9: ± 9223372036. On suppose qu'une ou deux classes suffiront pour couvrir les fonctionnalités nécessaires, auquel cas la méthode abstraite getScale sera très probablement dévirtualisée et intégrée. Les sous-classes (au lieu d'un champ supplémentaire) vous permettent de typifier strictement la précision des arguments et des résultats, ainsi que de signaler les arrondis possibles au stade de la compilation.

La bibliothèque permet des opérations avec un maximum de 2 (mais pas 3) de précision différente. Autrement dit, soit l'exactitude des deux arguments doit coïncider, soit l'exactitude de l'un des arguments et du résultat. Encore une fois, la prise en charge de 3 précisions différentes ralentirait considérablement le code et compliquerait l'API. Comme arguments, vous pouvez passer un long régulier, pour lequel une précision de N = 0 est supposée.

2.0000 / 3.0 = 0.6667 - ok (2 précision différente)
2/3 = 0,6667 - ok (arguments longs, résultat décimal)
2 / 3,0 = 0,6667 - impossible! (3 précision différente)

Avantages et inconvénients

De toute évidence, le calcul à haut bit effectué par la bibliothèque est plus lent que celui pris en charge par le matériel. Cependant, les frais généraux ne sont pas si importants (voir les repères ci-dessous).

De plus, en raison du manque de surcharge des opérateurs en Java, l'utilisation de méthodes au lieu d'opérateurs arithmétiques complique la perception du code.

Sur cette base, la bibliothèque est généralement utilisée dans des endroits où la perte de précision absolue est critique. Par exemple, calculer des statistiques financières précises, en tenant compte des indicateurs financiers actuels (positions de négociation, PnL, ordres exécutés). Dans l'échange réseau d'informations financières entre les systèmes, il est également plus pratique d'utiliser des formats avec un point décimal (au lieu de binaire).

Les algorithmes mathématiques complexes (modélisation, statistiques, prévisions) sont généralement plus faciles à réaliser de manière standard en double, car leur résultat n'est en tout cas pas absolument précis.

Code et repères

Code

En général, la multiplication est 4 fois plus rapide que BigDecimal, la division est de 1,5. Le taux de division dépend fortement des arguments, d'où la dispersion des valeurs.