fraction.gno
5.47 Kb · 225 lines
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/moul/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}
