src/math/num.bend
1import Base
2
3# The numeric interface of the generic math (generic.bend). A type T takes
4# part through two functions, passed as templates next to T:
5#
6# ~op: Op<T> -> T its arithmetic, one constructor per operation
7# ~test: Test<T> -> Bool its comparisons and overflow tests
8#
9# G.gcd(~U32, ~I.u32_op, ~I.u32_is, a, b)
10#
11# Templates are substituted at compile time and the match on the operation's
12# constructor is resolved there, so every call compiles to the instance's
13# native code (a record of functions would be called through closures at run
14# time, about 5x slower).
15#
16# Fixed widths are checked: Add, Sub and Mul are only formed after the
17# matching test (AddOver, Lt, MulOver) said the result fits. For floats the
18# over-tests are False and the operations are IEEE's.
19#
20# Zero, One constants
21# Add, Sub, Mul a + b, a - b (b <= a for unsigned), a * b
22# Neg, Abs -a (floats), |a|
23# Quot, Rem a / b, a mod b (unsigned, b != 0)
24# Half a / 2
25# MulMod a * b mod m for a, b < m (never overflows)
26# Pow2 2^k, for 2^k below the width
27# Sqrt the integer square root (instances may use hardware)
28# PowMod a^e mod m for a < m, only formed when Mont{m} holds
29# GcdSmall gcd(a, b), only formed when Small{a, b} holds
30# Lt, AddOver, MulOver, Odd, IsZero
31# FastDiv True when Quot/Rem are native machine divisions, so
32# gcd runs Euclid's algorithm; False (U64: division is
33# software long division) picks the binary gcd, which
34# only halves, subtracts and compares
35# Mont{m} True when the instance computes PowMod mod m itself
36# (U64: Montgomery multiplication for odd m in
37# [2^32, 2^63)); False keeps the generic MulMod loop
38# Small{a, b} True when the binary gcd should hand (a, b) to GcdSmall
39# (U64: both below 2^48, a at least 2^16: Euclid on Nat)
40#
41# Errors are values, as in natural.bend, with Overflow for results that do
42# not fit a fixed width (design reference section 2.6: checked results).
43
44type NumError is Data:
45 DivByZero{}
46 BadDomain{}
47 NoInverse{}
48 Overflow{}
49
50type Op<-T: Data> is Data:
51 ZeroOp{}
52 One{}
53 Add{a: T, b: T}
54 Sub{a: T, b: T}
55 Mul{a: T, b: T}
56 Neg{a: T}
57 Abs{a: T}
58 Quot{a: T, b: T}
59 Rem{a: T, b: T}
60 Half{a: T}
61 MulMod{a: T, b: T, m: T}
62 Pow2{k: Nat}
63 Sqrt{a: T}
64 PowMod{a: T, e: T, m: T}
65 GcdSmall{a: T, b: T}
66
67type Test<-T: Data> is Data:
68 Lt{a: T, b: T}
69 AddOver{a: T, b: T}
70 MulOver{a: T, b: T}
71 Odd{a: T}
72 IsZero{a: T}
73 FastDiv{}
74 Mont{m: T}
75 Small{a: T, b: T}