1	import Base
2	import ./num.bend as N
3	import ./u64.bend as W
4	import ./w64.bend as X
5	import ./generic.bend as G
6	import ./natural.bend as M
7	
8	# Numeric instances for generic.bend (num.bend's Op and Test per type):
9	# U32 (Base), U64 (the two-limb U64 of u64.bend, fast arithmetic in
10	# w64.bend) and F32 (Base's float); F64 lives in f64.bend.
11	#
12	#   G.gcd(~U32, ~I.u32_op, ~I.u32_is, a, b)
13	#   G.gcd(~W.U64, ~I.u64_op, ~I.u64_is, a, b)
14	#   G.pow(~F32, ~I.f32_op, ~I.f32_is, x, k)
15	#
16	# Fixed widths are checked: generic.bend forms Add and Mul only next to their
17	# over-test and uses the result only if the test says it fits.
18	
19	# ---- U32 ----
20	
21	# a * b >= 2^32: the full product has a nonzero high word
22	def u32_mul_over(+a: U32, +b: U32) -> Bool:
23	  Bool.not(U32.is_zero(X.hi(X.mul32(a, b))))
24	
25	def u32_mulmod(+a: U32, +b: U32, +m: U32) -> U32:
26	  X.mod32(X.mul32(a, b), m)
27	
28	def u32_op(o: N.Op<U32>) -> U32:
29	  match o:
30	    case N.ZeroOp{}:
31	      0
32	    case N.One{}:
33	      1
34	    case N.Add{a, b}:
35	      U32.add(a, b)
36	    case N.Sub{a, b}:
37	      U32.sub(a, b)
38	    case N.Mul{a, b}:
39	      U32.mul(a, b)
40	    case N.Neg{a}:
41	      U32.sub(0, a)
42	    case N.Abs{a}:
43	      a
44	    case N.Quot{a, b}:
45	      U32.div(a, b)
46	    case N.Rem{a, b}:
47	      U32.mod(a, b)
48	    case N.Half{a}:
49	      U32.shr(a)
50	    case N.MulMod{a, b, m}:
51	      u32_mulmod(a, b, m)
52	    case N.Pow2{k}:
53	      X.pow2(k)
54	    case N.Sqrt{a}:
55	      X.isqrt32(a)
56	    case N.PowMod{a, e, m}:
57	      X.mpow32(a, e, m)
58	
59	    case N.GcdSmall{a, b}:
60	      0
61	def u32_add_over(+a: U32, +b: U32) -> Bool:
62	  U32.is_lt(U32.add(a, b), a)
63	
64	def u32_odd(+a: U32) -> Bool:
65	  U32.is_eq(U32.and(a, 1), 1)
66	
67	def u32_is(t: N.Test<U32>) -> Bool:
68	  match t:
69	    case N.Lt{a, b}:
70	      U32.is_lt(a, b)
71	    case N.AddOver{a, b}:
72	      u32_add_over(a, b)
73	    case N.MulOver{a, b}:
74	      u32_mul_over(a, b)
75	    case N.Odd{a}:
76	      u32_odd(a)
77	    case N.IsZero{a}:
78	      U32.is_zero(a)
79	    case N.FastDiv{}:
80	      True{}
81	    case N.Mont{m}:
82	      X.mont32_ok(m)
83	
84	# ---- U64 ----
85	    case N.Small{a, b}:
86	      False{}
87	
88	# 2^k for k < 64
89	def u64_pow2(+k: Nat) -> W.U64:
90	  X.w_pow2(k, Nat.is_lt(k, 32n))
91	
92	def u64_op(o: N.Op<W.U64>) -> W.U64:
93	  match o:
94	    case N.ZeroOp{}:
95	      W.U64{0, 0}
96	    case N.One{}:
97	      W.U64{1, 0}
98	    case N.Add{a, b}:
99	      X.add(a, b)
100	    case N.Sub{a, b}:
101	      X.sub(a, b)
102	    case N.Mul{a, b}:
103	      X.mul(a, b)
104	    case N.Neg{a}:
105	      X.sub(W.U64{0, 0}, a)
106	    case N.Abs{a}:
107	      a
108	    case N.Quot{a, b}:
109	      X.quot(a, b)
110	    case N.Rem{a, b}:
111	      X.rem(a, b)
112	    case N.Half{a}:
113	      X.half(a)
114	    case N.MulMod{a, b, m}:
115	      X.mulmod(a, b, m)
116	    case N.Pow2{k}:
117	      u64_pow2(k)
118	    case N.Sqrt{a}:
119	      X.isqrt(a)
120	    case N.PowMod{a, e, m}:
121	      X.mpow(a, e, m)
122	
123	    case N.GcdSmall{a, b}:
124	      X.of48(M.gcd(X.n48(a), X.n48(b)))
125	def u64_is(t: N.Test<W.U64>) -> Bool:
126	  match t:
127	    case N.Lt{a, b}:
128	      X.lt(a, b)
129	    case N.AddOver{a, b}:
130	      X.add_over(a, b)
131	    case N.MulOver{a, b}:
132	      X.mul_over(a, b)
133	    case N.Odd{a}:
134	      X.odd(a)
135	    case N.IsZero{a}:
136	      X.is_zero(a)
137	    case N.FastDiv{}:
138	      False{}
139	    case N.Mont{m}:
140	      X.mont_ok(m)
141	    case N.Small{a, b}:
142	      X.small2(a, b)
143	
144	# ---- F32 ----
145	
146	def f32_op(o: N.Op<F32>) -> F32:
147	  match o:
148	    case N.ZeroOp{}:
149	      0.0
150	    case N.One{}:
151	      1.0
152	    case N.Add{a, b}:
153	      F32.add(a, b)
154	    case N.Sub{a, b}:
155	      F32.sub(a, b)
156	    case N.Mul{a, b}:
157	      F32.mul(a, b)
158	    case N.Neg{a}:
159	      F32.neg(a)
160	    case N.Abs{a}:
161	      F32.abs(a)
162	    case N.Quot{a, b}:
163	      F32.div(a, b)
164	    case N.Rem{a, b}:
165	      F32.mod(a, b)
166	    case N.Half{a}:
167	      F32.mul(a, 0.5)
168	    case N.MulMod{a, b, m}:
169	      F32.mod(F32.mul(a, b), m)
170	    case N.Pow2{k}:
171	      F32.pow(2.0, F32.from_nat(k))
172	    case N.Sqrt{a}:
173	      F32.sqrt(a)
174	    case N.PowMod{a, e, m}:
175	      0.0
176	
177	    case N.GcdSmall{a, b}:
178	      0.0
179	def f32_is(t: N.Test<F32>) -> Bool:
180	  match t:
181	    case N.Lt{a, b}:
182	      F32.is_lt(a, b)
183	    case N.AddOver{a, b}:
184	      False{}
185	    case N.MulOver{a, b}:
186	      False{}
187	    case N.Odd{a}:
188	      False{}
189	    case N.IsZero{a}:
190	      F32.is_eq(a, 0.0)
191	    case N.FastDiv{}:
192	      True{}
193	    case N.Mont{m}:
194	      False{}
195	
196	    case N.Small{a, b}:
197	      False{}