gno.land/p/moul/x/daily/fraction/v0⧉

1// Package fraction is exact rational arithmetic as a pure, reusable package:2// values are p/q with int64 numerator and denominator, always kept in lowest3// terms with a positive denominator.4//5// This exists because there are no floats worth trusting on chain. 0.1 + 0.2 is6// not 0.3 in binary floating point, and a consensus system cannot afford an7// answer that depends on rounding. A fraction is exact: one third really is one8// third, and only becomes lossy at the moment you ask for a decimal.9//10// Every operation is checked for int64 overflow and returns ok=false rather11// than silently wrapping — a wrapped numerator would be a wrong answer that12// looks fine.13//14// A live demo of this package is at15// [r/moul/x/daily/fractiondemo](/r/moul/x/daily/fractiondemo/v0).16package fraction1718import (19	"errors"20	"strconv"21	"strings"22)2324// ErrZeroDenominator is returned when a denominator of zero is requested.25var ErrZeroDenominator = errors.New("fraction: zero denominator")2627// Fraction is an exact rational number in lowest terms, denominator > 0.28type Fraction struct {29	num, den int6430}3132// New returns num/den reduced, or an error when den is zero.33func New(num, den int64) (Fraction, error) {34	if den == 0 {35		return Fraction{}, ErrZeroDenominator36	}37	if den < 0 { // keep the sign in the numerator so comparisons are simple38		num, den = -num, -den39	}40	g := gcd(abs(num), den)41	if g > 1 {42		num, den = num/g, den/g43	}44	return Fraction{num, den}, nil45}4647// Int returns n as n/1.48func Int(n int64) Fraction { return Fraction{n, 1} }4950// Zero is 0/1.51func Zero() Fraction { return Fraction{0, 1} }5253// Num returns the numerator; Den the (always positive) denominator.54func (f Fraction) Num() int64 { return f.num }5556// Den returns the denominator, which is always > 0. The zero value of the type57// has den == 0, so treat it as 1 to keep an un-initialised Fraction usable.58func (f Fraction) Den() int64 {59	if f.den == 0 {60		return 161	}62	return f.den63}6465// IsZero reports whether f == 0.66func (f Fraction) IsZero() bool { return f.num == 0 }6768func abs(x int64) int64 {69	if x < 0 {70		return -x71	}72	return x73}7475func gcd(a, b int64) int64 {76	for b != 0 {77		a, b = b, a%b78	}79	if a == 0 {80		return 181	}82	return a83}8485// mulOK multiplies with an overflow check.86func mulOK(a, b int64) (int64, bool) {87	if a == 0 || b == 0 {88		return 0, true89	}90	p := a * b91	if p/b != a { // the classic check: dividing back must reproduce a92		return 0, false93	}94	return p, true95}9697// addOK adds with an overflow check.98func addOK(a, b int64) (int64, bool) {99	s := a + b100	if (a > 0 && b > 0 && s < 0) || (a < 0 && b < 0 && s >= 0) {101		return 0, false102	}103	return s, true104}105106// Add returns f+g. ok is false on int64 overflow.107func (f Fraction) Add(g Fraction) (Fraction, bool) { return combine(f, g, false) }108109// Sub returns f-g. ok is false on int64 overflow.110func (f Fraction) Sub(g Fraction) (Fraction, bool) { return combine(f, g, true) }111112func combine(f, g Fraction, sub bool) (Fraction, bool) {113	fd, gd := f.Den(), g.Den()114	a, ok1 := mulOK(f.num, gd)115	b, ok2 := mulOK(g.num, fd)116	d, ok3 := mulOK(fd, gd)117	if !ok1 || !ok2 || !ok3 {118		return Fraction{}, false119	}120	if sub {121		b = -b122	}123	n, ok4 := addOK(a, b)124	if !ok4 {125		return Fraction{}, false126	}127	out, err := New(n, d)128	return out, err == nil129}130131// Mul returns f*g. ok is false on int64 overflow.132func (f Fraction) Mul(g Fraction) (Fraction, bool) {133	n, ok1 := mulOK(f.num, g.num)134	d, ok2 := mulOK(f.Den(), g.Den())135	if !ok1 || !ok2 {136		return Fraction{}, false137	}138	out, err := New(n, d)139	return out, err == nil140}141142// Div returns f/g. ok is false on overflow or division by zero.143func (f Fraction) Div(g Fraction) (Fraction, bool) {144	if g.IsZero() {145		return Fraction{}, false146	}147	n, ok1 := mulOK(f.num, g.Den())148	d, ok2 := mulOK(f.Den(), g.num)149	if !ok1 || !ok2 {150		return Fraction{}, false151	}152	out, err := New(n, d)153	return out, err == nil154}155156// Neg returns -f.157func (f Fraction) Neg() Fraction { return Fraction{-f.num, f.Den()} }158159// Cmp returns -1, 0 or +1 as f is less than, equal to, or greater than g.160// Compares by cross-multiplication, so it is exact — no decimal conversion.161func (f Fraction) Cmp(g Fraction) int {162	a, ok1 := mulOK(f.num, g.Den())163	b, ok2 := mulOK(g.num, f.Den())164	if !ok1 || !ok2 {165		// fall back to a lossy comparison only when exact would overflow166		fa := float64(f.num) / float64(f.Den())167		fb := float64(g.num) / float64(g.Den())168		switch {169		case fa < fb:170			return -1171		case fa > fb:172			return 1173		}174		return 0175	}176	switch {177	case a < b:178		return -1179	case a > b:180		return 1181	}182	return 0183}184185// Equal reports exact equality.186func (f Fraction) Equal(g Fraction) bool { return f.Cmp(g) == 0 }187188// String renders "p/q", or just "p" when the denominator is 1.189func (f Fraction) String() string {190	if f.Den() == 1 {191		return strconv.FormatInt(f.num, 10)192	}193	return strconv.FormatInt(f.num, 10) + "/" + strconv.FormatInt(f.Den(), 10)194}195196// Decimal renders f with exactly places digits after the point, truncated197// toward zero. THIS is where exactness ends — 1/3 cannot be written in decimal,198// so the caller chooses how much to lose and when.199func Decimal(f Fraction, places int) string {200	if places < 0 {201		places = 0202	}203	n, d := f.num, f.Den()204	neg := n < 0205	if neg {206		n = -n207	}208	whole := n / d209	rem := n % d210	var b strings.Builder211	if neg && (whole != 0 || rem != 0) {212		b.WriteByte('-')213	}214	b.WriteString(strconv.FormatInt(whole, 10))215	if places == 0 {216		return b.String()217	}218	b.WriteByte('.')219	for i := 0; i < places; i++ {220		rem *= 10221		b.WriteString(strconv.FormatInt(rem/d, 10))222		rem %= d223	}224	return b.String()225}226