proposal: math/big: Decimal

[kostya-sh]

Motivation

In many areas, especially in commerce, exact values need to be processed and the inputs are commonly decimal. Unfortunately, decimal values cannot be represented accurately using binary floating points.

Since Go can be used in many places where accurate decimal arithmetic is required it seems reasonable to support it as part of the standard library.

Proposal

The idea is to add math/big Decimal data type that supports integer, fixed-point, and floating-point decimal numbers.

The Decimal API is consistent with Float API when possible.

Internal representation

A Decimal consists of a boolean sign, an arbitrary precision integer unscaled value and a 32-bit integer scale. The value of the number represented by the Decimal is therefore sign × unscaledValue × 10^(-scale).

A Decimal (similar to Float) may also be zero (+0, -0) or infinite (+Inf, -Inf). NaN values are not supported.

Each Decimal value also has a precision, rounding mode, and accuracy. The precision is the maximum number of decimal digits available to represent the value. The rounding mode specifies how a result should be rounded to fit into the unscaled value, and accuracy describes the rounding error with respect to the exact result.

The same numerical value can have different representations (with different scales). The rules of arithmetic and rounding specify both the numerical result and the scale used in the result's representation.

Operations

The Decimal type provides operations for

• arithmetic: Add, Sub, Mul, Div, Quo, Rem, QuoRem, Abs
• scale manipulation: Scale, SetScale
• control over rounding behaviour: Mode, SetMode,
• control over precision and accuracy: Prec, SetPrec, Acc
• comparison: Cmp, TotalCmp (http://speleotrove.com/decimal/decifaq4.html#order)
• format conversion: to/from int64, uint64, float32, float64, big.Float, big.Int, big.Rat
• to/from string conversion

Implementation of the above operations closely follows the General Decimal Arithmetic Specification. This specification defines a decimal arithmetic which meets the requirements of commercial, financial, and human-oriented applications. It also matches the decimal arithmetic in the IEEE 754 Standard for Floating Point Arithmetic.

Test cases can be based on General Decimal Arithmetic
Testcases.

IEEE 754 fixed-point types

By setting the desired precision to 7, 16 or 34 and using matching rounding mode (typically ToNearestEven), Decimal operations produce the same results as the corresponding decimal32, decimal64 or decimal128 IEEE-754 arithmetic for operands that correspond to normal (i.e., not denormal) decimal32, decimal64 or decimal128 numbers.

Q&A

1. Why floating point?
   See https://www.python.org/dev/peps/pep-0327/#why-floating-point
2. Why are trailing fractional zeros important?
   See http://speleotrove.com/decimal/decifaq1.html#tzeros and http://speleotrove.com/decimal/decifaq4.html#unnari
3. How much precision and range is needed for decimal arithmetic?
   See http://speleotrove.com/decimal/decifaq1.html#needed
   In particular there is one example where decimal128 doesn't provide enough precision
4. Why arbitrary precision?
   See p3.
   Other use-cases: big.Float to string conversion, representing arbitrary precision numbers that are supported in other systems such as databases (for example PostgreSQL decimal can store up to 131072 digits before the decimal point and up to 16383 digits after the decimal point)

Existing packages

• Python: PEP-0327, decimal
• Java: JSR 13, BigDecimal
• ECMA Script proposal: http://wiki.ecmascript.org/doku.php?id=proposals:decimal

[cznic]

See also: http://godoc.org/github.com/shopspring/decimal

[rin01]

I also miss a decimal floating point data type.

The reasons why decimal floating numbers are important can be found here:
http://speleotrove.com/decimal/decifaq.html

In my projects, I use the C library decNumber, written by Mike Cowlishaw.
http://speleotrove.com/decimal/

The decNumber package, an implementation of the specifications in ANSI C, provides a reference implementation for both the arithmetic and the encodings.
It includes both an arbitrary-precision implementation and a (much faster) decFloats implementation that uses the IEEE 754 decimal encodings directly to implement decSingle, decDouble, and decQuad datatypes.

To download the source files, go to "International Components for Unicode (ICU)" and click "decNumber package".

The decQuad type is 128 bits long, and stores a decimal floating point number.
decDouble type is 64 bits long, and decSingle type is 32 bits long.

Personnally, I just put the .c and .h files in my project tree, and call the library functions using cgo.
I just use the decQuad type, which has the largest precision and stores numbers in 128 bits.
By experience, I really think it is an excellent library.

Example of use:
http://speleotrove.com/decimal/dnusers.html#example7

It would be great if a Go package wrapping this C library could be integrated in Go standard library, before being replaced by a pure Go solution with the same API.
In this case, it should perhaps be called "decnumber".

Note that this library is already integrated in gcc compiler.
But the type name have changed, e.g. decQuad became __Decimal128 in gcc.
https://gcc.gnu.org/onlinedocs/gcc/Decimal-Float.html

As an extension, GNU C supports decimal floating types as defined in the N1312 draft of ISO/IEC WDTR24732.
Support for decimal floating types in GCC will evolve as the draft technical report changes.
Calling conventions for any target might also change. Not all targets support decimal floating types.

The decimal floating types are _Decimal32, _Decimal64, and _Decimal128.

[griesemer]

math/big is all about arbitrary precision arithmetic, and in the case of Float, the precision can be set arbitrarily (within memory limits, essentially).

I'd be ok with a big.Decimal type; as long as it's also arbitrary precision. Fixed-size data types such as decQuad, decDouble belong into a separate package in my mind.

In fact, the Float implementation already uses some (minimal) decimal arithmetic for Float->string conversion; having an actual Decimal type would make that code unnecessary (in favor of using a fully-fledged Decimal implementation).

That said, I would like to see more "meat" around this proposal. With the Float implementation, the fixed-width IEEE floating-point spec provided reasonable guidance. What are the parameters for a Decimal implementation? Is it at Fixed-point implementation (arbitrary size number with fixed decimal point), or decimal floating-point representation (like Float, with mantissa and exponent, but the mantissa is always decimal)? Are the other options? What are the pros and cons? What are other packages doing? What is required for say business/banking applications?

[ianlancetaylor]

Just a note: any fixed-size Decimal implementation should consider the IEEE 754-2008 specs for decimal floating point, and the corresponding C extensions for decimal floating point (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1312.pdf).

[rin01]

@kostya-sh: do you really need arbitrary precision for financial computation ?
In my mind, they are best done by using base 10 floating point fixed-size data types, like a decimal128 (or decQuad).

I say that because I think the API of big.Float (and big,Decimal will certainly be the same) is quite complex.

As an example, for addition:

func (z *Float) Add(x, y *Float) *Float
Add sets z to the rounded sum x+y and returns z. If z's precision is 0, it is changed to the larger of x's or y's precision before the operation. Rounding is performed according to z's precision and rounding mode; and z's accuracy reports the result error relative to the exact (not rounded) result.

You must prepare the result variable with proper precision and rounding mode, and think about it for each arithmetic operation.

With a fixed-size floating point API, and decimal128 data type, all you do would be:

c = context.Add(a, b)

where context contains the rounding mode, and stores computation error of it occurs.
Also, numbers are just values, not pointers.
It would be as simple as working with float64.

The API of big.Float introduces a complexity that is not needed for most financial computation.
We just want that Add, Subtract and Mult don't round the result for numbers in usual range, but store them with the max precision allowed by the fixed-size data type. e.g. 34 significant digits for decimal128.
And if we want to round or truncate the result, we can just call the proper function.

Usual range for monetary values

Assets under management for a large multinational insurance company is:

$265,507,000,000

This figure is the sum of amounts that can have 8 digits after decimal point, because this precision is needed when working with foreign currency conversion.

This means that for a large company, a decimal data type must cope with figures like:

100,000,000,000.00000000, that is, 20 significant digits.

A decimal128 fixed-size data type provides 34 significant digits, which can easily store these figures.
We can even store USA national debt of $18,000,000,000,000 in it with full precision.

When doing financial computation, intermediate calculation can require some more digits, but 34 significant digits is really enough for most real cases financial computation.

That's why I think that big.Decimal for most financial applications is overkill, and a fixed-size decimal128 base-10 floating type is more than "good enough".

PRO and CONS

big.Decimal arbitrary-precision

CON: if like big.Float, the API is more complex than needed
CON: variables are pointers
CON: precision and rounding mode of the result must be think about for each operation
CON: is there a lot of financial applications that requires a precision of more than 34 significant digits ?
PRO: no limit to the precision

decnumber.Decimal128 fixed-size

PRO: API is simple
PRO: variable are values
PRO: no need to think about precision, as the result is always the max precision of decimal128
PRO: decimal128 can store 34 significant digits, which can accomodate the range of values used in most financial applications
PRO: no need to allocate memory to store the result, all numbers fits in 128 bits. (use of sync.Pool and small internal buffer can alleviate this problem, though)

Decimal floating point package used by other languages:

Let a and b be operands, and z is the result.
context contains the rounding mode, and computation error if any.
If an operation fails, context will keep the error and subsequent operations are no-op. There is no need to check for error after each operation, only after the last one.

C: gcc contains "decNumber" implementation of Mike Cowlishaw, fixed-size floating point (it is an extension of GNU C)
decQuad type is 128 bits.
The numbers are pointers.

decQuadAdd(&z, &a, &b, &context);

java.math.BigDecimal is arbitrary-precision, consisting of an arbitrary precision integer (like Go big.Int) and a scale.
The numbers are immutable values, not pointers.

BigDecimal z = a.add(b, context);

Python "decimal" module is also arbitrary-precision, with an API that ressembles very much to the C "decNumber" API, because the IBM decimal implementation by Mike Cowlishaw was chosen
as basis for the Python's decimal implementation.
The numbers are immutable values, not pointers.

z = context.add(a, b)

Microsoft C# "decimal"
The binary representation of a Decimal value consists of a 1-bit sign, a 96-bit integer number, and a scaling factor.
It is a fixed-size 128 bits binary format, like C "decNumber", but the API is very different.
The numbers are immutable values, not pointers.
No context, we work with "decimal" data type like with base-2 "Double" data type.

z = a + b

That being said, any means of working with base-10 floating point numbers, be it arbitrary-precision or fixed-size, will be welcomed by all those that work with monetary values ;-)

