rat128

package module
v0.1.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 9, 2024 License: Apache-2.0 Imports: 7 Imported by: 0

README

rat128

Fixed-precision rational numbers for Go. This module has no dependencies and is fairly straightforward to use:

  • Construct new values with var x rat128.N, x := rat128.New(m, n), or x, err := rat128.Try(m, n).
  • Retrieve the numerator and denominator with x.Num() and x.Den(), respectively.
  • Perform arithmetic with panicking x.Add(y), x.Mul(y) or error-returning x.TryAdd(y), x.TryMul(y), etc.
  • Convert from/to float64 with FromFloat64 and x.Float64() respectively.
  • Convert from/to decimal strings ("12.34") with ParseDecimalString and x.DecimalString(digits) respectively.

Design Goals

  • First and foremost: value semantics. Unlike big.Rat in the standard library, rat128.N is a value type like int64 or float32 and is safe to copy and compare with == and !=. Methods return values instead of mutating their receiver.
  • Mathematical operations should return correct results. If they don't, the incorrect behavior is a bug and fixing this bug will be treated as a non-breaking change. Do not rely on incorrect results.
  • Widened integer arithmetic is used where possible to avoid overflow of intermediate values used in basic arithmetic operations (add, subtract, multiply, and divide). The finite precision is more limiting than big.Rat, however, and panics from overflow of the numerator or denominator in the final result are possible.
  • Valid values are always in reduced form, to simplify operations and reduce the risk of overflow.
  • Converting to and from floating-point values should be exact wherever it is possible to do so, and approximation should be explicit.
  • There are panicking and panic-free versions of most operations. This means there are actually three ways to use this library:
    • Use the panicking operations (New, Add, etc.)
    • Use the panic-free operations (Try, TryAdd, etc.) and check for errors
    • Use the panic-free operations and ignore the errors; this is not recommended but will be fastest

Reporting issues

File bug reports, feature requests, etc. through GitHub Issues on this repository.

The following are always considered issues:

  • Incorrect mathematical results
  • Violation of the design goals; though fixing these may require breaking changes and thus a new major version
  • Unexpected behavior; for example, operations on otherwise valid values returning invalid results instead of valid results, a panic, or an error
  • Panics in Try* functions/methods; these return errors, so ordinary arithmetic exceptions should not cause panics

The following will be evaluated on a case-by-case basis:

  • Optimization; in particular, micro-optimizations that reduce readability of the code for little measurable benefit may be rejected
  • (Un-)marshaling/(de-)serializing in various formats
  • Undefined behavior; for example, the results of operations on invalid values created through unsafe code, reflection, unsychronized sharing across goroutines, cgo hacks, memory corruption, etc.
  • Converting to formats outside of the core language and standard library
  • Performance regressions; in general, this library should outperform big.Rat on an apples-to-apples basis on 64-bit machines, but the exact performance characteristics are not guaranteed

To Do

  • Improved overflow detection to reduce usage of widened arithmetic
  • Other optimizations where feasible/practical (e.g. faster Cmp)
  • More test coverage
  • Convenience methods as practical usage demonstrates their value

Documentation

Overview

Package rat128 provides fixed-precision rational numbers. See the N type and New function for details.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	ErrDenInvalid  = errors.New("denominator is not positive")
	ErrDenOverflow = errors.New("denominator overflow")
	ErrNumOverflow = errors.New("numerator overflow")
	ErrDivByZero   = errors.New("division by zero")
	ErrFmtInvalid  = errors.New("invalid number format")
)

Common errors returned by functions in this package.

Functions

func ExtGCD 

func ExtGCD(m, n int64) (a, b, d int64)

ExtGCD returns the GCD of m and n along with the Bézout coefficients. That is, it returns a, b, d such that: 

a*m + b*n == d == GCD(m, n)

func GCD 

func GCD(m, n int64) int64

GCD returns the greatest common denominator (GCD) of m and n. The GCD is the largest integer that divides both m and n.

Types

type N 

type N struct {
	// contains filtered or unexported fields
}

N is a rational number with 64-bit numerator and denominator.

One bit of the numerator is used for the sign and the denominator must be positive, so only 63 bits of precision are actually available in each. Internally, the denominator is biased by 1, which means the zero value is equivalent to 0/1 and thus valid and equal to 0. Due to the asymmetry of the int64 type (|math.MinInt64| > math.MaxInt64), math.MinInt64 is not a valid numerator in reduced form.

Valid values are obtained in the following ways:

  • the zero value of the type N
  • returned by the New or Try functions (with non-nil error)
  • returned by arithmetic on any valid values (with non-nil error)
  • copied from a valid value

N has proper value semantics and its values can be freely copied. Two valid values of N can be compared using the == and != operators.

func FromBigRat 

func FromBigRat(r *big.Rat) (N, error)

FromBigRat converts a big.Rat to N, if it is possible to do so.

func FromFloat64 

func FromFloat64(v float64) (N, error)

FromFloat64 extracts a rational number from a float64. The result will be exactly equal to v, or else an error will be returned.

func New 

func New(num, den int64) N

New is like Try but panics instead of returning an error.

Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	n := rat128.New(1, 2)
	fmt.Println(n)
}

Output:

1/2

func ParseDecimalString 

func ParseDecimalString(s string) (N, error)

ParseDecimalString parses a string representation of a decimal number as a rational number. The string must be in the form "A", "A.B", or ".B" where A is an integer that may have leading zeroes and may be negative (indicated with leading hyphen) and B is an integer that may have trailing zeroes. The concatenation of A without leading zeroes and B without trailing zeroes must not overflow int64.

func ParseRationalString 

func ParseRationalString(s string) (N, error)

