An arbitrary-precision decimal floating-point arithmetic package for Go

Overview

decimal

godocb travisb coverb goreportb

Package decimal implements arbitrary-precision decimal floating-point arithmetic for Go.

Rationale

How computers represent numbers internally is of no import for most applications. However numerical applications that interract with humans must use the same number base as humans. A very simple example is this: https://play.golang.org/p/CVjiDCdhyoR where 1.1 + 0.11 = 1.2100000000000002. Not quite what one would expect.

There are other arbitrary-precision decimal floating-point libraries available, but most use a binray representation of the mantissa (building on top of big.Int), use external C libraries or are just plain slow.

This started out as an experiment on how an implementation using a pure decimal representation would fare performance-wise. Secondary goals were to implement it with an API that would match the Go standard library's math/big API (for better or worse), and build it in such a way that it could some day be integrated into the Go standard library.

Admittedly, this actually started out while doing some yak shaving, combined with an NIH syndrom, but the result was well worth it.

Features

The implementation is in essence a port of big.Float to decimal floating-point, and the API is identical to that of *big.Float with the exception of a few additional getters and setters, an FMA operation, and helper functions to support implementation of missing low-level Decimal functionality outside this package.

Unlike big.Float, the mantissa of a Decimal is stored in a little-endian Word slice as "declets" of 9 or 19 decimal digits per 32 or 64 bits Word. All arithmetic operations are performed directly in base 10**9 or 10**19 without conversion to/from binary (see Performance below for a more in-depth discussion of this choice).

While basic operations are slower than with a binary representation, some operations like rounding (happening after every other operation!), or aligning mantissae (in add/subtract) are much cheaper.

Decimal and IEEE-754

The decimal package supports IEEE-754 rounding modes, signed zeros, infinity, and an exactly rounded Sqrt. Other functions like Log will be implemented in a future "math" sub-package. All results are rounded to the desired precision (no manual rounding).

NaN values are not directly supported (like in big.Float). They can be seen as "signaling NaNs" in IEEE-754 terminology, that is when a NaN is generated as a result of an operation, it causes a panic. Applications that need to handle NaNs gracefully can use Go's built-in panic/recover machanism to handle these efficiently: NaNs cause a panic with an ErrNaN which can be tested to distinguish NaNs from other causes of panic.

On the other hand, the context sub-package provides Contexts, which allow panic-free operation and a form of quiet-NaNs whereby any NaN generated by an operation will make the context enter into an error state. Further operations with the context will be no-ops until (*Context).Err is called to check for errors.

Mantissae are always normalized, as a result, Decimals have a single possible representation:

0.1 <= mantissa < 1; d = mantissa × 10**exponent

so there is no notion of scale and no Quantize operation.

TODO's and upcoming features

  • Some math primitives are implemented in assembler. Right now only the amd64 version is implemented, so we're still missing i386, arm, mips, power, riscV, and s390. The amd64 version could also use a good review (my assembly days date back to the Motorola MC68000). HELP WANTED!
  • Complete decimal conversion tests
  • A math sub-package that will provide at least the functions required by IEEE-754
  • Some performance improvement ideas:
    • try a non-normalized mantissa.
    • in add, there are some cycles to shave off by combining the shift and add for simple cases (initial testing yielded mitigated results. Wait and see)

The decimal API is frozen, that is, any additional features will be added in sub-packages.

Well, with the exception of NewDecimal: The current integer mantissa × 10**exp, works well enough, but I'm not truly happy with it. Early versions were using a float64 value as initializer, but that lead to unexpected side effects where one would expect the number to be exact; not quite so as it turned out, so it's not an option either.

Performance

There are other full-featured arbitrary-precision decimal-floating point libraries for Go out there, like Eric Lagergren's decimal, CockroachDB's apd, or Shopspring's decimal.

For users only interested in performance here are the benchmark results of this package versus the others using Eric's Pi test (times are in ns/op sorted from fastest to slowest at 38 digits of precision):

digits 9 19 38 100 500 5000
Eric's decimal (Go) 6415 30254 65171 194263 1731528 89841923
decimal 12887 42720 100878 348865 4212811 342349031
Eric's decimal (GDA) 7124 39357 107720 392453 5421146 1175936547
Shopspring's decimal 39528 96261 204017 561321 3402562 97370022
apd 70833 301098 1262021 9859180 716558666 ???

Note that Eric's decimal uses a separate logic for decimals < 1e19 (mantissa stored in a single uint64), which explains its impressive perfomance for low precisions.