[kostya-sh]

@rin01, I agree that for the most (if not all) financial computations decimal128 is enough. This is approach is used by .NET. System.Decimal is decimal128 though I am not sure how closely it follows IEEE 754-2008.

However I think that arbitrary precision big.Decimal type is a better fit for the inclusion in the Go standard library as it supports more use cases than decimal128. For example:

• Non-financial use-cases. E.g. big.Float to string conversion.
• Representing arbitrary precision numbers that are supported in other systems such as SQL databases. For example PostgreSQL decimal can store up to 131072 digits before the decimal point and up to 16383 digits after the decimal point.

big.Decimal API should probably be very similar to big.Float API for consistency. This means that big.Decimal will be mutable and its methods will be defined using pointers. To address some of your concerns:

• Mutable vs immutable. I believe this is a matter of user preference. Some users find surprising that calling a.add(b, context) in Java doesn't modify a. From the performance point of view mutable values leave more space for optimization, at least as far as memory usage is concerned.
• Values vs Pointers. It would be good to be able to work with large number of decimals without any GC overhead. While it won't be possible to avoid it in all cases (because of arbitrary precision) I believe that for the most common usecase when precision is small GC can be avoided completely by using uint64 instead of big.Int as big.Decimal internal representation. Go compiler should take care of allocating big.Decimal instances on the stack when possible using escape analysis.

