1	import 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	
44	type NumError is Data:
45	  DivByZero{}
46	  BadDomain{}
47	  NoInverse{}
48	  Overflow{}
49	
50	type 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	
67	type 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}