In additions and subtractions the operands' mantissae need to be aligned (shifted), this results in an additional multiplication by 10**shift. In implementations that use a binary representation of the matissa, this is faster for shifts < 19, but performance degrades as shifts get higher. With a decimal representation, this requires a multiplication as well but always by a single Word, regardless of precision.

Rounding happens after every operation in decimal and Eric's decimal in GDA mode (not in Go mode, which explains its speed). Rounding requires a decimal shift right, which translates to a division by 10**shift. Again for small shifts, binary representations are faster, but degrades even faster as precision gets higher. On decimal implementations, this operation is quite fast since it translates to a memcpy and a divmod of the least significant Word.

This explains why decimal's performace degrades slower than Eric's decimal-GDA as precision increases, and why Eric's decimal in Go mode is so fast (no rounding, which surprisingly counter-balances the high cost of mantissae alignment).

Caveats

The Float <-> Decimal conversion code needs some love.

The math/big API is designed to keep memory allocations to a minimum, but some people find it cumbersome. Indeed it requires some practice to get used to it, so here's a quick rundown of what to do and not do:

Most APIs look like:

func (z *Decimal) Add(x, y *Decimal) *Decimal

where the function sets the receiver z to the result of a + b and returns 'z'. The fact that the function returns the receiver is meant to allow chaining of operations:

s := new(Decimal).Mul(new(Decimal).Mul(r, r), pi) // d = r**2 * pi

If we don't care about what happens to r, we can just:

s := new(Decimal).Mul(r.Mul(r, r), pi)            // r *= r; d = r * pi

and save one memory allocation.

However, NEVER assign the result to a variable:

d := new(Decimal).SetUint(4)
d2 := d.Mul(d, d) // d2 == 16, but d == 16 as well!

Again, the sole intent behind returning the receiver is chaining of operations. By assigning it to a variable, you will shoot yourself in the foot and kill puppies in some far away land, so never assign the result of an operation!

However, feel free do do this:

d.Mul(d, d) // d = d*d

The code will properly detect that the receiver is also one of the arguments (possibly both), and allocate temporary storage space if (and only if) necessary. Should this kind of construct fail, please file an issue.

License

Simplified BSD license. See the LICENSE file.

The decimal package reuses a lot of code from the Go standard library, governed by a 3-Clause BSD license. See the LICENSE-go file.

I'm aware that software using this package might have to include both licenses, which might be a hassle; tracking licenses from dependencies is hard enough as it is. I'd love to have a single license and hand over copyright to "The Go authors", but the clause restricting use of the names of contributors for endorsement of a derived work in the 3-Clause BSD license that Go uses is problematic. i.e. I can't just use it as-is, mentioning Google Inc., as that would be an infringement in itself (well, that's the way I see it, but IANAL). On the other hand, any piece of software written in Go should include the Go license anyway...

Any helpful insights are welcome.

You might also like...
Arbitrary-precision decimals for Go

apd apd is an arbitrary-precision decimal package for Go. apd implements much of the decimal specification from the General Decimal Arithmetic descrip

Converts a number to its English counterpart. Uses arbitrary precision; so a number of any size can be converted.

Converts a number to its English counterpart. Uses arbitrary precision; so a number of any size can be converted.

Bigint - Immutable arbitrary-precision integer for Go

bigint Go's big.Int is mutable to enable flexibility in performance tuning but s

An anonymous, encrypted Point-to-Point (Layer 3) tunnel between two peers.

NKN-Link An anonymous, encrypted Point-to-Point (Layer 3) tunnel between two peers. NKN-Link Table of Contents Preface Description Install Setup Run P

Wg-configurator - This project makes it easier to configure a fleet of servers interconnected via the WireGuard point-to-point virtual private network.

WireGuard Configurator This project makes it easier to configure a fleet of servers interconnected via the WireGuard point-to-point virtual private ne

A simple evaluator for arithmetic integer expressions.

The expr package provides a simple evaluator for arithmetic integer expressions. The syntax and operations are the same as in Go. Operands are the nat

high performance fixed decimal place math library for Go

Summary A fixed place numeric library designed for performance. All numbers have a fixed 7 decimal places, and the maximum permitted value is +- 99999

An Alfred Workflow for the Johnny.Decimal filing system
An Alfred Workflow for the Johnny.Decimal filing system

alfred-jd An Alfred Workflow for the Johnny.Decimal filing system This workflow provides tools for working with the brilliant Johnny.Decimal filing sy

Transfer decimal ipv4 to binary ipv4

transfer decimal ipv4 to binary ipv4. Download: git clone https://github.com/Bet

