Fast Fixed Point Math for Java Financial Applications

3r33625. 3r3-31. 3r3611. It is no secret that financial information (invoices, transactions, and other bookkeeping) is not very friendly with floating point numbers, and many articles recommend using a fixed point (fixed point arithmetic). In Java, this format is represented, in fact, only by the BigDecimal class, which cannot always be used for performance reasons. You have to look for alternatives. This article describes a self-written Java library for performing arithmetic operations on fixed-precision numbers. The library was created to work in high-performance financial applications and allows you to work with an accuracy of up to 9 decimal places while maintaining acceptable performance. The link to the source code and benchmarks is given at the end of the article 3r31414.

3r33410.

3r33625.

Floating point arithmetic

3r33625. 3r3611. Modern computers can perform arithmetic operations only with limited accuracy. These are discrete devices that can work not with all possible numbers, but only with some of their countable subsets. The most common format for working with real numbers in the computer's memory is a floating (binary) point - floating (binary) point, when numbers are stored as M * 2 ^ E, where M and E are the integer mantissa and the order of the numbers. But some numbers, such as 0.? cannot be accurately represented in this format. Therefore, in the course of complex calculations, some error inevitably accumulates. That is, the result of the machine calculation, say 0.1 + 0.1 + 0.? does not coincide with the mathematically correct 0.3. Given the above, when programming complex arithmetic, you can follow several strategies: 3r3-33614.

3r33625. 3r3611. Strategy 1 - ignore. Do not pay attention to the error, consider all operations ideally mathematical, and hope that the accuracy available will suffice for acceptable results. The most common option. 3r31414.

3r33625. 3r3611. Strategy 2 - scrupulously calculate. Formulas for calculating machine errors have been known for more than a decade. They allow us to estimate from above the relative error of any arithmetic operation. Probably, and it is necessary to do for serious numerical modeling. The problem is that it is very time consuming. In fact, each + - * /character in the code must be accompanied by an error calculation. It is necessary to take into account all the dependencies between the calculations and repeat the procedure every time the code changes. 3r31414.

3r33625. 3r3611. Strategy 3 - use a decimal point (floating decimal point) instead of a binary one. That is, store numbers in the form M * 10 ^ E. This does not solve the problems with the error (the mantissa is still rounded to a finite number of significant digits), but at least all the “simple” numbers for a person (like 1.1) are now accurately represented in the memory. Payback will be performance. Any normalization of numbers (that is, an equivalent reduction of the mantissa and an increase in order) requires division by degree 1? which is not very fast, unlike division by degree 2. And there is a lot to normalize - with each addition or subtraction with different orders. 3r31414.

3r33625. 3r3611. Strategy 4 - use a fixed point (fixed decimal point). Simplify strategy 3 when we fix order E. In this case, normalization is not needed for addition /subtraction. In addition, all calculations will have the same absolute error. This strategy is devoted to the article. 3r31414.

3r33625.

Fixed-point arithmetic

3r33625. 3r3611. Unlike physics, where the relative error is important, in finance, we need just absolute. If, after conducting a complex financial transaction, a customer is billed at $ ?00???? while he expects $ ?00?000.1? then some difficulties may arise. An explanation of the “yes, why do you need an accuracy of 8 significant digits ??” may not roll. And it's not a loss of 5 cents (to make a mistake on the contrary, “in favor” of the client is not much better), but in the inconsistencies of accounting. Therefore, the rules of computation and rounding are clearly stipulated between the parties, and artifacts from the use of double and float variables sometimes complicate life. 3r31414.

3r33625. 3r3611. In Java, there is a standard class for fixed point arithmetic - BigDecimal. There are two problems with it: it is slow (because of its universality) and it is not mutable. Non-confusion means that any operation allocates an object on the heap. The selection and release in terms of an object takes a little time, but intensive calculations in the hot code create a decent load on the GC, which is unacceptable in some cases. You can hope for escape analysis and scalarization, but they are very unstable in the sense that even a minor change in the code or in the JIT (such as lazy loading of a new interface implementation) can turn the entire inline structure upside down, and the method that worked normally a minute ago, suddenly begin to allocate memory madly. 3r31414.

3r33625. 3r3611. The described library is the result of the fact that I was tired of rewriting non-allocating memory of fixed point arithmetic from scratch for each new employer, and I decided to write my own library for subsequent insourcing. 3r31414.

3r33625. 3r3611. Immediately show an example of use, before moving on to the details of implementation:

3r33625.` public class Sample {`

3r3394.

