1 (* Written by Henry
Cejtin (henry@sourcelight
.com
). *)
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
23 structure Matrix
:> MATRIX
=
25 type 'entry matrix
= int * int * 'entry array
33 fun make (height
: int, width
: int, generator
: int * int -> 'entry
)
35 if height
< 0 orelse width
< 0
39 Array
.tabulate (height
*width
,
40 fn z
=> generator (z
div width
,
43 fun height (height
, _
, _
) = height
45 fun width (width
, _
, _
) = width
47 fun fetch ((height
, width
, mat
), row
, col
) =
52 then Array
.sub (mat
, col
+ width
*row
)
55 fun fetchRow ((height
, width
, mat
), row
) =
56 if 0 <= row
andalso row
< height
57 then let val offset
= width
* row
59 if 0 <= col
andalso col
< width
60 then Array
.sub (mat
, col
+ offset
)
65 fun fetchCol ((height
, width
, mat
), col
) =
66 if 0 <= col
andalso col
< width
68 if 0 <= row
andalso row
< height
69 then Array
.sub (mat
, col
+ width
*row
)
73 fun store ((height
, width
, mat
), row
, col
, entry
) =
78 then Array
.update (mat
, col
+ width
*row
, entry
)
81 fun storeRow ((height
, width
, mat
), row
) =
82 if 0 <= row
andalso row
< height
83 then let val offset
= width
* row
85 if 0 <= col
andalso col
< width
86 then Array
.update (mat
, col
+ offset
, entry
)
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
)
99 fun swapLoop (from1
: int -> 'entry
,
100 to1
: int * 'entry
-> unit
,
101 from2
: int -> 'entry
,
102 to2
: int * 'entry
-> unit
,
104 let fun loop (i
: int): unit
=
107 else let val tmp
= from1 i
115 fun rowSwap (mat
as (height
, width
, _
), row1
, row2
): unit
=
116 if 0 <= row1
andalso row1
< height
117 andalso 0 <= row2
andalso row2
< height
120 else swapLoop (fetchRow (mat
, row1
),
121 storeRow (mat
, row1
),
122 fetchRow (mat
, row2
),
123 storeRow (mat
, row2
),
127 fun colSwap (mat
as (height
, width
, _
), col1
, col2
): unit
=
128 if 0 <= col1
andalso col1
< width
129 andalso 0 <= col2
andalso col2
< width
132 else swapLoop (fetchCol (mat
, col1
),
133 storeCol (mat
, col1
),
134 fetchCol (mat
, col2
),
135 storeCol (mat
, col2
),
139 fun opLoop (from1
: int -> 'entry
,
140 from2
: int -> 'entry
,
141 to2
: int * 'entry
-> unit
,
143 f
: 'entry
* 'entry
-> 'entry
): unit
=
144 let fun loop (i
: int): unit
=
149 f (from1 i
, from2 i
));
154 fun rowOp (mat
as (height
, width
, _
),
157 f
: 'entry
* 'entry
-> 'entry
): unit
=
158 if 0 <= row1
andalso row1
< height
159 andalso 0 <= row2
andalso row2
< height
161 then opLoop (fetchRow (mat
, row1
),
162 fetchRow (mat
, row2
),
163 storeRow (mat
, row2
),
168 fun colOp (mat
as (height
, width
, _
),
171 f
: 'entry
* 'entry
-> 'entry
): unit
=
172 if 0 <= col1
andalso col1
< width
173 andalso 0 <= col2
andalso col2
< width
175 then opLoop (fetchCol (mat
, col1
),
176 fetchCol (mat
, col2
),
177 storeCol (mat
, col2
),
182 fun copy ((height
, width
, mat
)) =
185 Array
.tabulate (Array
.length mat
,
186 fn i
=> Array
.sub (mat
, i
)))
188 fun map ((height
, width
, mat
: 'entry1 Array
.array
),
189 f
: 'entry1
-> 'entry2
)
193 Array
.tabulate (Array
.length mat
,
194 fn i
=> f (Array
.sub (mat
, i
))))
196 (* Natural fold a range
of integers
in reverse
. *)
197 fun naturalFold (limit
: int,
199 folder
: int * 'state
-> 'state
): 'state
=
200 let fun loop (i
: int, state
: 'state
) =
203 else loop (i
- 1, folder (i
- 1, state
))
206 else loop (limit
, state
)
210 local val blank8
= Byte
.charToByte #
" "
212 fun makeBlanks size
=
213 let val blanks
= Word8Vector
.tabulate (size
,
215 in Byte
.bytesToString blanks
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
),
222 fun colWidth col
= naturalFold (height
,
224 maxSize (fetchCol (mat
,
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
232 val s
= String.size next
233 val pad
= Vector.sub (widths
, col
) - s
236 else (makeBlanks pad
)::ac
245 else loop (width
- 1, ac
)
247 val pieces
= naturalFold (height
,
250 in String.concat pieces
255 val zero
= IntInf
.fromInt
0
257 fun smaller (a
: IntInf
.int, b
: IntInf
.int): bool =
259 andalso (b
= zero
orelse IntInf
.< (IntInf
.abs a
, IntInf
.abs b
))
261 fun 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
)
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
) =
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
) =
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)
283 in swapColLoop (best
, bestRow
, bestCol
, pos
)
287 then if (matCol row
) = zero
288 then rowLoop (row
+ 1)
289 else (Matrix
.rowOp (mat
,
292 let val x
= IntInf
.~
(IntInf
.quot(matCol row
, matCol pos
))
293 in fn (lhs
, rhs
) => IntInf
.+ (IntInf
.* (lhs
, x
), rhs
)
295 if (matCol row
) = zero
296 then rowLoop (row
+ 1)
298 else let fun colLoop col
=
300 then if (matRow col
) = zero
301 then colLoop (col
+ 1)
302 else (Matrix
.colOp (mat
,
305 let val x
= IntInf
.~
(IntInf
.quot (matRow col
, matRow pos
))
306 in fn (lhs
, rhs
) => IntInf
.+ (IntInf
.* (lhs
, x
), rhs
)
308 if (matRow col
) = zero
309 then colLoop (col
+ 1)
314 and hitPosAgain () = (swapRowLoop (zero
, pos
, pos
, pos
);
326 val 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]]
377 fun f (x
, y
) = List.nth (List.nth (table
, x
), y
)
378 fun show m
= print (Matrix
.toString (m
, IntInf
.toString
))
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")
389 else raise Fail
"bug"
395 | n
=> (snf(); loop(n
- 1))