Git Product home page Git Product logo

decimal's Introduction

decimal

This library implements fixed-precision decimal numbers based on IEEE 754R standard; https://ieeexplore.ieee.org/document/4674342 More info can be found at: http://speleotrove.com/decimal/

Features

  • Decimal64, partial implementation of the ieee-754R standard
  • Half up and half even rounding
  • Up to 3 times faster than arbitrary precision decimal libraries in Go

Goals

  • To implement 128 bit decimal

Installation and use

Run go get github.com/anz-bank/decimal

package main

import (
	"fmt"

	"github.com/anz-bank/decimal"
)

func main() {
	var a decimal.Decimal64
	b := decimal.MustParse64("0.1")
	c := decimal.MustParse64("0.3")
	d := decimal.New64FromInt64(123456)

	fmt.Println(a, b, c, d)
}

Docs

https://godoc.org/github.com/anz-bank/decimal

Why decimal

Binary floating point numbers are fundamentally flawed when it comes to representing exact numbers in a decimal world. Just like 1/3 can't be represented in base 10 (it evaluates to 0.3333333333 repeating), 1/10 can't be represented in binary. The solution is to use a decimal floating point number. Binary floating point numbers (often just called floating point numbers) are usually in the form Sign * Significand * 2 ^ exp and decimal floating point numbers change this to Sign * Significand * 10 ^ exp This eliminates the decimal fraction problem, as the base is in 10.

Why fixed precision

Most implementations of a decimal floating point datatype implement an 'arbitrary precision' type, which often uses an underlying big int. This gives flexibility in that as the number grows, the number of bits assigned to the number grows ( and thus 'arbitrary precision'). This library is different as it specifies a 64 bit decimal datatype as specified in the ieee-754R standard. This gives the sacrifice of being able to represent arbitrarily large numbers, but is faster than other arbitrary precision libraries.

decimal's People

Contributors

anzdaddy avatar joshcarp avatar juliaogris avatar marcelocantos avatar michaeldao avatar shanehowearth avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar

decimal's Issues

Avoid dynamic memory allocation where practical

For example, (Decimal64).Format allocates a buffer to pass to (Decimal64).Append but ends up passing it to (fmt.State).Write, which might be simply copying the buffer into another already allocated buffer.

The solution might be to reverse the roles. Format implements the algorithm and Append calls it like so:

type appender struct {
	buf []byte
	prec int
}

func (a *appender) Write(b []byte) (n int, err error) {
	a.buf = append(a.buf, b...)
	return n, nil
}

func (a *appender) Width() (wid int, ok bool) {
	return 0, false
}

func (a *appender) Precision() (prec int, ok bool) {
	return a.prec, true
}

func (a *appender) Flag(c int) bool {
	return false
}

// Append appends the text representation of d to buf.
func (d Decimal64) Append(buf []byte, format byte, prec int) []byte {
	a := appender{buf, prec}
	d.Format(&a, rune(format))
	return a.buf
}

// Format implements fmt.Formatter.
func (d Decimal64) Format(s fmt.State, format rune) {
	// Declare big enough local array to avoid dynamic allocation.
	var data [25]byte

	// Use the same algo as Append currently does
	buf := data[:]
	prec, havePrec := s.Precision()
	⋮
	if _, err := s.Write(buf); err != nil {
		panic(err)
	}
}

To reiterate, the above is just one case. There might be others. Also, it's possible the above solution yields worse performance, so don't assume, profile.

Exponent overflow in decimal64

Exponent overflows when adding very large numbers. eg 9e384 + 1e384.
Should add to inf

        x := MustParseDecimal64("9e384")
	y := MustParseDecimal64("1e384")
	z := x.Add(y)

z evaluates to .007199254740992e-383 instead of inf

Consider removing roundContext

roundContext bundles a rounding mode, which is stateless (set at construction and never changed) and a rounding status, which is stateful (meaningless at construction and only set later). These don't belong together.

Recommendation:

  1. Eliminate the roundContext type.
  2. Reassociate its methods with roundingMode.
  3. Adding a roundingStatus parameter to those methods that require it.

Security audit