Assigns floating ip addresses to Rancher Guest clusters.
Assigns floating ip addresses to Rancher Guest clusters.

kube-fip-operator The kube-fip-operator application manages the FloatingIP and FloatingIPRange Custom Resource Definition objects in a Rancher environ

High-precision indoor positioning framework, version 3.

The Framework for Internal Navigation and Discovery (FIND) is like indoor GPS for your house or business, using only a simple smartphone or laptop. Th

a Go package to interact with arbitrary JSON

go-simplejson a Go package to interact with arbitrary JSON Importing import github.com/bitly/go-simplejson Documentation Visit the docs on Go package

A Go package to interact with arbitrary JSON

go-simplejson a Go package to interact with arbitrary JSON Importing import github.com/bitly/go-simplejson Documentation Visit the docs on Go package

yet another point in polygon package

piper Yet another point in polygon package. Piper makes use of ray casting and does account for holes in polygons. Installation go get -u github.com/i

:handbag: Cache arbitrary data with an expiration time.

cache Cache arbitrary data with an expiration time. Features 0 dependencies About 100 lines of code 100% test coverage Usage // New cache c := cache.N

smartcrop finds good image crops for arbitrary crop sizes
smartcrop finds good image crops for arbitrary crop sizes

smartcrop smartcrop finds good image crops for arbitrary sizes. It is a pure Go implementation, based on Jonas Wagner's smartcrop.js Image: https://ww

Arbitrary transformations of JSON in Golang

kazaam Description Kazaam was created with the goal of supporting easy and fast transformations of JSON data with Golang. This functionality provides

Arbitrary expression evaluation for golang

govaluate Provides support for evaluating arbitrary C-like artithmetic/string expressions. Why can't you just write these expressions in code? Sometim

Job worker service that provides an API to run arbitrary Linux processes.
Job worker service that provides an API to run arbitrary Linux processes.

Job Scheduler Summary Prototype job worker service that provides an API to run arbitrary Linux processes. Overview Library The library (Worker) is a r

Owner
Denis Bernard
Denis Bernard
Package goraph implements graph data structure and algorithms.

goraph Package goraph implements graph data structure and algorithms. go get -v gopkg.in/gyuho/goraph.v2; I have tutorials and visualizations of grap

Gyuho Lee 706 Dec 20, 2022
A well tested and comprehensive Golang statistics library package with no dependencies.

Stats - Golang Statistics Package A well tested and comprehensive Golang statistics library / package / module with no dependencies. If you have any s

Montana Flynn 2.6k Dec 26, 2022
An arbitrary-precision decimal floating-point arithmetic package for Go

decimal Package decimal implements arbitrary-precision decimal floating-point arithmetic for Go. Rationale How computers represent numbers internally

Denis Bernard 29 Sep 27, 2022
Arbitrary-precision fixed-point decimal numbers in go

decimal Arbitrary-precision fixed-point decimal numbers in go. Note: Decimal library can "only" represent numbers with a maximum of 2^31 digits after

Spring Engineering 4.7k Jan 9, 2023
Arbitrary-precision fixed-point decimal numbers in go

decimal Arbitrary-precision fixed-point decimal numbers in go. Note: Decimal library can "only" represent numbers with a maximum of 2^31 digits after

Spring Engineering 4.7k Jan 8, 2023
Arbitrary-precision fixed-point decimal numbers in go

decimal Arbitrary-precision fixed-point decimal numbers in go. Note: Decimal library can "only" represent numbers with a maximum of 2^31 digits after

null 0 Jan 10, 2022
Implements a simple floating point arithmetic expression evaluator in Go (golang).

evaler https://github.com/soniah/evaler Package evaler implements a simple floating point arithmetic expression evaluator. Evaler uses Dijkstra's Shun

Sonia Hamilton 50 Sep 27, 2022
Implements a simple floating point arithmetic expression evaluator in Go (golang).

evaler https://github.com/soniah/evaler Package evaler implements a simple floating point arithmetic expression evaluator. Evaler uses Dijkstra's Shun

Sonia Hamilton 50 Sep 27, 2022
Utilities for rounding and truncating floating point numbers.

Rounders Provides utilities for rounding and truncating floating point numbers. Example: rounders.RoundToDecimals(12.48881, 2)

Konnor Klashinsky 0 Jan 6, 2022
It's a basic newtonian gravity simulation written in Go using floating point numbers with 1024 bits of accuracy

Float 1K Gravity What is it? It's a basic newtonian gravity simulation written in Go using floating point numbers with 1024 bits of accuracy. It is cu

Nathan Hedge 1 Dec 13, 2022