private final Decimal margin; 3r33625. private final Quantity cumQuantity = new Quantity (); 3r33625. private final Quantity contraQuantity = new Quantity (); 3r33625. private final Quantity cumContraQuantity = new Quantity (); 3r33625. private final Price priceWithMargin = new Price (); 3r33625. private final Price avgPrice = new Price (); 3r33625. 3r33625. public Sample (int marginBp) {3r3363625. //1 + margin /10000

this.margin = Decimal.create (marginBp) .divRD (10000L) .add (1); 3r33625.} 3r33625. 3r33625. public Price calculateAvgPrice (Quantity[]quantities, Price[]prices) {

cumQuantity.set (0); 3r33625. contraQuantity.set (0); 3r33625. 3r33625. //avg = sum (q * p * margin) /sum (q) 3r3-3625. for (int i = 0; i < quantities.length; i++) {

cumQuantity.add (quantities[i]); 3r3-33625. priceWithMargin.set (prices[i]) .mulRD (margin); 3r3363625. contraQuantity.set (distribution[i]) .muli.ruli.ruli .muli.ruli.sett. ; 3r3-3625. CumContraQuantity.add (contraQuantity); 3r3-3625.} 3r36253. 3r363625. Return avgPrice.quotientRD (cumContraQuantity, cumQuantity); p1 = Price.create ("1.5");

Price p2 = Price.create (1.6);

Quantity q1 = Quantity.create ("100");

Quantity q2 = Quantity.create (200) ; 3r33625. 3r33625. //apply ???% margin to the prices 3r33625. Sample sample = new Sample (5); 3r3-3625. System.out.println (sample.calculateAvgPrice (new Quantity[]{Q? q2}, new[]. {p? p2})); 3r362525.} 3r 3-3625.}

3r33625.

The idea of implementing 3r3405.

3r33625. 3r3611. So, we need a mutable wrapper for an integer primitive, more precisely, a long’a, which will give us almost 19 significant digits (enough for the whole and for the fractional part). In long, we mean N decimal places. For example, when N = ? the number ??? is stored as 256 (binary 100000000). Negative numbers are stored in the standard, in the additional code:

3r33625. 3r3611. 3r3612. -???r31313.

3r33625. 3r33333. -256

3r31414.

3r33625. 3r3611. (Hereinafter, 3r3-3122. Italics 3r3-33613. Denotes “mathematical” numbers and calculations, and

Bold 3r-33354. Is their internal representation) 3r33614.

3r33625. 3r3611. It also seemed to me useful to enter NaN as a separate value, which is returned in case of arithmetic errors (instead of elimination or garbage). 3r3612. NaN 3r31313. presented inside as 3r33353. Long.MIN_VALUE

, “Propagates” through all operations and allows you to determine the sign inversion for all the remaining numbers. 3r31414.

3r33625. 3r3611. Let us try to estimate the algorithms of arithmetic operations for the case when N = 2. 3r31414.

3r33625. 3r3611. Addition and subtraction do not require any extra gestures, just use the values as is:

3r33625. 3r3611. 3r3612. ??? + ??? = ???r3r3613.

3r33625. 3r33333. 120 + 230 = 350

3r31414.

3r33625. 3r3611. Multiplication and division require additional normalization, that is, multiplication /division by 10 ^ N (by 100 in our example) 3r3614.

3r33625. 3r3611. 3r3612. ??? * ??? = ???r3r3613.

3r33625. 3r33333. 120 * 200/100 = 240

3r31414.

3r33625. 3r3611. 3r3612. ??? /??? = ???r3r3613.

3r33625. 3r33333. 100 * 120/200 = 60

3r31414.

3r33625. 3r3611. Additional division is not the fastest operation. But in this case, this division by a constant, because we fixed N = 2 and 10 ^ N = 100 in advance. The division by a constant, especially the “beautiful” (type 10), is intensively optimized in the CPU and much faster than the division by a random number. We do a lot of divisions by 10 each time we convert any number to a string (for example, in logs), and CPU manufacturers know this (3r3174. For more information about optimizing 3r310? see "Division by a constant"). 3r31414.

3r33625. 3r3611. To consolidate the understanding of what we are doing, I will give one more operation: a unary inversion of a number, that is, 1 /x. This is a special case of division, you just need to submit ??? in our format and do not forget to normalize: 3r3-3614.

3r33625. 3r3611. 3r3612. ??? /??? = ???r3r3613.

3r33625. 3r33333. 100 * 100/200 = 50

3r31414.

3r33625. 3r3611. Well, while everything is pretty simple, let's try to get into the details. 3r31414.

3r33625. 3r3197. Rounding 3r3405.

3r33625. 3r3611. Let's try to draw another number:

3r33625. 3r3611. 3r3612. ??? /??? = ???r3r3613.

3r33625. 3r33333. 100 * 100/300 = 33 r3r3354. 3r31414.

