Arbitrary-precision arithmetic in Erlang and Elixir
Even school students know that there are different number systems. As well, they are aware of the fact that not every finite decimal fraction equals to its finite binary representation. However, not many of us realize that due to this fact all operations with floats and doubles are never precise enough.
Let’s take Erlang, for instance. As many other languages, it implements IEEE754 standard for floats while standard Integer is implemented via arbitrary-precision arithmetic. However, it would be great to have not just bigint, but also an opportunity to handle rational and complex numbers and floats with precision required.
This article provides an overview of number coding theory of floats, and the most vivid examples of possible results. It also presents the solution which ensures the necessary precision of operations through a fixed-point implementation. This solution is framed as a library EAPA (Erlang Arbitrary Precision Arithmetic) whose main aim is to meet the needs of Erlang/Elixir financial apps.
Standards, standards, standards…
For the time being IEEE754 is the main standard for floating-point binary arithmetic. It is widely adopted in technology and programming and has four formats of representation:
- single-precision 32 bit
- double-precision 64 bit
- single-extended precision >=43 bit (rarely used)
- double-extended precision >= 79 bit (usually 80 bit)
Also, there are four rounding modes:
- rounding to the nearest integer
- rounding towards zero
- rounding towards +∞
- rounding towards -∞
Most of modern microprocessors are made with a hardware implementation of real number representation in IEEE754. The number length is limited by the format, and rounding modes influence precision. Programmers are often unable to change the behaviour of equipment, or languages implementation. For example, the official implementation of Erlang stores float in 3 words on a 64-bit machine and in 4 words on a 32-bit one.
As we have said before, IEEE754 numbers are an infinite set represented as finite. That’s why every operand can be misrepresented in IEEE754.
Most numbers when represented as a finite set have stable minimal relative error. For instance, it is 11,920928955078125e-6% for a float and 2,2204460492503130808472633361816e-14% for a double. Most programmers can afford to neglect such an error, though it should be mentioned that you can be caught in the same trap because the rate of an absolute error might be up to 10³¹ and 10²⁹² for a float and a double respectively. It can be troublesome for your computing.
Demonstration of effects
So, let’s get back to business and try to reproduce the effects in Erlang. All the examples below are processed as ct-tests.
Rounding and precision loss
First things first — how about adding 0,1+0,2 = ?:
t30000000000000004(_)-> ["0.30000000000000004"] = io_lib:format("~w", [0.1 + 0.2]).
The result of addition is a bit different from the one we’ve been expecting, and the test is run successfully. Let’s try to get the precise result now. To do so, we should re-write the test, using EAPA:
t30000000000000004_eapa(_)-> %% prec = 1 symbols after coma X = eapa_int:with_val(1, <<"0.1">>), Y = eapa_int:with_val(1, <<"0.2">>), <<"0.3">> = eapa_int:to_float(1, eapa_int:add(X, Y)).
This test is also successful and shows us that the problem has been solved. However, we keep on experimenting and add just a tiny value to 1.0:
tiny(_)-> X = 1.0, Y = 0.0000000000000000000000001, 1.0 = X + Y.
As we can see, our addition has been left unnoticed. Let’s try to fix it and, as well, show one of the library functions which is the autoscaling:
tiny_eapa(_)-> X1 = eapa_int:with_val(1, <<"1.0">>), X2 = eapa_int:with_val(25, <<"0.0000000000000000000000001">>), <<"1.0000000000000000000000001">> = eapa_int:to_float( eapa_int:add(X1, X2) ).
Word size overflow
Apart from the issues related to small numbers, one might overcome quite a significant problem of overflow.
float_overflow(_) -> 1.0 = 9007199254740991.0 - 9007199254740990.0, 1.0 = 9007199254740992.0 - 9007199254740991.0, 0.0 = 9007199254740993.0 - 9007199254740992.0, 2.0 = 9007199254740994.0 - 9007199254740993.0.
As can be seen from the test, at some point the difference stops being equal to 1.0. EAPA helps solve this problem too:
float_overflow_eapa(_)-> X11 = eapa_int:with_val(1, <<"9007199254740992.0">>), X21 = eapa_int:with_val(1, <<"9007199254740991.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X11, X21)), X12 = eapa_int:with_val(1, <<"9007199254740993.0">>), X22 = eapa_int:with_val(1, <<"9007199254740992.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X12, X22)), X13 = eapa_int:with_val(1, <<"9007199254740994.0">>), X23 = eapa_int:with_val(1, <<"9007199254740993.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X13, X23)).
The following text is an example of how dangerous reduction might appear. It means that computing precision is reduced dramatically when we deal with operations with resulting value much smaller than input ones. In our case the result of subtraction is 1. You can see that this problem exists in Erlang:
reduction(_)-> X = float(87654321098765432), Y = float(87654321098765431), 16.0 = X-Y. %% has to be 1.0
Somehow we’ve got 16.0 instead of anticipated 1.0. What can we do to improve it?
reduction_eapa(_)-> X = eapa_int:with_val(1, <<"87654321098765432">>), Y = eapa_int:with_val(1, <<"87654321098765431">>), <<"1.0">> = eapa_int:to_float(eapa_int:sub(X, Y)).
Some more unexpected features of floating-point arithmetic in Erlang/Elixir
Let’s start with ignoring the signed zero.
eq(_)-> true = list_to_float("0.0") =:= list_to_float("-0.0").
It should be mentioned that EAPA sticks to such behaviour:
eq_eapa(_)-> X = eapa_int:with_val(1, <<"0.0">>), Y = eapa_int:with_val(1, <<"-0.0">>), true = eapa_int:eq(X, Y).
as it is absolutely acceptable. As Erlang does not possess any clear syntax or handling NaN and infinities, it leads to a number of features like the following:
1> math:sqrt(list_to_float("-0.0")). 0.0
Next thing is particular processing of big and small numbers. Let’s repeat it for small numbers:
2> list_to_float("0."++lists:duplicate(322, $0)++"1"). 1.0e-323 3> list_to_float("0."++lists:duplicate(323, $0)++"1"). 0.0
and for big ones:
4> list_to_float("1"++lists:duplicate(308, $0)++".0"). 1.0e308 5> list_to_float("1"++lists:duplicate(309, $0)++".0"). ** exception error: bad argument
Some more examples for small numbers:
6> list_to_float("0."++lists:duplicate(322, $0)++"123456789"). 1.0e-323 7> list_to_float("0."++lists:duplicate(300, $0)++"123456789"). 1.23456789e-301
and last one:
8> 0.123456789e-100 * 0.123456789e-100. 1.524157875019052e-202 9> 0.123456789e-200 * 0.123456789e-200. 0.0
All the above-mentioned examples just confirm the truth for Erlang projects: money mustn’t be calculated in IEEE754.
EAPA is a NIF extension written on Rust. So far, in EAPA repository there is an
eapa_int interface. It is as simple as possible, as well as the most convenient. This interface is used for working with fixed-point numbers. Among its main features are:
- No effects of IEEE754 encoding
- Big numbers support
- Customized precision up to 126 decimal places (current realization)
- Support of all main numerical operations
- More or less complete testing, including property based one
- with_val/2 — conversion from a float into a fixed-point representation which can be safely used with json and xml.
- to_float/2 — conversion from a fixed-point number into a float with precision required.
- to_float/1 — conversion from a fixed-point number into a float.
- add/2 — sum of two numbers
- sub/2 — difference
- mul/2 — multiplication
- divp/2 — division
- min/2 — min number
- max/2 — max number
- eq/2 — equality
- lt/2 — less than
- lte/2 — less than or equals to
- gt/2 — greater than
- gte/2 — greater than or equals to
You might find EAPA code in the project repository
When is using eapa_int a good idea? For instance, if your app deals with money, or if you have to compute numbers like 92233720368547758079223372036854775807.92233720368547758079223372036854775807 precisely and with no trouble.
As almost every solution, EAPA is a bit of a compromise. We get the precision required at the expense of memory and speed. Performance tests and real systems statistics show that most of the operations are performed within 3–30 microseconds range. It should also be taken into account while choosing EAPA interface with a fixed point.
Obviously, we don’t always deal with this kind of problems in Erlang or Elixir. However, when one arises, but there isn’t a proper tool, you can do nothing but invent a solution. This article is just an attempt to share such a tool and a bit of personal experience with the community. I hope that this library might be of use for some of you and will help save your time.
Well…how do you count money in Erlang? P.S. The following articles will be devoted to working with rational and complex numbers. They will also cover the topic of native access to Integer, Float, Complex, and Rational types of arbitrary precision. Stay tuned!