This is required for approval by the ANZ open source committee to use this library in ANZ systems.

First step is to define what constitutes an acceptable audit.

Fix Abs on nans

current dec tests don't change the sign on negative NaNs, eg
abs(-NaN) == -NaN
Logic is that this is good in order for all operations on NaNs keep as mush information for diagnostic info as possible

Change function syntax to be rounding context oriented

Sooner or later rounding attributes are going to be implemented by parsing some sort of argument

proposal to change function syntax from d.Add(e) to context.Add(d, e)
where context is the rounding attribute.

Even with this implemented the standard d.Add(e) could still be implemented with half up rounding, for example

Equality behaviour of Nans

the IEEE 754-r specifies that:
"Four mutually exclusive relations are possible: less than, equal, greater than, and unordered. The last case
arises when at least one operand is NaN. Every NaN shall compare unordered with everything, including
itself"

which means that Nan != Nan
although there isn't a way to set equality behaviour in golang (that i know of), but it's got to do with the bits that make up the Nan

Test against a reference IEEE754 decimal implementation

I created https://github.com/anz-bank/decimal-reference. You can invoke it from the command line (supports cmdline args and stdin input modes) driving arbitrary operations using an RPN notation. The major caveat is that I based it on libdfp, which only wants to compile on Linux, so you need docker to run it.