ParseRationalString parses a string representation of a rational number. The string must be in the form "m/n", where m and n are integers in base 10, n is not zero, and only m may be negative (indicated with leading hyphen). It is not necessary for m/n to be in lowest terms, but the result will be. Also, m and n cannot overflow int64.

Example (DenomZero) 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	_, err := rat128.ParseRationalString("1/0")
	fmt.Println(err)
}

Output:

denominator is not positive
Example (NegOneHalf) 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	n, err := rat128.ParseRationalString("-1/2")
	if err != nil {
		panic(err)
	}
	fmt.Println(n)
}

Output:

-1/2
Example (OneHalf) 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	n, err := rat128.ParseRationalString("1/2")
	if err != nil {
		panic(err)
	}
	fmt.Println(n)
}

Output:

1/2
Example (TwoFourths) 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	n, err := rat128.ParseRationalString("2/4")
	if err != nil {
		panic(err)
	}
	fmt.Println(n)
}

Output:

1/2

func Try 

func Try(num, den int64) (N, error)

Try creates a new rational number with the given numerator and denominator. Try returns an error if the reduced numerator is math.MinInt64 or if the denominator is not positive.

Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	n, err := rat128.Try(1, 2)
	if err != nil {
		panic(err)
	}
	fmt.Println(n)
}

Output:

1/2
Example (DenomZero) 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	_, err := rat128.Try(1, 0)
	fmt.Println(err)
}

Output:

denominator is not positive

func (N) Abs 

func (x N) Abs() N

Abs returns the absolute value of x, |x|.

func (N) Add 

func (x N) Add(y N) N

Add adds x and y and returns the result. Add panics if the result would overflow.

Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	x := rat128.New(1, 2)
	y := rat128.New(1, 3)
	z := x.Add(y)
	fmt.Println(z)
}

Output:

5/6

func (N) BigRat 

func (x N) BigRat() *big.Rat

BigRat converts x to a new big.Rat.

func (N) Cmp 

func (x N) Cmp(y N) int

Cmp returns -1 if x < y, 0 if x == y, and 1 if x > y.

func (N) DecimalString 

func (x N) DecimalString(prec int) string

DecimalString returns a string representation of x, as a decimal number to the given number of digits after the decimal point. The last digit is rounded to nearest, with ties rounded away from zero. If prec <= 0, the decimal point is omitted from the string. If the result of rounding is zero but x is negative, the string will still include a negative sign.

The following relation should hold for all valid values of x: 

x.DecimalString(prec) == x.BigRat().FloatString(prec)

func (N) Den 

func (x N) Den() int64

Den returns the denominator of x.

func (N) Div 

func (x N) Div(y N) N

Div divides x by y and returns the result. The following are equivalent in outcome and behavior: 

x.Div(y) == x.Mul(y.Inv())
Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	x := rat128.New(1, 2)
	y := rat128.New(2, 3)
	z := x.Div(y)
	fmt.Println(z)
}

Output:

3/4

func (N) Float64 

func (x N) Float64() (v float64, exact bool)

Float64 returns the floating-point equivalent of x. If exact is true, then v is exactly equal to x; otherwise, it is the closest approximation.

func (N) Inv 

func (x N) Inv() N

Inv is like TryInv but panics instead of returning an error.

func (N) IsValid 

func (x N) IsValid() bool

IsValid returns true if x is a valid rational number. Invalid numbers do not arise under normal circumstances, but may occur if a value is constructed or manipulated using unsafe operations.

func (N) IsZero 

func (x N) IsZero() bool

IsZero returns true if x is equal to 0.

func (N) Mul 

func (x N) Mul(y N) N

Mul multiplies x and y and returns the result. Mul panics if the result would overflow.

Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	x := rat128.New(1, 2)
	y := rat128.New(2, 3)
	z := x.Mul(y)
	fmt.Println(z)
}

Output:

1/3

func (N) Neg 

func (x N) Neg() N

Neg returns the negation of x, -x.

func (N) Num 

func (x N) Num() int64

Num returns the numerator of x.

func (N) RationalString 

func (x N) RationalString(sep string) string

RationalString returns a string representation of x, as m+sep+n. For example, x.String() is equivalent to x.RationalString("/").

func (N) Sign 

func (x N) Sign() int

Sign returns the sign of x: -1 if x < 0, 0 if x == 0, and 1 if x > 0.

func (N) String 

func (x N) String() string

String returns a string representation of x, as m/n.

func (N) Sub 

func (x N) Sub(y N) N

Sub subtracts y from x and returns the result. The following are equivalent in outcome and behavior: 

x.Sub(y) == x.Add(y.Neg())
Example 
package main

import (
	"fmt"

	"github.com/kbolino/rat128"
)

func main() {
	x := rat128.New(1, 2)
	y := rat128.New(1, 3)
	z := x.Sub(y)
	fmt.Println(z)
}

Output:

1/6

func (N) TryAdd 

func (x N) TryAdd(y N) (N, error)

TryAdd adds x and y and returns the result. TryAdd returns 0 and a non-nil error if the result would overflow.

func (N) TryDiv 

func (x N) TryDiv(y N) (N, error)

TryDiv divides x by y and returns the result. TryDiv returns 0 and a non-nil error for division by zero or if the result would overflow.

func (N) TryInv 

func (x N) TryInv() (N, error)

TryInv returns the inverse of x, 1/x. If x.Num() == 0, TryInv returns (0, ErrDivByZero).

func (N) TryMul 

func (x N) TryMul(y N) (N, error)

TryMul multiplies x and y and returns the result. TryMul returns 0 and a non-nil error if the result would overflow.

func (N) TrySub 

func (x N) TrySub(y N) (N, error)

TrySub subtracts y from x and returns the result. TrySub returns 0 and a non-nil error if the result would overflow.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.