[kostya-sh]

The following proposal documents can be used to understand what other packages are doing:

• JSR 13 for Java. Interestingly the original author seems to be Mike Cowlishaw.
• PEP 0327 for Python

Reference documentation: Java BigDecimal, Python decimal

Both Java and Python implementations are based on a decimal arithmetic model, as defined by the relevant standards: IEEE 854 , ANSI X3-274 and the proposed revision of IEEE 754.

While Java and Python implementations are slightly different they have the following commonalities:

• Both exact unrounded decimal arithmetic (sometimes called fixed-point arithmetic) and rounded floating-point arithmetic are supported
• A decimal number has a sign, coefficient digits, and an exponent.
• A notion of significant places so that 1.30 + 1.20 is 2.50 is supported. The trailing zero is kept to indicate significance.
• A concept of context for arithmetic operations specifying precision and rounding rules

Python decimal is more complete implementation comparing to Java BigDecimal:

• Infinities and NaNs are supported
• Error behaviour is configurable via context (hardcoded in Java)
• more numeric operations are implemented

[rin01]

In Go, numeric data types have both a built-in fixed-size implementation, and a package for arbitrary-precision.

Ultimately, Go should perhaps have both kinds.
A default fixed-size decimal128 implementation for usual cases, and a big.Decimal for more specialized cases.