3r33625. 3r3611. An honest mathematical result lies between ??? and 0.3? but we cannot accurately represent it. Which way to round? Usually rounded to ? and this is the fastest way (supported by hardware). But, returning to the real financial problems, this is not always the case. Usually, when processing transactions with a client, rounding is “in favor of the client”. That is, the price is rounded up if the customer sells, and down if the customer buys. But other options may be required, for example, arithmetic rounding to the nearest number with subtypes (half-up, half-down, half-even) to minimize accounting inconsistencies. Or rounding to ± infinity for negative prices (for some financial instruments). Java BigDecimal already contains a list of standard rounding modes, and the described library supports them all. UNNECESSARY mode returns NaN if the operation unexpectedly requires rounding. 3r31414.

3r33625. 3r3611. In the round-up mode, our calculation should yield: 3r36144.

3r33625. 3r3611. 3r3612. ??? /??? = ???r3r3613.

3r33625. 3r33333. 100 * 100/300 + 1 = 34 3r33354. 3r31414.

3r33625. 3r3611. How do I know if I need to add one? We need the remainder of the division of 10000% 300 = 100. Which is as slow as the division itself. Fortunately, if you write in succession in the code "a /b; a% b", then JIT will figure out that 2 divisions are not necessary, just one assembler command div returning 2 numbers (quotient and remainder). 3r31414.

3r33625. 3r3611. Other rounding options are a bit more complicated, but they can also be calculated based on the remainder and the divisor. 3r31414.

3r33625. 3r3611. In the API, I intentionally made a rounding reference wherever it occurs, either as a parameter or as a suffix

R

ound

D

own in methods where it defaults to zero. 3r31414.

3r33625.

Overflow 3r3405.

3r33625. 3r3611. We come to the most difficult part. Recall once again our multiplication:

3r33625. 3r3611. 3r3612. ??? * ??? = ???r3r3613.

3r33625. 3r33333. 120 * 200/100 = 240

3r31414.

3r33625. 3r3611. Now imagine that we are in the 1980s and we have 16-bit processors. That is, only short is available to us with a maximum value of 65535. The first multiplication will overflow and will be equal to 240000 & 0xFFFF = 44392 (this is if without a sign, with a sign it will also be negative), which will break the result. 3r31414.

3r33625. 3r3611. This will not work. We have 2 normal (values that fit into our range) arguments, and the same normal expected result, but we are overflowing halfway. Exactly the same situation is possible with a 64-bit long, just numbers are needed more. 3r31414.

3r33625. 3r3611. In the 1980s, we would need multiplication, giving a 32-bit result. Today we need multiplication with a 128-bit result. The most annoying thing is that both multiplications are available in assemblers 8086 and x86-6? respectively, but we cannot use them from Java! JNI, even in the case of a hack with fast JavaCritical, gives the overhead in tens of nanoseconds, introduces problems with deployment and compatibility, freezes the GC for the duration of the call. In addition, we would somehow have to return a 128-bit result from the native method, and writing by reference to the array (in memory) is an additional delay. 3r31414.

3r33625. 3r3611. In general, I had to write manual multiplication and division. Column. I needed 2 auxiliary operations: 3r33614.

3r33625.

3r33625.

A (64) * B (64) = T (128); T (128) /N (32) = Q (64), R (32) - as part of the fixed point multiplication A * B

3r33625.

N (32) * A (64) = T (96); T (96) /B (64) = Q (64), R (64) - as part of the fixed point of the division A /B

3r33625. (the data in bits is shown in brackets, T is a temporary variable that should not be overflowed) 3r33291. 3r33625.

3r33625. 3r3611. Both operations return a private and a remainder (one - as the result of the method, the second - in the field of the object). They can overflow too, but only on the lastm step when it is inevitable. Here is an example (from the 1980s):

3r33625. 3r3611. 3r3612. ??? /??? = ???r3r3613.

3r33625. 3r33333. 100 * 5?000 /50 = 10?000

- overflow! 3r31414.

3r33625. 3r3611. Dividing the column a la Knut is not the easiest algorithm. Plus, it should all be relatively fast. Therefore, the code of both operations is hundreds of lines of fairly harsh bit magic, it will take a long time for me to remember again what exactly is happening there. I pulled them into a separate class and commented in detail as I could. 3r31414.

3r33625. 3r3611. The multiplication algorithm is not limited to calling operation ? but the remaining code is not so complicated and simply adds support for negative numbers, rounding, and NaN. 3r31414.

3r33625. 3r3611. Usually (with the exception of special cases), both operations contain 4 multiplications and 2 divisions. Operation 1 is significantly faster than ? since in it these divisions are by a constant. 3r31414.

3r33625. 3r3611. By the way, if anyone noticed, N (32) is our 10 ^ N for normalization. It is 32-bit, which means that N can be a maximum of 9. In the real applications I saw, ? ? or 8 decimal places were used. More than 9 I have not met, so that should be enough. If you make 10 ^ N 64-bit, the code becomes more complicated (and slows down) even more. 3r31414.

3r33625.

Several different accuracy 3r3405.

