fraction.gno

  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 lowest
  3// terms with a positive denominator.
  4//
  5// This exists because there are no floats worth trusting on chain. 0.1 + 0.2 is
  6// not 0.3 in binary floating point, and a consensus system cannot afford an
  7// answer that depends on rounding. A fraction is exact: one third really is one
  8// 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 rather
 11// than silently wrapping — a wrapped numerator would be a wrong answer that
 12// looks fine.
 13//
 14// A live demo of this package is at
 15// [r/moul/x/daily/fractiondemo](/r/nym-moultest123/x/daily/fractiondemo/v0).
 16package fraction
 17
 18import (
 19	"errors"
 20	"strconv"
 21	"strings"
 22)
 23
 24// ErrZeroDenominator is returned when a denominator of zero is requested.
 25var ErrZeroDenominator = errors.New("fraction: zero denominator")
 26
 27// Fraction is an exact rational number in lowest terms, denominator > 0.
 28type Fraction struct {
 29	num, den int64
 30}
 31
 32// 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{}, ErrZeroDenominator
 36	}
 37	if den < 0 { // keep the sign in the numerator so comparisons are simple
 38		num, den = -num, -den
 39	}
 40	g := gcd(abs(num), den)
 41	if g > 1 {
 42		num, den = num/g, den/g
 43	}
 44	return Fraction{num, den}, nil
 45}
 46
 47// Int returns n as n/1.
 48func Int(n int64) Fraction { return Fraction{n, 1} }
 49
 50// Zero is 0/1.
 51func Zero() Fraction { return Fraction{0, 1} }
 52
 53// Num returns the numerator; Den the (always positive) denominator.
 54func (f Fraction) Num() int64 { return f.num }
 55
 56// Den returns the denominator, which is always > 0. The zero value of the type
 57// 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 1
 61	}
 62	return f.den
 63}
 64
 65// IsZero reports whether f == 0.
 66func (f Fraction) IsZero() bool { return f.num == 0 }
 67
 68func abs(x int64) int64 {
 69	if x < 0 {
 70		return -x
 71	}
 72	return x
 73}
 74
 75func gcd(a, b int64) int64 {
 76	for b != 0 {
 77		a, b = b, a%b
 78	}
 79	if a == 0 {
 80		return 1
 81	}
 82	return a
 83}
 84
 85// mulOK multiplies with an overflow check.
 86func mulOK(a, b int64) (int64, bool) {
 87	if a == 0 || b == 0 {
 88		return 0, true
 89	}
 90	p := a * b
 91	if p/b != a { // the classic check: dividing back must reproduce a
 92		return 0, false
 93	}
 94	return p, true
 95}
 96
 97// addOK adds with an overflow check.
 98func addOK(a, b int64) (int64, bool) {
 99	s := a + b
100	if (a > 0 && b > 0 && s < 0) || (a < 0 && b < 0 && s >= 0) {
101		return 0, false
102	}
103	return s, true
104}
105
106// Add returns f+g. ok is false on int64 overflow.
107func (f Fraction) Add(g Fraction) (Fraction, bool) { return combine(f, g, false) }
108
109// Sub returns f-g. ok is false on int64 overflow.
110func (f Fraction) Sub(g Fraction) (Fraction, bool) { return combine(f, g, true) }
111
112func 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{}, false
119	}
120	if sub {
121		b = -b
122	}
123	n, ok4 := addOK(a, b)
124	if !ok4 {
125		return Fraction{}, false
126	}
127	out, err := New(n, d)
128	return out, err == nil
129}
130
131// 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{}, false
137	}
138	out, err := New(n, d)
139	return out, err == nil
140}
141
142// 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{}, false
146	}
147	n, ok1 := mulOK(f.num, g.Den())
148	d, ok2 := mulOK(f.Den(), g.num)
149	if !ok1 || !ok2 {
150		return Fraction{}, false
151	}
152	out, err := New(n, d)
153	return out, err == nil
154}
155
156// Neg returns -f.
157func (f Fraction) Neg() Fraction { return Fraction{-f.num, f.Den()} }
158
159// 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 overflow
166		fa := float64(f.num) / float64(f.Den())
167		fb := float64(g.num) / float64(g.Den())
168		switch {
169		case fa < fb:
170			return -1
171		case fa > fb:
172			return 1
173		}
174		return 0
175	}
176	switch {
177	case a < b:
178		return -1
179	case a > b:
180		return 1
181	}
182	return 0
183}
184
185// Equal reports exact equality.
186func (f Fraction) Equal(g Fraction) bool { return f.Cmp(g) == 0 }
187
188// 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}
195
196// Decimal renders f with exactly places digits after the point, truncated
197// 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 = 0
202	}
203	n, d := f.num, f.Den()
204	neg := n < 0
205	if neg {
206		n = -n
207	}
208	whole := n / d
209	rem := n % d
210	var b strings.Builder
211	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 *= 10
221		b.WriteString(strconv.FormatInt(rem/d, 10))
222		rem %= d
223	}
224	return b.String()
225}