base	built-in fixed-size	arbitrary-precision package
2	int	big.Int
2	float64	big.Float
10	decimal128	big.Decimal

[rin01]

If anyone wants to play with a fixed-size decimal package, I have written this Go wrapper around the decNumber package of Mike Cowllishaw, but just the "decQuad" data type.
The package is well tested.

decnum.Quad is a 128 bits fixed-size base-10 floating point

https://github.com/rin01/decnum
https://godoc.org/github.com/rin01/decnum

[kostya-sh]

@rin01, your decnum package looks very interesting. In fact I think that a package that supports both fixed size types (decimal.Single, decimal.Double, decimal.Quad) and an arbitrary precision type (decimal.Number) for decimal numbers that is modeled after decnumber library could be a very good addition to golang.org/x packages. Such package will probably will have to be implemented in pure Go. I don't think that it fits math/big package though as the APIs are quite different. Maybe you can create another proposal?

If possible I would like to keep this proposal limited to the new math/big Decimal type with a set of methods similar to Float type. The purpose of big.Decimal is to provide a standard and consistent API to work with arbitrary precision decimal numbers in Go that will work for 99% of users. And users requiring more control or better performance or different API could look at other packages similar to your decnum proposal.

I will update the proposal with more details as requested by @griesemer soon.

[kostya-sh]

I have updated the issue to include more details about the proposed implementation.

[rin01]

@kostya-sh: I agree with you. This proposal should be limited to math/big Decimal type with similar API to Float type. This would be great and will make the arbitrary-precision package math/big complete in a consistent manner.

Fixed-size base-10 floating point like decimal128 is another topic and should belong to another package and issue.
Just for info, I am working on my decnum package to make it fully tested, debugged and usable for next week.
This way, even if a pure Go implementation of decimal128 (aka decnum.Quad) is desirable, it won't be an urgent topic any more.

[mpvl]

As an FYI, some of the issues that are aimed to be solved by this proposal, like rounding modes and precision (trailing zeros), I plan to address in the number formatting package in the text repo. In this model, aspects like rounding and precision are considered a property of the visualization, not the underlying number. This allows precision in computation to be higher than that of visualization. The number rendering would also support the big variants.

This is not to say that an addition of big.Dec (naming to be consistent) wouldn't be useful; I think it would be, even though it could be easily simulated with big.Int. Mostly, it would define a standard for decimal numbers so that it can be supported out of the box in other repos (like text). Note that many major frameworks, including .Net, OS X Foundation, Java etc. all have this functionality in their core library, which indicates it probably belongs there.

One could try to make the rounding definitions more general than just math/big. One could define a math/round package (as in .Net) or, IMO better, define the rounding modes and behaviors in math and add a func Round(float64, Rounding) (res float64, exact bool) to complement Floor and Trunc. In math/big, the various operations would use these rounding types. The method Dec(round math.Rounding) (d *Dec, exact bool) could then be defined on Rat to convert it to Dec. There is no efficient easy way to do that now that I can think of.

Note that these rounding parameters don't cover the whole spectrum of rounding algorithms. For currencies and in finance one sometimes does not round to a power of 10. I think it will be sufficient to simulate it, though. For example, rounding for Swiss accounting could be achieved by rounding HalfEven and then completing the rounding "manually" to select 0 or 5 for the last digit.