decimal.bend

bend-kit-bignum@0.1.0.0 · 436 lines · 50 definitions

1# Exact signed decimals: a BigInt coefficient over a power of ten.
2import Base
3import bend-kit-bignum@0.1.0.0/bigint.bend as Big
4
5# The value is unscaled / 10^scale. Scale is kept as written, so 1.50 stays
6# 1.50 (money keeps its cents); cmp is numeric, and normalize strips trailing
7# zeros. No operation rounds: an inexact request answers None.
8type Decimal is Data:
9  Decimal{unscaled: Big.BigInt, scale: Nat}
10
11def Decimal.zero() -> Decimal:
12  Decimal{Big.BigInt.zero(), 0n}
13
14def Decimal.pow10(n: Nat) -> Big.BigInt:
15  Big.BigInt.pow(Big.BigInt.from_u32(10), n)
16
17# u * 10^k, without a multiply when k is 0.
18def Decimal.up(u: Big.BigInt, k: Nat) -> Big.BigInt:
19  match k:
20    case 0n:
21      u
22    case 1n+p:
23      Big.BigInt.mul(u, Decimal.pow10(1n+p))
24
25def Decimal.neg(d: Decimal) -> Decimal:
26  match d:
27    case Decimal{u, s}:
28      Decimal{Big.BigInt.neg(u), s}
29
30def Decimal.abs(d: Decimal) -> Decimal:
31  match d:
32    case Decimal{u, s}:
33      Decimal{Big.BigInt.abs(u), s}
34
35def Decimal.is_zero(d: Decimal) -> Bool:
36  match d:
37    case Decimal{u, s}:
38      Big.BigInt.is_zero(u)
39
40def Decimal.add(a: Decimal, b: Decimal) -> Decimal:
41  match a b:
42    case Decimal{ua, +sa} Decimal{ub, +sb}:
43      Decimal{Big.BigInt.add(Decimal.up(ua, Nat.sub(sb, sa)),
44        Decimal.up(ub, Nat.sub(sa, sb))), Nat.max(sa, sb)}
45
46def Decimal.sub(a: Decimal, b: Decimal) -> Decimal:
47  Decimal.add(a, Decimal.neg(b))
48
49def Decimal.mul(a: Decimal, b: Decimal) -> Decimal:
50  match a b:
51    case Decimal{ua, sa} Decimal{ub, sb}:
52      Decimal{Big.BigInt.mul(ua, ub), Nat.add(sa, sb)}
53
54def Decimal.cmp(a: Decimal, b: Decimal) -> Cmp:
55  match a b:
56    case Decimal{ua, +sa} Decimal{ub, +sb}:
57      Big.BigInt.cmp(Decimal.up(ua, Nat.sub(sb, sa)),
58        Decimal.up(ub, Nat.sub(sa, sb)))
59
60# The quotient of a division whose divisor is known to be nonzero.
61def Decimal.quot(m: Maybe<&1, Big.BigInt & Big.BigInt>) -> Big.BigInt:
62  match m:
63    case Some{(q, r)}:
64      q
65    case None{}:
66      Big.BigInt.zero()
67
68# (remainder is zero, quotient) of u / k, for a nonzero k.
69def Decimal.divk.m(m: Maybe<&1, Big.BigInt & Big.BigInt>) -> Bool & Big.BigInt:
70  match m:
71    case Some{(q, r)}:
72      (Big.BigInt.is_zero(r), q)
73    case None{}:
74      (False{}, Big.BigInt.zero())
75
76def Decimal.divk(u: Big.BigInt, k: U32) -> Bool & Big.BigInt:
77  Decimal.divk.m(Big.BigInt.divmod(u, Big.BigInt.from_u32(k)))
78
79def Decimal.is_one(u: Big.BigInt) -> Bool:
80  Cmp.is_eq(Big.BigInt.cmp(u, Big.BigInt.one()))
81
82def Decimal.lowest.fix(neg: Bool, n: Big.BigInt, d: Big.BigInt) ->
83  Big.BigInt & Big.BigInt:
84  match neg:
85    case True{}:
86      (Big.BigInt.neg(n), Big.BigInt.neg(d))
87    case False{}:
88      (n, d)
89
90def Decimal.lowest.den(n: Big.BigInt, +d: Big.BigInt) -> Big.BigInt & Big.BigInt:
91  Decimal.lowest.fix(Cmp.is_lt(Big.BigInt.cmp(d, Big.BigInt.zero())), n, d)
92
93def Decimal.lowest.by(n: Big.BigInt, d: Big.BigInt, +g: Big.BigInt) ->
94  Big.BigInt & Big.BigInt:
95  Decimal.lowest.den(Decimal.quot(Big.BigInt.divmod(n, g)),
96    Decimal.quot(Big.BigInt.divmod(d, g)))
97
98# n / d in lowest terms with a positive denominator; d must be nonzero.
99def Decimal.lowest(+n: Big.BigInt, +d: Big.BigInt) -> Big.BigInt & Big.BigInt:
100  Decimal.lowest.by(n, d, Big.BigInt.gcd(n, d))
101
102# Each step divides d by 2 or 5 and scales n to match, so a d of D digits
103# needs fewer than 4D steps; f is that bound.
104def Decimal.frac.go(f: Nat, n: Big.BigInt, k: Nat, one: Bool,
105  t2: Bool & Big.BigInt, t5: Bool & Big.BigInt) -> Maybe<&2, Decimal>:
106  match f:
107    case 0n:
108      None{}
109    case 1n+g:
110      match one:
111        case True{}:
112          Some{Decimal{n, k}}
113        case False{}:
114          (z2, q2) = t2
115          match z2:
116            case True{}:
117              +d = {q2 : Big.BigInt}
118              Decimal.frac.go(g, Big.BigInt.mul(n, Big.BigInt.from_u32(5)),
119                1n+k, Decimal.is_one(d), Decimal.divk(d, 2),
120                Decimal.divk(d, 5))
121            case False{}:
122              (z5, q5) = t5
123              match z5:
124                case True{}:
125                  +d = {q5 : Big.BigInt}
126                  Decimal.frac.go(g, Big.BigInt.mul(n, Big.BigInt.from_u32(2)),
127                    1n+k, Decimal.is_one(d), Decimal.divk(d, 2),
128                    Decimal.divk(d, 5))
129                case False{}:
130                  None{}
131
132def Decimal.frac.run(p: Big.BigInt & Big.BigInt) -> Maybe<&2, Decimal>:
133  (n, d) = p
134  +e = {d : Big.BigInt}
135  Decimal.frac.go(
136    (4n * String.length(Big.BigInt.show(e)) + 1n : Nat),
137    n, 0n, Decimal.is_one(e), Decimal.divk(e, 2), Decimal.divk(e, 5))
138
139def Decimal.frac.if(z: Bool, n: Big.BigInt, d: Big.BigInt) ->
140  Maybe<&2, Decimal>:
141  match z:
142    case True{}:
143      None{}
144    case False{}:
145      Decimal.frac.run(Decimal.lowest(n, d))
146
147# n / d at the smallest exact scale, or None when d is zero or the decimal
148# expansion does not terminate (d has a prime factor other than 2 and 5).
149def Decimal.from_fraction(n: Big.BigInt, +d: Big.BigInt) -> Maybe<&2, Decimal>:
150  Decimal.frac.if(Big.BigInt.is_zero(d), n, d)
151
152# a / b exactly, at the smallest scale that holds it; None for a zero
153# divisor or a repeating quotient (use Rational for those).
154def Decimal.div_exact(a: Decimal, b: Decimal) -> Maybe<&2, Decimal>:
155  match a b:
156    case Decimal{ua, sa} Decimal{ub, sb}:
157      Decimal.from_fraction(Big.BigInt.mul(ua, Decimal.pow10(sb)),
158        Big.BigInt.mul(ub, Decimal.pow10(sa)))
159
160def Decimal.normalize.go(s: Nat, u: Big.BigInt, qr: Bool & Big.BigInt) ->
161  Decimal:
162  match s:
163    case 0n:
164      Decimal{u, 0n}
165    case 1n+p:
166      (z, q) = qr
167      match z:
168        case True{}:
169          +v = {q : Big.BigInt}
170          Decimal.normalize.go(p, v, Decimal.divk(v, 10))
171        case False{}:
172          Decimal{u, 1n+p}
173
174# The same value at the smallest scale: 1.500 is 1.5, 0.00 is 0.
175def Decimal.normalize(d: Decimal) -> Decimal:
176  match d:
177    case Decimal{+u, s}:
178      Decimal.normalize.go(s, u, Decimal.divk(u, 10))
179
180def Decimal.rescale.keep(z: Bool, q: Big.BigInt, t: Nat) -> Maybe<&2, Decimal>:
181  match z:
182    case True{}:
183      Some{Decimal{q, t}}
184    case False{}:
185      None{}
186
187def Decimal.rescale.cut(t: Nat, m: Maybe<&1, Big.BigInt & Big.BigInt>) ->
188  Maybe<&2, Decimal>:
189  match m:
190    case Some{(q, r)}:
191      Decimal.rescale.keep(Big.BigInt.is_zero(r), q, t)
192    case None{}:
193      None{}
194
195def Decimal.rescale.if(up: Bool, u: Big.BigInt, +s: Nat, +t: Nat) ->
196  Maybe<&2, Decimal>:
197  match up:
198    case True{}:
199      Some{Decimal{Decimal.up(u, Nat.sub(t, s)), t}}
200    case False{}:
201      Decimal.rescale.cut(t, Big.BigInt.divmod(u, Decimal.pow10(Nat.sub(s, t))))
202
203# The same value at scale t, or None when that would drop a nonzero digit:
204# rescale(1.5, 2n) is 1.50; rescale(1.25, 1n) is None, never 1.2 or 1.3.
205def Decimal.rescale(d: Decimal, +t: Nat) -> Maybe<&2, Decimal>:
206  match d:
207    case Decimal{u, +s}:
208      Decimal.rescale.if(Nat.is_le(s, t), u, s, t)
209
210def Decimal.show.split(+s: Nat, +ds: String) -> String:
211  +i = {Nat.sub(String.length(ds), s) : Nat}
212  String.append(String.take(ds, i), SCon{Chr{46}, String.drop(ds, i)})
213
214# Digits with a point s places from the right, zero-padded to one whole digit.
215def Decimal.show.point(+s: Nat, +ds: String) -> String:
216  match s:
217    case 0n:
218      ds
219    case 1n+p:
220      Decimal.show.split(1n+p, String.append(
221        String.repeat("0", Nat.sub(2n+p, String.length(ds))), ds))
222
223def Decimal.show.sign(neg: Bool, body: String) -> String:
224  match neg:
225    case True{}:
226      SCon{Chr{45}, body}
227    case False{}:
228      body
229
230# Plain notation with every scale digit: -12.50, 0.001, 7. Never an exponent.
231def Decimal.show(d: Decimal) -> String:
232  match d:
233    case Decimal{+u, s}:
234      Decimal.show.sign(Cmp.is_lt(Big.BigInt.cmp(u, Big.BigInt.zero())),
235        Decimal.show.point(s, Big.BigInt.show(Big.BigInt.abs(u))))
236
237# A character of a number.
238type Class is Data:
239  Digit{code: U32}
240  Minus{}
241  Plus{}
242  Point{}
243  Expo{}
244  Other{}
245
246def Decimal.class.sym(minus: Bool, plus: Bool, point: Bool, expo: Bool) ->
247  Class:
248  match minus:
249    case True{}:
250      Minus{}
251    case False{}:
252      match plus:
253        case True{}:
254          Plus{}
255        case False{}:
256          match point:
257            case True{}:
258              Point{}
259            case False{}:
260              match expo:
261                case True{}:
262                  Expo{}
263                case False{}:
264                  Other{}
265
266def Decimal.class.if(digit: Bool, +c: U32) -> Class:
267  match digit:
268    case True{}:
269      Digit{c}
270    case False{}:
271      Decimal.class.sym(U32.is_eq(c, 45), U32.is_eq(c, 43), U32.is_eq(c, 46),
272        Bool.or(U32.is_eq(c, 101), U32.is_eq(c, 69)))
273
274def Decimal.class(+c: U32) -> Class:
275  Decimal.class.if(Bool.and(U32.is_ge(c, 48), U32.is_le(c, 57)), c)
276
277# Where the reader is. ds holds the coefficient's digits, last first, without
278# leading zeros; sc counts fraction digits; e is the exponent's magnitude.
279type Scan is Data:
280  Bad{}
281  Begin{}
282  Signed{neg: Bool}
283  Whole{neg: Bool, ds: String}
284  Dot{neg: Bool, ds: String}
285  Frac{neg: Bool, ds: String, sc: Nat}
286  Exp{neg: Bool, ds: String, sc: Nat}
287  ExpSigned{neg: Bool, ds: String, sc: Nat, eneg: Bool}
288  ExpDigits{neg: Bool, ds: String, sc: Nat, eneg: Bool, e: U32}
289
290def Decimal.read.lead(zero: Bool, c: U32) -> String:
291  match zero:
292    case True{}:
293      SNil{}
294    case False{}:
295      SCon{Chr{c}, SNil{}}
296
297def Decimal.read.push(+c: U32, ds: String) -> String:
298  match ds:
299    case SNil{}:
300      Decimal.read.lead(U32.is_eq(c, 48), c)
301    case SCon{h, t}:
302      SCon{Chr{c}, SCon{h, t}}
303
304# ponytail: exponents past 100000 in magnitude are refused, since 1e100000
305# materializes 100000 digits; raise the bound if a caller needs more.
306def Decimal.read.exp(big: Bool, neg: Bool, ds: String, sc: Nat, eneg: Bool,
307  e: U32) -> Scan:
308  match big:
309    case True{}:
310      Bad{}
311    case False{}:
312      ExpDigits{neg, ds, sc, eneg, e}
313
314def Decimal.read.step(st: Scan, cl: Class) -> Scan:
315  match st:
316    case Begin{}:
317      match cl:
318        case Digit{c}:
319          Whole{False{}, Decimal.read.push(c, SNil{})}
320        case Minus{}:
321          Signed{True{}}
322        case Plus{}:
323          Signed{False{}}
324        case _:
325          Bad{}
326    case Signed{neg}:
327      match cl:
328        case Digit{c}:
329          Whole{neg, Decimal.read.push(c, SNil{})}
330        case _:
331          Bad{}
332    case Whole{neg, ds}:
333      match cl:
334        case Digit{c}:
335          Whole{neg, Decimal.read.push(c, ds)}
336        case Point{}:
337          Dot{neg, ds}
338        case Expo{}:
339          Exp{neg, ds, 0n}
340        case _:
341          Bad{}
342    case Dot{neg, ds}:
343      match cl:
344        case Digit{c}:
345          Frac{neg, Decimal.read.push(c, ds), 1n}
346        case _:
347          Bad{}
348    case Frac{neg, ds, sc}:
349      match cl:
350        case Digit{c}:
351          Frac{neg, Decimal.read.push(c, ds), 1n+sc}
352        case Expo{}:
353          Exp{neg, ds, sc}
354        case _:
355          Bad{}
356    case Exp{neg, ds, sc}:
357      match cl:
358        case Digit{c}:
359          ExpDigits{neg, ds, sc, False{}, U32.sub(c, 48)}
360        case Minus{}:
361          ExpSigned{neg, ds, sc, True{}}
362        case Plus{}:
363          ExpSigned{neg, ds, sc, False{}}
364        case _:
365          Bad{}
366    case ExpSigned{neg, ds, sc, eneg}:
367      match cl:
368        case Digit{c}:
369          ExpDigits{neg, ds, sc, eneg, U32.sub(c, 48)}
370        case _:
371          Bad{}
372    case ExpDigits{neg, ds, sc, eneg, e}:
373      match cl:
374        case Digit{c}:
375          +x = (e * 10 + c - 48 : U32)
376          Decimal.read.exp(U32.is_gt(x, 100000), neg, ds, sc, eneg, x)
377        case _:
378          Bad{}
379    case _:
380      Bad{}
381
382def Decimal.read.go(s: String, st: Scan) -> Scan:
383  match s:
384    case SNil{}:
385      st
386    case SCon{Chr{x}, t}:
387      Decimal.read.go(t, Decimal.read.step(st, Decimal.class(x)))
388
389def Decimal.read.abs(m: Maybe<&2, Big.BigInt>) -> Big.BigInt:
390  match m:
391    case Some{v}:
392      v
393    case None{}:
394      Big.BigInt.zero()
395
396# The coefficient; ds holds only digits, so read cannot fail.
397def Decimal.read.coef(neg: Bool, ds: String) -> Big.BigInt:
398  match neg:
399    case True{}:
400      Big.BigInt.neg(Decimal.read.abs(Big.BigInt.read(String.reverse(ds))))
401    case False{}:
402      Decimal.read.abs(Big.BigInt.read(String.reverse(ds)))
403
404def Decimal.read.digits(neg: Bool, ds: String) -> Big.BigInt:
405  match ds:
406    case SNil{}:
407      Big.BigInt.zero()
408    case SCon{h, t}:
409      Decimal.read.coef(neg, SCon{h, t})
410
411# A negative exponent adds scale; a positive one spends scale, then multiplies.
412def Decimal.read.shift(u: Big.BigInt, +sc: Nat, eneg: Bool, +e: Nat) -> Decimal:
413  match eneg:
414    case True{}:
415      Decimal{u, Nat.add(sc, e)}
416    case False{}:
417      Decimal{Decimal.up(u, Nat.sub(e, sc)), Nat.sub(sc, e)}
418
419def Decimal.read.fin(st: Scan) -> Maybe<&2, Decimal>:
420  match st:
421    case Whole{neg, ds}:
422      Some{Decimal{Decimal.read.digits(neg, ds), 0n}}
423    case Frac{neg, ds, sc}:
424      Some{Decimal{Decimal.read.digits(neg, ds), sc}}
425    case ExpDigits{neg, ds, sc, eneg, e}:
426      Some{Decimal.read.shift(Decimal.read.digits(neg, ds), sc, eneg,
427        U32.to_nat(e))}
428    case _:
429      None{}
430
431# [+-]digits[.digits][(e|E)[+-]digits], a superset of JSON's number grammar
432# (it also takes a leading + and leading zeros). The scale is the number of
433# fraction digits less the exponent, floored at zero: "1.50" has scale 2,
434# "1.5e1" is 15, "25e-3" is 0.025.
435def Decimal.read(s: String) -> Maybe<&2, Decimal>:
436  Decimal.read.fin(Decimal.read.go(s, Begin{}))