HCoop / hcoop / debian / mlton.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Import Upstream version 20180207
[hcoop/debian/mlton.git] / benchmark / tests / smith-normal-form.sml
CommitLineData
7f918cf1
CE		 1(* Written by Henry Cejtin (henry@sourcelight.com). *)
2signature MATRIX =
3 sig
4 type 'entry matrix
5 val make: int * int * (int * int -> 'entry) -> 'entry matrix
6 val height: 'entry matrix -> int
7 val width: 'entry matrix -> int
8 val fetch: 'entry matrix * int * int -> 'entry
9 val fetchRow: 'entry matrix * int -> int -> 'entry
10 val fetchCol: 'entry matrix * int -> int -> 'entry
11 val store: 'entry matrix * int * int * 'entry -> unit
12 val storeRow: 'entry matrix * int -> int * 'entry -> unit
13 val storeCol: 'entry matrix * int -> int * 'entry -> unit
14 val rowSwap: 'entry matrix * int * int -> unit
15 val colSwap: 'entry matrix * int * int -> unit
16 val rowOp: 'entry matrix * int * int * ('entry * 'entry -> 'entry) -> unit
17 val colOp: 'entry matrix * int * int * ('entry * 'entry -> 'entry) -> unit
18 val copy: 'entry matrix -> 'entry matrix
19 val map: 'entry1 matrix * ('entry1 -> 'entry2) -> 'entry2 matrix
20 val toString: 'entry matrix * ('entry -> string) -> string
21 end
22
23structure Matrix:> MATRIX =
24 struct
25 type 'entry matrix = int * int * 'entry array
26
27 exception sizeError
28
29 exception index
30
31 exception foldError
32
33 fun make (height: int, width: int, generator: int * int -> 'entry)
34 : 'entry matrix =
35 if height < 0 orelse width < 0
36 then raise sizeError
37 else (height,
38 width,
39 Array.tabulate (height*width,
40 fn z => generator (z div width,
41 z mod width)))
42
43 fun height (height, _, _) = height
44
45 fun width (width, _, _) = width
46
47 fun fetch ((height, width, mat), row, col) =
48 if 0 <= row
49 andalso row < height
50 andalso 0 <= col
51 andalso col < width
52 then Array.sub (mat, col + width*row)
53 else raise index
54
55 fun fetchRow ((height, width, mat), row) =
56 if 0 <= row andalso row < height
57 then let val offset = width * row
58 in fn col =>
59 if 0 <= col andalso col < width
60 then Array.sub (mat, col + offset)
61 else raise index
62 end
63 else raise index
64
65 fun fetchCol ((height, width, mat), col) =
66 if 0 <= col andalso col < width
67 then fn row =>
68 if 0 <= row andalso row < height
69 then Array.sub (mat, col + width*row)
70 else raise index
71 else raise index
72
73 fun store ((height, width, mat), row, col, entry) =
74 if 0 <= row
75 andalso row < height
76 andalso 0 <= col
77 andalso col < width
78 then Array.update (mat, col + width*row, entry)
79 else raise index
80
81 fun storeRow ((height, width, mat), row) =
82 if 0 <= row andalso row < height
83 then let val offset = width * row
84 in fn (col, entry) =>
85 if 0 <= col andalso col < width
86 then Array.update (mat, col + offset, entry)
87 else raise index
88 end
89 else raise index
90
91 fun storeCol ((height, width, mat), col) =
92 if 0 <= col andalso col < width
93 then fn (row, entry) =>
94 if 0 <= row andalso row < height
95 then Array.update (mat, col + width*row, entry)
96 else raise index
97 else raise index
98
99 fun swapLoop (from1: int -> 'entry,
100 to1: int * 'entry -> unit,
101 from2: int -> 'entry,
102 to2: int * 'entry -> unit,
103 limit: int): unit =
104 let fun loop (i: int): unit =
105 if i = limit
106 then ()
107 else let val tmp = from1 i
108 in to1 (i, from2 i);
109 to2 (i, tmp);
110 loop (i + 1)
111 end
112 in loop 0
113 end
114
115 fun rowSwap (mat as (height, width, _), row1, row2): unit =
116 if 0 <= row1 andalso row1 < height
117 andalso 0 <= row2 andalso row2 < height
118 then if row1 = row2
119 then ()
120 else swapLoop (fetchRow (mat, row1),
121 storeRow (mat, row1),
122 fetchRow (mat, row2),
123 storeRow (mat, row2),
124 width)
125 else raise index
126
127 fun colSwap (mat as (height, width, _), col1, col2): unit =
128 if 0 <= col1 andalso col1 < width
129 andalso 0 <= col2 andalso col2 < width
130 then if col1 = col2
131 then ()
132 else swapLoop (fetchCol (mat, col1),
133 storeCol (mat, col1),
134 fetchCol (mat, col2),
135 storeCol (mat, col2),
136 height)
137 else raise index
138
139 fun opLoop (from1: int -> 'entry,
140 from2: int -> 'entry,
141 to2: int * 'entry -> unit,
142 limit: int,
143 f: 'entry * 'entry -> 'entry): unit =
144 let fun loop (i: int): unit =
145 if i = limit
146 then ()
147 else (
148 to2 (i,
149 f (from1 i, from2 i));
150 loop (i + 1))
151 in loop 0
152 end
153
154 fun rowOp (mat as (height, width, _),
155 row1,
156 row2,
157 f: 'entry * 'entry -> 'entry): unit =
158 if 0 <= row1 andalso row1 < height
159 andalso 0 <= row2 andalso row2 < height
160 andalso row1 <> row2
161 then opLoop (fetchRow (mat, row1),
162 fetchRow (mat, row2),
163 storeRow (mat, row2),
164 width,
165 f)
166 else raise index
167
168 fun colOp (mat as (height, width, _),
169 col1,
170 col2,
171 f: 'entry * 'entry -> 'entry): unit =
172 if 0 <= col1 andalso col1 < width
173 andalso 0 <= col2 andalso col2 < width
174 andalso col1 <> col2
175 then opLoop (fetchCol (mat, col1),
176 fetchCol (mat, col2),
177 storeCol (mat, col2),
178 height,
179 f)
180 else raise index
181
182 fun copy ((height, width, mat)) =
183 (height,
184 width,
185 Array.tabulate (Array.length mat,
186 fn i => Array.sub (mat, i)))
187
188 fun map ((height, width, mat: 'entry1 Array.array),
189 f: 'entry1 -> 'entry2)
190 : 'entry2 matrix =
191 (height,
192 width,
193 Array.tabulate (Array.length mat,
194 fn i => f (Array.sub (mat, i))))
195
196 (* Natural fold a range of integers in reverse. *)
197 fun naturalFold (limit: int,
198 state: 'state,
199 folder: int * 'state -> 'state): 'state =
200 let fun loop (i: int, state: 'state) =
201 if i = 0
202 then state
203 else loop (i - 1, folder (i - 1, state))
204 in if limit < 0
205 then raise foldError
206 else loop (limit, state)
207 end
208
209
210 local val blank8 = Byte.charToByte #" "
211
212 fun makeBlanks size =
213 let val blanks = Word8Vector.tabulate (size,
214 fn _ => blank8)
215 in Byte.bytesToString blanks
216 end
217
218 in fun toString (mat: 'entry matrix, f: 'entry -> string): string =
219 let val mat as (height, width, _) = map (mat, f)
220 fun maxSize from (i, width) = Int.max (String.size (from i),
221 width)
222 fun colWidth col = naturalFold (height,
223 0,
224 maxSize (fetchCol (mat,
225 col)))
226 val widths = Vector.tabulate (width, colWidth)
227 fun doRow (row: int, ac: string list): string list =
228 let val from = fetchRow (mat, row)
229 fun loop (col: int, ac: string list) =
230 let val next = from col
231 val ac = next::ac
232 val s = String.size next
233 val pad = Vector.sub (widths, col) - s
234 val ac = if pad <= 0
235 then ac
236 else (makeBlanks pad)::ac
237 in if col = 0
238 then ac
239 else loop (col - 1,
240 " "::ac)
241 end
242 val ac = "\n"::ac
243 in if width = 0
244 then ac
245 else loop (width - 1, ac)
246 end
247 val pieces = naturalFold (height,
248 [],
249 doRow)
250 in String.concat pieces
251 end
252 end
253 end
254
255val zero = IntInf.fromInt 0
256
257fun smaller (a: IntInf.int, b: IntInf.int): bool =
258 (not (a = zero))
259 andalso (b = zero orelse IntInf.< (IntInf.abs a , IntInf.abs b))
260
261fun smithNormalForm (mat: IntInf.int Matrix.matrix): IntInf.int Matrix.matrix =
262 let val height = Matrix.height mat
263 val width = Matrix.width mat
264 val mat = Matrix.copy mat
265 val range = Int.min (width, height)
266 fun dd pos =
267 let val matCol = Matrix.fetchCol (mat, pos)
268 val matRow = Matrix.fetchRow (mat, pos)
269 val _ = print ("dd: pos = " ^ (Int.toString pos) ^ "\n")
270 fun swapRowLoop (best, bestRow, bestCol, row) =
271 if row >= height
272 then (Matrix.rowSwap (mat, pos, bestRow);
273 Matrix.colSwap (mat, pos, bestCol))
274 else let val matRow = Matrix.fetchRow (mat, row)
275 fun swapColLoop (best, bestRow, bestCol, col) =
276 if col >= width
277 then swapRowLoop (best, bestRow, bestCol, row + 1)
278 else let val next = matRow col
279 in if smaller (next, best)
280 then swapColLoop (next, row, col, col + 1)
281 else swapColLoop (best, bestRow, bestCol, col + 1)
282 end
283 in swapColLoop (best, bestRow, bestCol, pos)
284 end
285 fun rowLoop row =
286 if row < height
287 then if (matCol row) = zero
288 then rowLoop (row + 1)
289 else (Matrix.rowOp (mat,
290 pos,
291 row,
292 let val x = IntInf.~ (IntInf.quot(matCol row, matCol pos))
293 in fn (lhs, rhs) => IntInf.+ (IntInf.* (lhs, x), rhs)
294 end);
295 if (matCol row) = zero
296 then rowLoop (row + 1)
297 else hitPosAgain ())
298 else let fun colLoop col =
299 if col < width
300 then if (matRow col) = zero
301 then colLoop (col + 1)
302 else (Matrix.colOp (mat,
303 pos,
304 col,
305 let val x = IntInf.~ (IntInf.quot (matRow col, matRow pos))
306 in fn (lhs, rhs) => IntInf.+ (IntInf.* (lhs, x), rhs)
307 end);
308 if (matRow col) = zero
309 then colLoop (col + 1)
310 else hitPosAgain ())
311 else ()
312 in colLoop (pos + 1)
313 end
314 and hitPosAgain () = (swapRowLoop (zero, pos, pos, pos);
315 rowLoop (pos + 1))
316 in hitPosAgain ()
317 end
318 fun loop pos =
319 if pos = range
320 then mat
321 else (dd pos;
322 loop (pos + 1))
323 in loop 0
324 end
325
326val table = [[ 8, ~3, 1, 3, 6, 9, ~2, 4, ~9, ~9, 2, 3, 8, ~1, 3, ~5, 4, ~3, ~5, ~6, 8, 1, 4, ~5, 7, ~4, ~4, ~7, 7, 1, 4, ~3, 8, 4, ~4, ~8, 5, ~9, 3, ~4, 1, 9, ~8, ~6, ~2, 8, ~9, ~5, ~3, ~3],
327 [ 0, 8, ~6, ~2, ~3, 4, 5, ~2, 7, ~7, ~6, ~7, ~3, ~4, 9, 7, ~3, 3, 0, 3, 3, ~8, ~8, 2, 3, 8, 3, ~2, ~4, 3, ~6, ~6, ~2, 6, 5, ~1, ~3, 1, 8, ~8, 2, 1, ~7, ~7, ~7, ~3, ~6, 6, ~4, ~9],
328 [ 0, ~5, 8, ~9, 2, 4, 2, 7, ~4, 9, ~3, 6, ~2, 3, ~3, 0, ~9, 5, 8, ~1, 2, ~8, 3, 4, ~6, 5, ~6, ~5, ~8, 0, ~5, 3, ~2, ~5, 8, 7, ~1, 1, ~1, 7, 6, 3, 6, 5, 6, 8, 7, 9, 7, ~3],
329 [ 5, 4, 7, 2, 3, ~9, 7, ~7, 3, ~8, 7, 5, 5, ~2, ~6, ~3, 6, 5, 3, ~1, ~1, 4, 5, ~5, 5, 9, 9, 3, 8, ~3, ~1, 9, ~9, 6, ~7, 7, 4, 6, ~8, ~9, 0, ~3, ~2, ~7, 1, ~2, ~6, 7, 7, 7],
330 [ 2, 9, 9, 3, ~4, 0, 9, 2, 5, 3, ~5, ~3, ~1, 1, 8, ~6, 2, ~4, ~8, ~7, ~8, 4, 5, 8, ~1, ~1, 7, 2, 5, 5, ~4, ~7, ~3, ~7, 6, ~4, ~5, ~8, ~5, ~9, ~8, 5, ~5, ~5, 0, 8, 8, 6, 4, ~1],
331 [ 5, 5, 1, ~7, 3, ~5, 4, 9, 3, 4, 4, ~5, 7, ~1, 7, 4, ~7, 7, ~7, ~2, 9, ~9, 0, ~4, ~4, 0, 2, 6, 3, ~1, 6, 6, 8, ~6, ~4, ~9, 3, ~2, ~5, 5, ~3, 2, ~1, ~6, 9, 3, ~3, ~8, ~9, 7],
332 [ 7, 1, 2, 7, 6, 5, ~6, ~3, ~4, ~8, 0, 9, 6, 1, 2, ~5, 4, 4, 4, ~6, ~7, ~9, ~6, 2, ~4, 5, ~2, 1, 0, 1, ~8, 7, ~7, ~5, 4, 1, ~5, 4, ~4, ~2, ~3, 1, 1, 3, 4, ~4, ~5, 9, 8, ~2],
333 [ 6, 2, ~1, ~8, 4, ~7, 7, ~3, ~2, ~5, 3, 0, 3, ~9, 3, 3, 9, ~1, 4, 8, ~9, 6, ~5, 9, 5, ~1, ~1, ~9, 7, ~2, 3, 9, 8, 9, 2, 7, 7, 6, ~1, ~1, ~2, ~2, ~7, 3, ~6, 0, ~9, 4, 3, 7],
334 [ 0, ~6, ~3, ~7, ~1, 5, ~2, 8, ~5, ~3, ~8, 7, ~2, ~2, 0, ~8, 4, 8, 9, ~5, ~4, ~8, ~1, 7, 1, 1, 6, ~9, ~4, 0, 8, 4, 3, ~7, 6, 0, 1, 8, 6, ~1, ~1, ~7, 9, ~9, ~5, ~2, ~2, ~1, 1, 0],
335 [~4, 9, 6, ~3, ~2, ~6, ~3, 4, 8, ~8, 1, ~5, 9, 7, 9, 7, ~9, ~6, 6, 1, ~3, 3, ~3, ~7, 1, 7, ~7, 0, ~2, 7, ~4, ~6, 0, 1, ~3, ~5, ~9, ~7, 8, 4, 9, ~8, ~8, ~7, ~6, 7, 6, ~3, ~8, 5],
336 [ 6, 7, ~5, ~9, 6, 1, 8, 4, ~2, 7, ~7, ~1, ~9, 1, ~6, ~5, 4, 9, 6, 0, ~8, ~3, 1, ~3, 8, ~3, 2, 9, ~3, ~9, ~1, ~3, 4, 3, 2, ~9, ~5, ~3, 8, ~4, 8, 5, ~4, 7, 6, ~8, 7, 6, ~5, 5],
337 [ 1, 7, ~8, ~9, ~7, ~3, 8, 9, ~7, ~1, ~7, 4, 0, 0, 1, ~5, 9, ~8, ~1, ~2, 3, 5, 9, ~9, 5, 4, ~9, 1, ~4, ~2, 3, ~4, 8, ~6, ~4, ~8, ~5, ~5, 4, ~2, ~4, ~1, ~9, ~5, 2, ~9, 2, ~9, ~2, ~3],
338 [~5, ~4, ~4, 9, 2, 7, ~2, 6, 7, 2, ~9, 4, 2, 7, 8, ~9, 2, 5, 3, 9, 6, 3, 0, ~7, ~6, ~7, 6, ~2, 9, ~3, ~6, 9, ~9, 2, 2, ~6, ~1, 4, ~3, 3, 0, 6, ~3, 4, 9, 9, ~6, 5, 5, ~5],
339 [ 5, ~7, 8, ~4, 8, 8, ~4, ~9, 6, 0, ~3, 6, 0, 8, 8, ~6, ~2, 5, 4, ~1, ~8, 1, ~3, ~1, 2, 3, ~9, ~9, ~5, 1, 8, ~5, ~3, 0, ~4, ~9, 0, ~6, 3, ~1, ~7, 0, 8, 9, ~6, ~1, ~9, 1, ~6, 2],
340 [ 7, ~5, ~1, 5, ~2, 7, 0, ~7, ~1, 8, 8, ~3, 9, ~5, 7, ~8, ~8, ~4, 3, 2, ~1, 8, ~2, 1, 2, 5, 0, ~6, 7, 3, 3, 7, ~5, 5, ~1, 1, 0, ~8, 1, 0, 0, ~4, 6, 9, ~5, ~6, 3, ~5, 8, 5],
341 [~4, ~2, 3, ~3, ~1, 2, ~2, ~1, ~9, ~5, 1, 0, 0, 2, 9, ~3, ~9, 2, 9, 3, 8, ~3, 4, 8, 8, 3, ~3, ~1, ~4, 4, ~6, ~9, 5, ~2, 1, 3, ~7, ~5, ~6, ~5, ~8, 4, ~8, ~3, 5, 0, 7, ~9, 6, 2],
342 [ 5, 1, 4, ~3, ~1, ~9, 5, ~8, ~8, 6, 1, 1, ~2, 7, 5, 6, ~4, 2, ~7, 0, ~7, ~3, ~5, 9, 3, 4, ~6, 8, ~4, 3, 6, 0, 2, 3, ~6, 3, 9, 4, 1, ~4, 6, ~5, ~7, 0, ~1, ~8, ~3, ~9, 9, 7],
343 [ 2, ~6, ~1, 8, 4, ~3, ~1, ~6, ~2, ~8, ~2, ~1, ~1, ~5, ~9, ~8, 9, ~9, 5, 1, 9, ~1, ~6, 9, ~7, 2, 8, ~7, 4, ~9, 7, 6, ~2, 1, ~2, ~7, 8, 0, 5, 0, ~5, ~7, ~6, 0, 4, 0, 3, ~8, 5, 4],
344 [~2, 9, ~9, ~6, 1, ~8, 8, 4, ~6, 8, 1, ~3, ~7, 8, ~5, 2, ~8, 1, 3, ~2, 6, 6, 6, 1, 0, 0, ~7, 7, ~3, ~3, 0, ~4, 3, ~7, ~6, 7, 5, 9, ~5, 7, ~8, 2, 3, ~8, ~7, 6, ~5, ~5, ~8, ~9],
345 [~7, ~4, 4, 1, ~1, ~3, ~8, 3, 7, 9, 8, 3, 0, 4, 4, ~1, ~5, 4, 2, 2, 0, 6, ~6, 2, ~9, 8, ~9, 3, ~2, 2, 6, 6, 1, 7, 1, 0, ~8, 2, 3, ~3, 8, 9, 5, 5, ~6, 4, ~7, ~4, ~2, ~3],
346 [~5, 8, 6, 1, ~6, ~6, 6, 1, 1, ~3, ~9, ~6, 2, ~7, 2, ~1, 6, ~6, 0, 2, ~7, 8, ~8, 4, 9, ~3, 9, ~7, ~9, ~6, ~4, ~4, ~5, 8, 2, ~5, ~4, ~3, 5, 2, 1, ~3, ~3, ~7, ~9, 3, 7, ~7, 3, ~8],
347 [~4, ~7, ~2, 2, ~4, ~2, 6, ~3, ~1, ~4, 0, ~5, 9, 7, ~6, ~9, 7, ~9, ~6, 2, ~3, 1, 5, ~9, 4, ~5, 4, ~9, 1, ~2, ~2, 4, 0, 4, ~8, ~8, 3, ~1, ~5, ~4, ~9, ~7, 7, 6, 3, ~9, 6, 4, ~4, ~7],
348 [~9, 6, 6, ~5, ~1, ~7, 4, ~9, 4, ~1, 6, ~4, 7, 2, 8, 7, 3, 1, ~7, 7, 7, 9, 8, ~9, 7, 2, 1, 2, ~8, 4, 5, 6, 7, 2, ~7, 6, 8, 4, ~9, 7, ~5, 6, 9, ~1, 9, 2, 0, 9, 3, 6],
349 [ 4, ~3, 8, 0, ~2, ~2, 2, ~3, 8, 3, 1, ~8, ~5, ~2, 5, 6, 8, 0, ~3, 4, ~2, 4, ~9, ~5, 7, 6, ~4, ~7, 2, 4, ~3, ~8, ~9, 9, 8, ~9, 3, ~7, 4, ~7, ~5, 4, 9, 3, ~6, ~3, ~7, 4, 2, ~2],
350 [~8, ~8, 6, ~2, ~6, 8, ~3, 3, ~1, ~7, 1, 9, 1, 7, ~6, 8, ~2, ~9, ~1, 3, ~4, 7, 8, ~1, 9, ~9, 6, ~3, 5, 0, 2, 5, ~1, ~6, ~6, 1, 8, 6, ~3, ~9, ~1, 9, ~2, 9, ~8, ~7, ~3, 6, ~3, ~3],
351 [ 5, ~2, 3, 0, ~9, ~8, ~6, 1, 8, 0, 1, 2, ~8, ~2, 0, ~9, ~8, 0, 5, ~3, ~4, 5, 6, ~2, ~5, 0, ~9, 9, ~9, ~5, 9, 9, ~5, ~2, 4, 3, 8, ~8, ~7, 5, ~3, ~2, 2, 3, 9, 7, ~1, 0, 4, ~1],
352 [~4, 5, ~5, 7, 8, 9, 7, ~3, 1, 9, ~7, ~1, 8, ~5, ~1, 2, ~8, 1, 0, 9, ~8, ~1, 6, ~1, 9, ~8, 7, 4, ~8, 7, 0, ~6, 2, 3, 7, 4, ~3, ~5, 9, ~3, 0, 6, ~9, 2, 4, ~8, 6, ~7, 9, 1],
353 [ 7, 0, ~9, 6, 8, 2, 2, 5, ~6, ~6, 9, ~5, 9, 2, 2, ~8, 0, ~6, ~9, ~6, ~4, ~9, 8, ~2, 9, 7, ~5, ~1, 7, 2, ~7, 7, ~1, ~3, 6, 6, 1, ~4, 0, ~1, ~6, ~5, 6, ~7, ~3, ~2, 8, 2, ~9, 8],
354 [ 8, ~7, ~9, ~6, 9, ~7, ~7, 6, ~8, 9, 5, ~4, 1, ~7, ~8, ~6, ~3, 8, ~8, 1, ~8, 6, 9, ~3, ~7, 7, 1, 6, 1, 0, 8, ~5, ~8, 8, ~9, 0, 4, 4, 3, ~4, 6, ~3, ~9, 0, 4, ~4, ~5, ~9, ~5, ~8],
355 [~3, ~2, 8, 1, ~1, ~1, ~4, 3, 7, ~2, ~9, 9, ~8, ~9, 6, ~4, 7, ~1, ~5, ~3, ~9, 0, ~3, 0, 7, 9, 1, ~2, 7, ~9, ~6, 3, 3, ~4, ~7, ~3, ~4, ~8, ~2, ~3, ~9, ~2, ~6, 3, ~6, ~4, 7, ~5, ~8, ~1],
356 [~9, ~9, ~2, ~9, ~9, 9, 6, 6, 7, 5, ~1, ~2, 1, 5, 2, ~3, ~4, 1, ~6, 0, ~3, ~9, ~1, 7, 0, ~9, 5, ~2, ~2, 5, 3, 4, ~1, 6, ~6, 3, ~6, 7, ~1, 5, ~8, ~4, ~2, ~2, ~6, ~5, ~6, 3, ~1, 4],
357 [ 7, 7, 8, 7, 6, 1, ~2, 5, ~6, 9, 4, 8, 5, 0, ~4, ~2, ~2, ~5, ~2, ~6, 9, ~8, ~2, ~5, ~9, 3, ~6, ~3, ~4, ~5, ~2, 6, 1, 6, ~5, 0, ~3, ~2, 4, ~6, 1, 6, ~1, 3, ~9, 2, ~3, 1, 5, ~6],
358 [ 6, 4, ~7, 3, ~7, 9, 1, ~7, ~8, 0, ~6, 8, 4, 1, 9, 6, 8, 3, 0, 9, 0, 4, 9, ~7, ~7, 1, 5, 1, ~5, 6, 9, 2, 4, 1, ~9, 8, 4, 5, 8, 3, 2, ~9, ~6, ~9, 9, ~9, 7, ~6, ~4, 3],
359 [~3, ~9, ~4, 2, 3, 9, ~9, 8, ~9, 9, ~4, ~9, ~5, 5, 0, 7, 3, ~5, ~8, 2, ~3, 0, ~9, ~3, 1, 9, 4, 5, ~1, 8, 0, ~4, ~2, 9, ~4, ~1, 3, 5, 9, ~1, 1, 4, ~8, ~2, ~3, 5, 1, 5, ~6, 7],
360 [ 9, ~3, 2, ~9, 3, 4, 0, 7, ~5, 9, 0, ~6, 7, ~2, 3, ~7, 2, ~5, ~2, 6, 3, ~9, ~5, ~9, 5, 2, ~5, ~3, 8, ~5, 6, 2, 9, ~7, ~7, ~7, ~6, 9, ~3, 6, 0, 6, ~6, ~9, 4, ~3, ~9, 0, ~4, ~9],
361 [~4, ~8, 8, ~7, 7, 0, ~6, ~6, 8, ~9, ~4, 5, ~3, ~1, 7, ~5, ~6, ~1, 8, 6, ~2, 1, ~1, 5, ~9, 1, ~1, ~7, ~6, ~6, ~6, ~4, 6, 3, ~5, ~5, ~6, 2, 3, ~6, ~8, ~3, 8, ~2, ~5, ~4, ~3, 1, 4, ~4],
362 [ 4, ~6, 2, 6, 2, ~8, 8, 5, 8, ~2, 0, ~6, ~1, ~6, ~2, 2, 6, ~9, ~7, ~6, ~4, ~4, ~7, ~2, 8, 6, 3, ~7, ~6, 8, 2, 3, 4, 5, 3, 4, ~6, 8, 8, ~1, 4, ~5, 6, 2, 8, ~3, ~9, ~2, 6, 7],
363 [ 3, ~4, 0, ~3, ~5, 0, ~2, ~6, ~2, 8, 5, ~9, ~4, ~8, ~6, 0, 8, 9, 1, ~2, 8, 2, ~2, 8, 9, 3, 3, 5, ~9, ~3, ~2, 7, 2, 9, 0, 4, 8, ~9, 0, ~6, 9, ~9, 9, ~4, 8, ~8, ~8, 2, ~3, 2],
364 [~1, 3, ~9, ~8, ~7, 6, ~6, 3, 0, 5, ~5, 1, 2, ~2, ~3, 7, 7, 3, ~4, ~2, ~9, ~5, ~1, 9, 6, 8, 2, 8, 7, ~3, 4, 6, 6, 0, ~2, 2, ~7, ~7, 6, ~3, 8, 2, 1, 0, 8, ~1, 3, 9, 8, 6],
365 [ 1, ~2, ~3, 6, 5, 5, ~6, ~4, ~5, 1, 1, 6, ~7, ~4, ~3, 4, 4, ~8, ~9, 7, ~2, ~3, ~7, ~2, 1, 2, 0, 8, ~6, ~5, ~5, 7, 8, 5, ~2, 3, 9, 0, 5, 1, 3, ~4, ~6, 1, 4, ~9, ~2, 5, 4, 3],
366 [ 3, 3, 9, ~2, 6, 9, 4, 9, 4, ~8, 5, ~1, 3, ~2, 1, ~7, ~3, 2, 2, 0, ~3, 3, 8, 2, 0, ~5, 7, 1, 4, ~8, 8, ~9, ~1, 1, ~9, ~4, 5, 2, 2, 8, 6, 1, 6, ~2, 2, 7, 1, ~6, ~1, ~1],
367 [ 4, ~2, 4, ~1, ~5, ~1, 5, ~2, 3, ~4, ~5, 0, 2, ~4, 6, 4, ~3, 2, 2, 5, ~6, ~7, ~9, ~1, ~9, ~9, 6, 0, 6, 5, 9, ~1, 3, ~3, ~8, 8, ~8, 8, 4, 5, ~1, ~5, 1, 0, 3, ~2, 5, 6, 6, 5],
368 [~4, 9, 6, 8, ~9, 5, 5, ~3, ~7, 7, 6, 8, ~8, 0, 4, ~1, 9, 5, ~7, 0, ~1, ~2, 3, 6, 0, 4, ~3, 1, 4, 6, 4, 0, 5, ~1, 7, ~7, ~6, ~8, ~3, ~6, 7, ~1, ~3, ~2, ~3, ~5, 3, 1, ~8, ~9],
369 [~6, 4, ~5, 9, 9, ~7, ~1, ~8, ~4, 2, ~6, 0, ~6, ~6, 7, 6, 0, 1, 7, ~7, 0, ~4, ~6, ~8, ~9, 5, ~6, ~9, 2, ~7, ~2, ~6, 9, 4, ~5, 0, 4, ~4, ~5, 6, 9, 1, ~6, ~5, 3, ~1, 7, ~7, ~6, 7],
370 [~8, 7, 7, ~6, 7, ~4, 8, 0, ~9, ~8, ~3, 7, ~3, 3, 8, ~7, ~2, ~7, 5, 5, ~5, 4, 6, 2, 4, 1, 4, ~9, ~3, 8, 8, ~9, ~4, ~2, 1, ~3, 1, 3, 9, ~5, ~8, ~2, 7, 8, 9, 2, 0, 1, ~9, 6],
371 [~7, 1, ~9, 5, ~5, ~5, 7, 6, ~5, ~9, ~6, ~8, ~6, 9, 7, 9, 0, ~5, 7, 7, ~6, 4, 5, ~9, ~1, ~2, ~7, 3, ~5, ~2, ~5, 5, ~3, ~4, ~2, ~8, 2, ~8, 0, ~8, 0, ~8, 9, 8, ~5, ~5, 1, 3, 5, ~4],
372 [~8, ~8, 0, ~5, ~8, ~6, 3, ~6, ~4, 6, 1, ~5, ~6, ~8, ~4, ~6, ~2, ~6, 6, ~4, 8, 8, 4, ~5, ~1, 0, 9, ~8, ~3, ~1, ~8, 7, ~3, 0, ~7, 1, ~7, ~1, ~7, 3, ~7, 3, ~4, ~8, 8, ~7, ~9, ~8, 3, 2],
373 [ 3, 6, 8, ~9, 7, 1, ~9, 9, 3, 8, 6, 4, ~2, 1, ~8, 4, ~7, ~4, ~3, 3, ~5, ~6, ~7, ~2, 0, ~4, 5, 2, 5, 6, 3, ~8, 2, ~5, ~7, 6, 8, ~2, ~5, ~4, 9, 9, 2, ~2, ~2, 7, 4, 4, ~2, 3],
374 [ 6, 6, ~5, ~2, ~8, ~2, ~9, 0, 2, 4, ~6, ~9, 9, 0, ~8, ~3, ~1, ~2, ~1, 6, 8, 2, ~9, 5, ~2, 1, 7, ~6, 5, 1, ~1, 4, ~4, ~7, ~6, ~3, ~8, 2, 2, 5, 5, ~6, 5, 3, 3, 7, 4, 7, ~3, ~9],
375 [~9, 6, ~4, 1, 3, ~8, ~8, ~8, ~1, 5, 1, 1, ~1, 6, 5, 1, ~1, 5, ~8, 8, ~7, ~5, ~1, ~1, 6, ~8, ~3, ~1, ~2, ~6, ~5, ~5, ~6, 0, 2, 2, 7, ~1, ~5, ~7, ~1, ~3, 7, 6, 0, 2, 4, ~5, 0, ~4]]
376
377fun f (x, y) = List.nth (List.nth (table, x), y)
378fun show m = print (Matrix.toString (m, IntInf.toString))
379structure Main =
380 struct
381 fun snf() =
382 let val dim = 35
383 val big = Matrix.map (Matrix.make (dim, dim, f), IntInf.fromInt)
384 val entry = Matrix.fetch(smithNormalForm big, dim - 1, dim - 1)
385(* val _ = print (concat [IntInf.toString entry, "\n"]) *)
386 in if entry = valOf (IntInf.fromString
387 "~1027954043102083189860753402541358641712697245")
388 then ()
389 else raise Fail "bug"
390 end
391 fun doit n =
392 let
393 val rec loop =
394 fn 0 => ()
395 | n => (snf(); loop(n - 1))
396 in loop n
397 end
398 end
mlton packaging