3r33625. 3r3611. Sometimes it is necessary to perform an operation on arguments with a different number of decimal places. At a minimum, enter transactions involving the usual long. 3r31414.

3r33625. 3r3611. For example: 3r31414.

3r33625. 3r3611. 3r3612. ??? (N = 4) + ??? (N = 2) = ??? (N = 4) 3r3363613.

3r33625. 3r33333. 2?000 + 300 * 100 = 50000

3r31414.

3r33625. 3r3611. 3r3612. ??? (N = 2) + ??? (N = 4) = ??? (N = 2) 3r3363613.

3r33625. 3r33333. 300 + 20000/100 = 500

3r31414.

3r33625. 3r3611. In this case, additional normalization of one of the arguments is required. Note that mathematically both operations are equivalent, but because of the other accuracy of the result, they are calculated differently. It is also worth noting that the second operation generally requires rounding. 3r31414.

3r33625. 3r3611. The number of decimal places is NOT stored in the object. Instead, a separate subclass is assumed for each accuracy. Class names can be business oriented, for example Price (N = 8), Quantity (N = 2). And they can be generalized: Decimal? Decimal? Decimal? The greater the accuracy, the smaller the range of stored values, the minimum range has Decimal9: ± 9223372036. It is assumed that one or two classes will be enough to cover the necessary functionality, and in this case, the abstract getScale method will most likely be virtualized and inline. Subclasses (instead of an additional field) allow you to strictly typify the accuracy of the arguments and the result, as well as to signal possible rounding at the compilation stage. 3r31414.

3r33625. 3r3611. The library allows for operations in which a maximum of 2 (but not 3) of different accuracy are involved. That is, either the accuracy of the two arguments must match, or the accuracy of one of the arguments and the result. Again, support for 3 different precisions would slow the code down and complicate the API. As arguments, you can pass the usual long, for which the accuracy is assumed to be N = 0. 3r31414.

3r33625. 3r3611. 3r3612. ??? /3.0 = ???r3r3613. - ok (2 different accuracy) 3r3609. 3r33625. 3r3612. 2/3 = ???r3r3613. - ok (long arguments, decimal result)

3r33625. 3r3612. 2 /3.0 = ???r3r3613. - impossible! (3 different accuracy) 3r31414.

3r33625.

Advantages and disadvantages of

3r33625. 3r3611. Obviously, the calculations of increased bitness carried out by the library are slower than the hardware supported. However, the overhead projector is not so large (see benchmarks below). 3r31414.

3r33625. 3r3611. In addition, due to the lack of operator overloading in Java, using methods instead of arithmetic operators complicates code perception. 3r31414.

3r33625. 3r3611. Based on this, the library is usually used in places where the loss of absolute accuracy is critical. For example, calculating accurate financial statistics, accounting for current financial indicators (trading positions, PnL, executing orders). In the case of a network exchange of financial information between systems, it is also more convenient to use formats with a decimal point (instead of binary). 3r31414.

3r33625. 3r3611. Complicated mathematical algorithms (modeling, statistics, forecasting) are usually simpler to perform as standard in double, since their result is not absolutely accurate in any case. 3r31414.

3r33625. 3r3404. Code and benchmarks

3r33625. 3r3611. 3r3409. Code

3r31414.

3r33625. 3r33414. 3r33625. 3r33584. 3r33625. 3r33333. Benchmark

3r33625. 3r33333. Mode

3r33625. 3r33333. Cnt

3r33625. 3r33333. Score

3r33625. 3r33333. Error

3r33625. 3r33333. Units

3r33625.

3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.control

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.multiplyNative

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.multiplyMyDecimal

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.multiplyBigDecimal

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.quotientNative

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.quotientMyDecimal

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r33584. 3r33625. 3r3601. DecimalBenchmark.quotientBigDecimal

3r33625. 3r3601. avgt

3r33625. 3r3601. 200

3r33625. 3r3601. ???r3604. 3r33625. 3r3601. ± ???r3r3604. 3r33625. 3r3601. ns /op 3r3609. 3r33625. 3r3604. 3r33625.

3r33625. 3r3608.

3r33625. 3r3611. In general, multiplication is 4 times faster than BigDecimal, division is 1.5. Division rate 3r33612. strongly

depends on the arguments, hence the spread of values. 3r31414.

3r33625. 3r33625. 3r3618. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e. ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3619. 3r33625.

3r33625. 3r33625. 3r33625. 3r33625.

It may be interesting

#### weber

Author**6-10-2018, 20:20**

Publication Date
#### Programming / Mathematics / High performance / JavaScript

Category- Comments: 0
- Views: 302

Pleasant data, significant and magnificent plan, as offer great stuff with smart thoughts and ideas, bunches of incredible data and motivation, the two of which I need, on account of offer such an accommodating data here.

Cheers!