It still needs to be hooked in for testing purposes, and if we can replace libdfp with a macOS-friendly library to avoid the Docker dependency, that would be awesome (though then we'd have to ensure some kind of build environment, probably Xcode, which has its own challenges).

Either way, we should stick to the cmdline/stdin approach to keep the moving parts fully decoupled.

Implement decimal32

As described in https://en.wikipedia.org/wiki/Decimal32_floating-point_format. The value of this is likely marginal, but might be useful in some scenarios:

  1. Memory constrained environments might benefit from the halving in size relative to decimal64.
  2. Since uint64 suffices for internal operations, it will likely be much faster than decimal64.
  3. 32-bit environments may benefit even more from the above two points.

Consider a package each for Decimal64 and Decimal128

Having to suffix every name with 64 is annoying. Should we have a decimal64 package (and therefore decimal128) instead?

The counterargument is that most users will have to use the suffix regardless, whether it's on the typename or the package name, so it's really only a headache for the maintainers.

Tighten up rounding logic

Currently, rounding status is one of eq0, lt5, eq5 and gt5. Tests then look for different combinations of these. For instance, round() has the following test:

if context.rndStatus == gt5 || context.rndStatus == eq5 {

This could be made more efficient if the constants were intialised with 1 << iota. You could then test:

if context.rndStatus & (gt5 | eq5) != 0 {

Convert to/from other types

E.g.:

  1. float64 (currently only to)
  2. math/big Float and Rat
  3. Third-party big-decimal libraries (I'd say not, but we should consider the pros and cons).

Implement error returns in Context struct

ieee 754 requires the following error types to be implemented:

invalidOperation
divisionByzero
inexact
overflow
underflow```

These should be returned as an error type in the context struct after an operation

Remove SNan panics?

SNan panics in functions such as signalNaN64 aren't needed due to the fact that the calling function can check if a number is a signalling Nan

Code becomes a lot simpler once panics are removed and Snan (or original weighted Nans) are returned

Performance analysis

There are several loops in the code that might be removable or at least improvable. Investigate and possibly rework to improve performance.

Reuse math/bits package

I just noticed that the standard math/bits package has some support for 128-bit operations. It might be worth using these in place of the equivalent uint128_t operations to reduce LoC.

Fix rounding issues with subtracting

When subtracting numbers 10000000000000000 + -77
rounding errors occur with the rescaling of 77 as the magnitude of the number decreases by a power of 10 then the truncated 7 would have resolution in the answer, but the number is already truncated.

current error is:
expected value: 0.9999999999999923
calculated value: 0.9999999999999931

Cleanup decimal64const.go

Let's clean this up.

  1. Use consistent prefixes.
  2. Suffix everything with 64.
  3. Show the math behind the values.

Thus:

const (
	decDigits64  = 16
	expBits64    = 10
	expRange64   = 3 << (expBits - 2)
	symmMaxExp64 = expRange64 / 2
	symmMinExp64 = 1 - symmMaxExp64
	maxExp64     = symmMaxExp64 - (decDigits64 - 1)
	minExp64     = symmMinExp64 - (decDigits64 - 1)
)

We end up with symm(Max|Min)Exp64 = 384|-383 and (max|min)Exp64 = 369|-398.

The decimal128 group can then be written in exactly the same form, with the only changes being to the first two constants:

	decDigits128  = 34
	expBits128    = 14

It could even be extended to decimal32, in the event that we ever wanted to implement it:

	decDigits32  = 7
	expBits32    = 8

Technically, we could even derive decDigits(32|64|128):

	decDigits64  = (64 - expBits64) * 3 / 10

64 - expBits64 is the number of bits of precision available for the significand and 3/10 is close enough to log(2)/log(10) to convert bits to digits for the given values of expBits(32|64|128). But I think this a bit too abstruse for the reader.

https://play.golang.org/p/X-WNwWgkcht

Fix Non-normalised Decimal numbers

Currently numbers are "normalised" so that there are trailing zeros,
for example 1 is stored as a significand 100000000000000 with an exponent of -15

Generally outputs are normalised from ParseDecimal and arithmetic functions.
Some problems are:

  1. Errors may arise when Decimal encodings are parsed in using methods other then strings
  2. Arithmetic functions currently have a remove trailing zeros function to avoid integer overflow
    If Decimal64s are stored without trailing zeros arithmetic functions may be faster

Review and round out decimal64 testing

A key concern is accurate numeric outcomes for all arithmetic operations, including parsing and formatting. The last thing we want is some variant of 0.1 + 0.1 + 0.1 ≠ 0.3.

Some thought needs to go into the completeness of the tests such that all conceivable edge cases are covered. The following is a reasonably thorough but incomplete set of cases to consider.

  1. Boundaries such the largest and smallest possible exponent
  2. Every combination of positive and negative arguments
  3. Every combination of kinds of arguments (SNaN, QNaN, ±∞, ±normal, ±subnormal, ±0)
    1. Make sure to include the largest and smallest ±normals and ±subnormals.
  4. Numbers close to ±0
  5. The smallest normal number and its neighborhood
  6. ±10ⁱ and its neighborhood for every representable i
  7. ±2ⁱ and its neighborhood for every representable i
  8. Operations jumping numbers into different phases (e.g., doubling ±the largest number = ±∞, halving ±the smallest number = ±0. Consider this for every operation
  9. Parsing massive numeric representations (e.g., a number with 5000 digits)
  10. Parsing out of range numbers (e.g., 1E1234 or 1E-1000)

Add Class function

This should return a string with a sign and the type of the decimal number
eg Class(0) --> +0
Class(-420) --> +Normal

Also consider adding a zero flavour in the constants flZero

Clean up rounding

Rounding is done in different places and users slightly different logic based on which arithmetic function.
It should be cleaned up and generalised to be used in one function

Should Neg… constants be removed?

Go has a math.MaxFloat64 but no math.NegativeFloat64 because it's trivial to write -math.MaxFloat64. Should the decimal library similarly avoid defining negative versions of a bunch of constants?

The main counterargument is that decimal.Max64().Neg() isn't quite as neat and it requires a computation on each use, whereas defining as a constant means it can be computed once at program initialisation time.

Make Size function O(1) time complexity

Size gets the magnitude of the significand,
currently using a for loop method that divides till it reaches zero.
@anzdaddy speculates that it might be possible to get the same result using bitwise inspection as used in the renormalise function, although this method currently doens't work for all decimal numbers

numBits := 64 - bits.LeadingZeros64(significand)
	numDigits := numBits * 3 / 10
	normExp := 15 - numDigits 

change int constants to uint64/int64 constants

32 bit go compilers (such as go play) result in an integer overflow when using this library with constants such as decimal64Base.

This needs to be changed to be a uint64 or int64 for consistency across compilers.

database/sql support

thanks for this package, does it possible to add database/sql support to allow to Scan to decimal value and store it inside db?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.