rational.bend

bend-kit-bignum@0.1.0.0 · 122 lines · 21 definitions

1# Exact rational numbers over BigInt, always in lowest terms.
2import Base
3import bend-kit-bignum@0.1.0.0/bigint.bend as Big
4import bend-kit-bignum@0.1.0.0/decimal.bend as Dec
5
6# num / den with den > 0 and gcd(num, den) = 1, so zero is 0/1 and equal
7# values are equal terms. Build one with make, from_bigint or from_decimal;
8# the raw constructor does not normalize.
9type Rational is Data:
10  Rational{num: Big.BigInt, den: Big.BigInt}
11
12def Rational.low(p: Big.BigInt & Big.BigInt) -> Rational:
13  (n, d) = p
14  Rational{n, d}
15
16# n / d for a nonzero d.
17def Rational.norm(n: Big.BigInt, d: Big.BigInt) -> Rational:
18  Rational.low(Dec.Decimal.lowest(n, d))
19
20def Rational.from_bigint(n: Big.BigInt) -> Rational:
21  Rational{n, Big.BigInt.one()}
22
23def Rational.make.if(z: Bool, n: Big.BigInt, d: Big.BigInt) ->
24  Maybe<&2, Rational>:
25  match z:
26    case True{}:
27      None{}
28    case False{}:
29      Some{Rational.norm(n, d)}
30
31# n / d in lowest terms, or None when d is zero.
32def Rational.make(n: Big.BigInt, +d: Big.BigInt) -> Maybe<&2, Rational>:
33  Rational.make.if(Big.BigInt.is_zero(d), n, d)
34
35def Rational.from_decimal(d: Dec.Decimal) -> Rational:
36  match d:
37    case Dec.Decimal{u, s}:
38      Rational.norm(u, Dec.Decimal.pow10(s))
39
40# The exact decimal, or None when it repeats (den has a factor besides 2, 5).
41def Rational.to_decimal(r: Rational) -> Maybe<&2, Dec.Decimal>:
42  match r:
43    case Rational{n, d}:
44      Dec.Decimal.from_fraction(n, d)
45
46def Rational.neg(r: Rational) -> Rational:
47  match r:
48    case Rational{n, d}:
49      Rational{Big.BigInt.neg(n), d}
50
51def Rational.is_zero(r: Rational) -> Bool:
52  match r:
53    case Rational{n, d}:
54      Big.BigInt.is_zero(n)
55
56def Rational.add(a: Rational, b: Rational) -> Rational:
57  match a b:
58    case Rational{an, +ad} Rational{bn, +bd}:
59      Rational.norm(Big.BigInt.add(Big.BigInt.mul(an, bd),
60        Big.BigInt.mul(bn, ad)), Big.BigInt.mul(ad, bd))
61
62def Rational.sub(a: Rational, b: Rational) -> Rational:
63  Rational.add(a, Rational.neg(b))
64
65def Rational.mul(a: Rational, b: Rational) -> Rational:
66  match a b:
67    case Rational{an, ad} Rational{bn, bd}:
68      Rational.norm(Big.BigInt.mul(an, bn), Big.BigInt.mul(ad, bd))
69
70# a / b, or None when b is zero.
71def Rational.div(a: Rational, b: Rational) -> Maybe<&2, Rational>:
72  match a b:
73    case Rational{an, ad} Rational{bn, bd}:
74      Rational.make(Big.BigInt.mul(an, bd), Big.BigInt.mul(ad, bn))
75
76# Denominators are positive, so cross-multiplying keeps the order.
77def Rational.cmp(a: Rational, b: Rational) -> Cmp:
78  match a b:
79    case Rational{an, ad} Rational{bn, bd}:
80      Big.BigInt.cmp(Big.BigInt.mul(an, bd), Big.BigInt.mul(bn, ad))
81
82def Rational.show.if(whole: Bool, n: Big.BigInt, d: Big.BigInt) -> String:
83  match whole:
84    case True{}:
85      Big.BigInt.show(n)
86    case False{}:
87      Big.BigInt.show(n) ++ "/" ++ Big.BigInt.show(d)
88
89# "n/d", or "n" when the denominator is 1.
90def Rational.show(r: Rational) -> String:
91  match r:
92    case Rational{n, +d}:
93      Rational.show.if(Dec.Decimal.is_one(d), n, d)
94
95def Rational.read.frac(a: Maybe<&2, Big.BigInt>, b: Maybe<&2, Big.BigInt>) ->
96  Maybe<&2, Rational>:
97  match a b:
98    case Some{n} Some{d}:
99      Rational.make(n, d)
100    case _ _:
101      None{}
102
103def Rational.read.dec(m: Maybe<&2, Dec.Decimal>) -> Maybe<&2, Rational>:
104  match m:
105    case Some{d}:
106      Some{Rational.from_decimal(d)}
107    case None{}:
108      None{}
109
110def Rational.read.parts(ps: List<&2, String>) -> Maybe<&2, Rational>:
111  match ps:
112    case Con{a, Nil{}}:
113      Rational.read.dec(Dec.Decimal.read(a))
114    case Con{a, Con{b, Nil{}}}:
115      Rational.read.frac(Big.BigInt.read(a), Big.BigInt.read(b))
116    case _:
117      None{}
118
119# "n/d" with BigInt sides (normalized; a zero d is None), or any number
120# Decimal.read takes, such as "-1.25" or "3e-2".
121def Rational.read(s: String) -> Maybe<&2, Rational>:
122  Rational.read.parts(String.split(s, '/'))