Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/smlnj-lib/Util/int-inf.sml
ViewVC logotype

Annotation of /sml/trunk/src/smlnj-lib/Util/int-inf.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1209 - (view) (download)

1 : monnier 26 (* int-inf.sml
2 :     *
3 :     * COPYRIGHT (c) 1995 by AT&T Bell Laboratories. See COPYRIGHT file for details.
4 :     *
5 : monnier 411 * This package is derived from Andrzej Filinski's bignum package. It is very
6 : monnier 26 * close to the definition of the optional IntInf structure in the SML'97 basis.
7 :     *
8 :     * It is implemented almost totally on the abstraction presented by
9 :     * the BigNat structure. The only concrete type information it assumes
10 :     * is that BigNat.bignat = 'a list and that BigNat.zero = [].
11 :     * Some trivial additional efficiency could be obtained by assuming that
12 :     * type bignat is really int list, and that if (v : bignat) = [d], then
13 :     * bignat d = [d].
14 :     *
15 :     * At some point, this should be reimplemented to make use of Word32, or
16 :     * have compiler/runtime support.
17 :     *
18 :     * Also, for booting, this module could be broken into one that has
19 :     * all the types and arithmetic functions, but doesn't use NumScan,
20 :     * constructing values from strings using bignum arithmetic. Various
21 :     * integer and word scanning, such as NumScan, could then be constructed
22 :     * from IntInf. Finally, a user-level IntInf could be built by
23 :     * importing the basic IntInf, but replacing the scanning functions
24 :     * by more efficient ones based on the functions in NumScan.
25 :     *
26 :     *)
27 :    
28 :     structure IntInf :> INT_INF =
29 :     struct
30 :    
31 :     (* It is not clear what advantage there is to having NumFormat as
32 :     * a submodule.
33 :     *)
34 :    
35 :     structure NumScan : sig
36 :    
37 :     val skipWS : (char, 'a) StringCvt.reader -> 'a -> 'a
38 :    
39 : monnier 411 val scanWord : StringCvt.radix
40 :     -> (char, 'a) StringCvt.reader
41 :     -> 'a -> (Word32.word * 'a) option
42 : monnier 26 val scanInt : StringCvt.radix
43 :     -> (char, 'a) StringCvt.reader
44 :     -> 'a -> (int * 'a) option
45 :     (** should be to int32 **)
46 :    
47 :     end = struct
48 :    
49 :     structure W = Word32
50 :     structure I = Int31
51 :    
52 :     val op < = W.<
53 :     val op >= = W.>=
54 :     val op + = W.+
55 :     val op - = W.-
56 :     val op * = W.*
57 :    
58 :     val largestWordDiv10 : Word32.word = 0w429496729(* 2^32-1 divided by 10 *)
59 :     val largestWordMod10 : Word32.word = 0w5 (* remainder *)
60 :     val largestNegInt : Word32.word = 0w1073741824 (* absolute value of ~2^30 *)
61 :     val largestPosInt : Word32.word = 0w1073741823 (* 2^30-1 *)
62 :    
63 :     type 'a chr_strm = {getc : (char, 'a) StringCvt.reader}
64 :    
65 :     (* A table for mapping digits to values. Whitespace characters map to
66 : monnier 411 * 128, "+" maps to 129, "-","~" map to 130, "." maps to 131, and the
67 :     * characters 0-9,A-Z,a-z map to their * base-36 value. All other
68 :     * characters map to 255.
69 : monnier 26 *)
70 :     local
71 :     val cvtTable = "\
72 :     \\255\255\255\255\255\255\255\255\255\128\128\255\255\255\255\255\
73 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
74 : monnier 411 \\128\255\255\255\255\255\255\255\255\255\255\129\255\130\131\255\
75 : monnier 26 \\000\001\002\003\004\005\006\007\008\009\255\255\255\255\255\255\
76 :     \\255\010\011\012\013\014\015\016\017\018\019\020\021\022\023\024\
77 :     \\025\026\027\028\029\030\031\032\033\034\035\255\255\255\255\255\
78 :     \\255\010\011\012\013\014\015\016\017\018\019\020\021\022\023\024\
79 : monnier 411 \\025\026\027\028\029\030\031\032\033\034\035\255\255\255\130\255\
80 : monnier 26 \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
81 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
82 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
83 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
84 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
85 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
86 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
87 :     \\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
88 :     \"
89 :     val ord = Char.ord
90 :     in
91 :     fun code (c : char) = W.fromInt(ord(CharVector.sub(cvtTable, ord c)))
92 :     val wsCode : Word32.word = 0w128
93 : monnier 411 val plusCode : Word32.word = 0w129
94 :     val minusCode : Word32.word = 0w130
95 : monnier 26 end (* local *)
96 :    
97 :     fun skipWS (getc : (char, 'a) StringCvt.reader) cs = let
98 :     fun skip cs = (case (getc cs)
99 :     of NONE => cs
100 :     | (SOME(c, cs')) => if (code c = wsCode) then skip cs' else cs
101 :     (* end case *))
102 :     in
103 :     skip cs
104 :     end
105 :    
106 : monnier 411 (* skip leading whitespace and any sign (+, -, or ~) *)
107 :     fun scanPrefix (getc : (char, 'a) StringCvt.reader) cs = let
108 :     fun skipWS cs = (case (getc cs)
109 :     of NONE => NONE
110 :     | (SOME(c, cs')) => let val c' = code c
111 :     in
112 :     if (c' = wsCode) then skipWS cs' else SOME(c', cs')
113 :     end
114 :     (* end case *))
115 :     fun getNext (neg, cs) = (case (getc cs)
116 :     of NONE => NONE
117 :     | (SOME(c, cs)) => SOME{neg=neg, next=code c, rest=cs}
118 :     (* end case *))
119 :     in
120 :     case (skipWS cs)
121 :     of NONE => NONE
122 :     | (SOME(c, cs')) =>
123 :     if (c = plusCode) then getNext(false, cs')
124 :     else if (c = minusCode) then getNext(true, cs')
125 :     else SOME{neg=false, next=c, rest=cs'}
126 :     (* end case *)
127 :     end
128 :    
129 : monnier 26 (* for power of 2 bases (2, 8 & 16), we can check for overflow by looking
130 :     * at the hi (1, 3 or 4) bits.
131 :     *)
132 :     fun chkOverflow mask w =
133 :     if (W.andb(mask, w) = 0w0) then () else raise Overflow
134 :    
135 : monnier 411 fun scanBin (getc : (char, 'a) StringCvt.reader) cs = (case (scanPrefix getc cs)
136 : monnier 26 of NONE => NONE
137 : monnier 411 | (SOME{neg, next, rest}) => let
138 : monnier 26 fun isDigit (d : Word32.word) = (d < 0w2)
139 :     val chkOverflow = chkOverflow 0wx80000000
140 :     fun cvt (w, rest) = (case (getc rest)
141 : monnier 411 of NONE => SOME{neg=neg, word=w, rest=rest}
142 : monnier 26 | SOME(c, rest') => let val d = code c
143 :     in
144 :     if (isDigit d)
145 :     then (
146 :     chkOverflow w;
147 :     cvt(W.+(W.<<(w, 0w1), d), rest'))
148 : monnier 411 else SOME{neg=neg, word=w, rest=rest}
149 : monnier 26 end
150 :     (* end case *))
151 :     in
152 :     if (isDigit next)
153 :     then cvt(next, rest)
154 :     else NONE
155 :     end
156 :     (* end case *))
157 :    
158 : monnier 411 fun scanOct getc cs = (case (scanPrefix getc cs)
159 : monnier 26 of NONE => NONE
160 : monnier 411 | (SOME{neg, next, rest}) => let
161 : monnier 26 fun isDigit (d : Word32.word) = (d < 0w8)
162 :     val chkOverflow = chkOverflow 0wxE0000000
163 :     fun cvt (w, rest) = (case (getc rest)
164 : monnier 411 of NONE => SOME{neg=neg, word=w, rest=rest}
165 : monnier 26 | SOME(c, rest') => let val d = code c
166 :     in
167 :     if (isDigit d)
168 :     then (
169 :     chkOverflow w;
170 :     cvt(W.+(W.<<(w, 0w3), d), rest'))
171 : monnier 411 else SOME{neg=neg, word=w, rest=rest}
172 : monnier 26 end
173 :     (* end case *))
174 :     in
175 :     if (isDigit next)
176 :     then cvt(next, rest)
177 :     else NONE
178 :     end
179 :     (* end case *))
180 :    
181 : monnier 411 fun scanDec getc cs = (case (scanPrefix getc cs)
182 : monnier 26 of NONE => NONE
183 : monnier 411 | (SOME{neg, next, rest}) => let
184 : monnier 26 fun isDigit (d : Word32.word) = (d < 0w10)
185 :     fun cvt (w, rest) = (case (getc rest)
186 : monnier 411 of NONE => SOME{neg=neg, word=w, rest=rest}
187 : monnier 26 | SOME(c, rest') => let val d = code c
188 :     in
189 :     if (isDigit d)
190 :     then (
191 :     if ((w >= largestWordDiv10)
192 :     andalso ((largestWordDiv10 < w)
193 :     orelse (largestWordMod10 < d)))
194 :     then raise Overflow
195 :     else ();
196 :     cvt (0w10*w+d, rest'))
197 : monnier 411 else SOME{neg=neg, word=w, rest=rest}
198 : monnier 26 end
199 :     (* end case *))
200 :     in
201 :     if (isDigit next)
202 :     then cvt(next, rest)
203 :     else NONE
204 :     end
205 :     (* end case *))
206 : jhr 1209
207 :     (* consume a possible "0x" or "0X" prefix on a hex literal *)
208 :     fun scan0x getc NONE = NONE
209 :     | scan0x getc (orig as SOME{neg, next, rest}) =
210 :     if (next = 0w0)
211 :     then (case getc rest
212 :     of SOME((#"x" | #"X"), rest1) => (case getc rest1
213 :     of SOME(c, rest2) => let
214 :     val d = code c
215 :     in
216 :     if (d < 0w16)
217 :     then SOME{neg=neg, next=d, rest=rest2}
218 :     else orig
219 :     end
220 :     | NONE => orig
221 :     (* end case *))
222 :     | _ => orig
223 :     (* end case *))
224 :     else orig
225 :    
226 :     fun scanHex getc cs = (case scan0x getc (scanPrefix getc cs)
227 : monnier 26 of NONE => NONE
228 : monnier 411 | (SOME{neg, next, rest}) => let
229 : monnier 26 fun isDigit (d : Word32.word) = (d < 0w16)
230 :     val chkOverflow = chkOverflow 0wxF0000000
231 :     fun cvt (w, rest) = (case (getc rest)
232 : monnier 411 of NONE => SOME{neg=neg, word=w, rest=rest}
233 : monnier 26 | SOME(c, rest') => let val d = code c
234 :     in
235 :     if (isDigit d)
236 :     then (
237 :     chkOverflow w;
238 :     cvt(W.+(W.<<(w, 0w4), d), rest'))
239 : monnier 411 else SOME{neg=neg, word=w, rest=rest}
240 : monnier 26 end
241 :     (* end case *))
242 :     in
243 :     if (isDigit next)
244 :     then cvt(next, rest)
245 :     else NONE
246 :     end
247 :     (* end case *))
248 :    
249 : monnier 411 fun finalWord scanFn getc cs = (case (scanFn getc cs)
250 :     of NONE => NONE
251 :     | (SOME{neg=true, ...}) => NONE
252 :     | (SOME{neg=false, word, rest}) => SOME(word, rest)
253 :     (* end case *))
254 :    
255 :     fun scanWord StringCvt.BIN = finalWord scanBin
256 :     | scanWord StringCvt.OCT = finalWord scanOct
257 :     | scanWord StringCvt.DEC = finalWord scanDec
258 :     | scanWord StringCvt.HEX = finalWord scanHex
259 :    
260 : monnier 26 fun finalInt scanFn getc cs = (case (scanFn getc cs)
261 :     of NONE => NONE
262 : monnier 411 | (SOME{neg=true, word, rest}) =>
263 :     if (largestNegInt < word)
264 :     then raise Overflow
265 :     else SOME(I.~(W.toInt word), rest)
266 :     | (SOME{word, rest, ...}) =>
267 : monnier 26 if (largestPosInt < word)
268 :     then raise Overflow
269 :     else SOME(W.toInt word, rest)
270 :     (* end case *))
271 :    
272 :     fun scanInt StringCvt.BIN = finalInt scanBin
273 :     | scanInt StringCvt.OCT = finalInt scanOct
274 :     | scanInt StringCvt.DEC = finalInt scanDec
275 :     | scanInt StringCvt.HEX = finalInt scanHex
276 :    
277 :     end (* structure NumScan *)
278 :    
279 :     structure NumFormat : sig
280 :    
281 :     val fmtWord : StringCvt.radix -> Word32.word -> string
282 :     val fmtInt : StringCvt.radix -> int -> string (** should be int32 **)
283 :    
284 :     end = struct
285 :    
286 :     structure W = Word32
287 :     structure I = Int
288 :    
289 :     val op < = W.<
290 :     val op - = W.-
291 :     val op * = W.*
292 :     val op div = W.div
293 :    
294 :     fun mkDigit (w : Word32.word) =
295 :     CharVector.sub("0123456789abcdef", W.toInt w)
296 :    
297 :     fun wordToBin w = let
298 :     fun mkBit w = if (W.andb(w, 0w1) = 0w0) then #"0" else #"1"
299 :     fun f (0w0, n, l) = (I.+(n, 1), #"0" :: l)
300 :     | f (0w1, n, l) = (I.+(n, 1), #"1" :: l)
301 :     | f (w, n, l) = f(W.>>(w, 0w1), I.+(n, 1), (mkBit w) :: l)
302 :     in
303 :     f (w, 0, [])
304 :     end
305 :     fun wordToOct w = let
306 :     fun f (w, n, l) = if (w < 0w8)
307 :     then (I.+(n, 1), (mkDigit w) :: l)
308 :     else f(W.>>(w, 0w3), I.+(n, 1), mkDigit(W.andb(w, 0w7)) :: l)
309 :     in
310 :     f (w, 0, [])
311 :     end
312 :     fun wordToDec w = let
313 :     fun f (w, n, l) = if (w < 0w10)
314 :     then (I.+(n, 1), (mkDigit w) :: l)
315 :     else let val j = w div 0w10
316 :     in
317 :     f (j, I.+(n, 1), mkDigit(w - 0w10*j) :: l)
318 :     end
319 :     in
320 :     f (w, 0, [])
321 :     end
322 :     fun wordToHex w = let
323 :     fun f (w, n, l) = if (w < 0w16)
324 :     then (I.+(n, 1), (mkDigit w) :: l)
325 :     else f(W.>>(w, 0w4), I.+(n, 1), mkDigit(W.andb(w, 0w15)) :: l)
326 :     in
327 :     f (w, 0, [])
328 :     end
329 :    
330 :     fun fmtW StringCvt.BIN = #2 o wordToBin
331 :     | fmtW StringCvt.OCT = #2 o wordToOct
332 :     | fmtW StringCvt.DEC = #2 o wordToDec
333 :     | fmtW StringCvt.HEX = #2 o wordToHex
334 :    
335 :     fun fmtWord radix = String.implode o (fmtW radix)
336 :    
337 :     (** NOTE: this currently uses 31-bit integers, but really should use 32-bit
338 :     ** ints (once they are supported).
339 :     **)
340 :     fun fmtInt radix = let
341 :     val fmtW = fmtW radix
342 :     val itow = W.fromInt
343 :     fun fmt i = if I.<(i, 0)
344 :     then let
345 :     val (digits) = fmtW(itow(I.~ i))
346 :     in
347 :     String.implode(#"~"::digits)
348 :     end
349 :     handle _ => (case radix
350 :     of StringCvt.BIN => "~1111111111111111111111111111111"
351 :     | StringCvt.OCT => "~7777777777"
352 :     | StringCvt.DEC => "~1073741824"
353 :     | StringCvt.HEX => "~3fffffff"
354 :     (* end case *))
355 :     else String.implode(fmtW(itow i))
356 :     in
357 :     fmt
358 :     end
359 :    
360 :     end (* structure NumFormat *)
361 :    
362 :     structure BigNat =
363 :     struct
364 :    
365 :     exception Negative
366 :    
367 :     val itow = Word.fromInt
368 :     val wtoi = Word.toIntX
369 :    
370 :     val lgBase = 30 (* No. of bits per digit; must be even *)
371 :     val nbase = ~0x40000000 (* = ~2^lgBase *)
372 :    
373 :     val maxDigit = ~(nbase + 1)
374 :     val realBase = (real maxDigit) + 1.0
375 :    
376 :     val lgHBase = Int.quot (lgBase, 2) (* half digits *)
377 :     val hbase = Word.<<(0w1, itow lgHBase)
378 :     val hmask = hbase-0w1
379 :    
380 :     fun quotrem (i, j) = (Int.quot (i, j), Int.rem (i, j))
381 :     fun scale i = if i = maxDigit then 1 else nbase div (~(i+1))
382 :    
383 :     type bignat = int list (* least significant digit first *)
384 :    
385 :     val zero = []
386 :     val one = [1]
387 :    
388 :     fun bignat 0 = zero
389 :     | bignat i = let
390 :     val notNbase = Word.notb(itow nbase)
391 :     fun bn 0w0 = []
392 :     | bn i = let
393 :     fun dmbase n =
394 :     (Word.>> (n, itow lgBase), Word.andb (n, notNbase))
395 :     val (q,r) = dmbase i
396 :     in
397 :     (wtoi r)::(bn q)
398 :     end
399 :     in
400 :     if i > 0
401 :     then if i <= maxDigit then [i] else bn (itow i)
402 :     else raise Negative
403 :     end
404 :    
405 :     fun int [] = 0
406 :     | int [d] = d
407 :     | int [d,e] = ~(nbase*e) + d
408 :     | int (d::r) = ~(nbase*int r) + d
409 :    
410 :     fun consd (0, []) = []
411 :     | consd (d, r) = d::r
412 :    
413 :     fun hl i = let
414 :     val w = itow i
415 :     in
416 :     (wtoi(Word.~>> (w, itow lgHBase)), (* MUST sign-extend *)
417 :     wtoi(Word.andb(w, hmask)))
418 :     end
419 :    
420 :     fun sh i = wtoi(Word.<< (itow i, itow lgHBase))
421 :    
422 :     fun addOne [] = [1]
423 :     | addOne (m::rm) = let
424 :     val c = nbase+m+1
425 :     in
426 :     if c < 0 then (c-nbase)::rm else c::(addOne rm)
427 :     end
428 :    
429 :     fun add ([], digits) = digits
430 :     | add (digits, []) = digits
431 :     | add (dm::rm, dn::rn) = addd (nbase+dm+dn, rm, rn)
432 :     and addd (s, m, n) =
433 :     if s < 0 then (s-nbase) :: add (m, n) else (s :: addc (m, n))
434 :     and addc (m, []) = addOne m
435 :     | addc ([], n) = addOne n
436 :     | addc (dm::rm, dn::rn) = addd (nbase+dm+dn+1, rm, rn)
437 :    
438 :     fun subtOne (0::mr) = maxDigit::(subtOne mr)
439 :     | subtOne [1] = []
440 :     | subtOne (n::mr) = (n-1)::mr
441 :     | subtOne [] = raise Fail ""
442 :    
443 :     fun subt (m, []) = m
444 :     | subt ([], n) = raise Negative
445 :     | subt (dm::rm, dn::rn) = subd(dm-dn,rm,rn)
446 :     and subb ([], n) = raise Negative
447 :     | subb (dm::rm, []) = subd (dm-1, rm, [])
448 :     | subb (dm::rm, dn::rn) = subd (dm-dn-1, rm, rn)
449 :     and subd (d, m, n) =
450 :     if d >= 0 then consd(d, subt (m, n)) else consd(d-nbase, subb (m, n))
451 :    
452 :     (* multiply 2 digits *)
453 :     fun mul2 (m, n) = let
454 :     val (mh, ml) = hl m
455 :     val (nh, nl) = hl n
456 :     val x = mh*nh
457 :     val y = (mh-ml)*(nh-nl) (* x-y+z = mh*nl + ml*nh *)
458 :     val z = ml*nl
459 :     val (zh, zl) = hl z
460 :     val (uh,ul) = hl (nbase+x+z-y+zh) (* can't overflow *)
461 :     in (x+uh+wtoi hbase, sh ul+zl) end
462 :    
463 :     (* multiply bigint by digit *)
464 :     fun muld (m, 0) = []
465 :     | muld (m, 1) = m (* speedup *)
466 :     | muld (m, i) = let
467 :     fun muldc ([], 0) = []
468 :     | muldc ([], c) = [c]
469 :     | muldc (d::r, c) = let
470 :     val (h, l) = mul2 (d, i)
471 :     val l1 = l+nbase+c
472 :     in
473 :     if l1 >= 0
474 :     then l1::muldc (r, h+1)
475 :     else (l1-nbase)::muldc (r, h)
476 :     end
477 :     in muldc (m, 0) end
478 :    
479 :     fun mult (m, []) = []
480 :     | mult (m, [d]) = muld (m, d) (* speedup *)
481 :     | mult (m, 0::r) = consd (0, mult (m, r)) (* speedup *)
482 :     | mult (m, n) = let
483 :     fun muln [] = []
484 :     | muln (d::r) = add (muld (n, d), consd (0, muln r))
485 :     in muln m end
486 :    
487 :     (* divide DP number by digit; assumes u < i , i >= base/2 *)
488 :     fun divmod2 ((u,v), i) = let
489 :     val (vh,vl) = hl v
490 :     val (ih,il) = hl i
491 :     fun adj (q,r) = if r<0 then adj (q-1, r+i) else (q, r)
492 :     val (q1,r1) = quotrem (u, ih)
493 :     val (q1,r1) = adj (q1, sh r1+vh-q1*il)
494 :     val (q0,r0) = quotrem (r1, ih)
495 :     val (q0,r0) = adj (q0, sh r0+vl-q0*il)
496 :     in (sh q1+q0, r0) end
497 :    
498 :     (* divide bignat by digit>0 *)
499 :     fun divmodd (m, 1) = (m, 0) (* speedup *)
500 :     | divmodd (m, i) = let
501 :     val scale = scale i
502 :     val i' = i * scale
503 :     val m' = muld (m, scale)
504 :     fun dmi [] = ([], 0)
505 :     | dmi (d::r) = let
506 :     val (qt,rm) = dmi r
507 :     val (q1,r1) = divmod2 ((rm,d), i')
508 :     in (consd (q1,qt), r1) end
509 :     val (q,r) = dmi m'
510 :     in (q, r div scale) end
511 :    
512 :     (* From Knuth Vol II, 4.3.1, but without opt. in step D3 *)
513 :     fun divmod (m, []) = raise Div
514 :     | divmod ([], n) = ([], []) (* speedup *)
515 :     | divmod (d::r, 0::s) = let
516 :     val (qt,rm) = divmod (r,s)
517 :     in (qt, consd (d, rm)) end (* speedup *)
518 :     | divmod (m, [d]) = let
519 :     val (qt, rm) = divmodd (m, d)
520 :     in (qt, if rm=0 then [] else [rm]) end
521 :     | divmod (m, n) = let
522 :     val ln = length n (* >= 2 *)
523 :     val scale = scale(List.nth (n,ln-1))
524 :     val m' = muld (m, scale)
525 :     val n' = muld (n, scale)
526 :     val n1 = List.nth (n', ln-1) (* >= base/2 *)
527 :     fun divl [] = ([], [])
528 :     | divl (d::r) = let
529 :     val (qt,rm) = divl r
530 :     val m = consd (d, rm)
531 :     fun msds ([],_) = (0,0)
532 :     | msds ([d],1) = (0,d)
533 :     | msds ([d2,d1],1) = (d1,d2)
534 :     | msds (d::r,i) = msds (r,i-1)
535 :     val (m1,m2) = msds (m, ln)
536 :     val tq = if m1 = n1 then maxDigit
537 :     else #1 (divmod2 ((m1,m2), n1))
538 :     fun try (q,qn') = (q, subt (m,qn'))
539 :     handle Negative => try (q-1, subt (qn', n'))
540 :     val (q,rr) = try (tq, muld (n',tq))
541 :     in (consd (q,qt), rr) end
542 :     val (qt,rm') = divl m'
543 :     val (rm,_(*0*)) = divmodd (rm',scale)
544 :     in (qt,rm) end
545 :    
546 : jhr 1194 fun eq ([], []) = true
547 :     | eq ((i : int)::ri,j::rj) = (i = j) andalso eq(ri, rj)
548 :     | eq _ = false
549 :    
550 :     fun neq ([], []) = false
551 :     | neq ((i : int)::ri,j::rj) = (i <> j) orelse neq(ri, rj)
552 :     | neq _ = true
553 :    
554 : monnier 26 fun cmp ([],[]) = EQUAL
555 :     | cmp (_,[]) = GREATER
556 :     | cmp ([],_) = LESS
557 :     | cmp ((i : int)::ri,j::rj) =
558 :     case cmp (ri,rj) of
559 :     EQUAL => if i = j then EQUAL
560 :     else if i < j then LESS
561 :     else GREATER
562 :     | c => c
563 :    
564 :     fun exp (_, 0) = one
565 :     | exp ([], n) = if n > 0 then zero else raise Div
566 :     | exp (m, n) =
567 :     if n < 0 then zero
568 :     else let
569 :     fun expm 0 = [1]
570 :     | expm 1 = m
571 :     | expm i = let
572 :     val r = expm (i div 2)
573 :     val r2 = mult (r,r)
574 :     in
575 :     if i mod 2 = 0 then r2 else mult (r2, m)
576 :     end
577 :     in expm n end
578 :    
579 :     local
580 :     fun try n = if n >= lgHBase then n else try (2*n)
581 :     val pow2lgHBase = try 1
582 :     in
583 :     fun log2 [] = raise Domain
584 :     | log2 (h::t) = let
585 :     fun qlog (x,0) = 0
586 :     | qlog (x,b) =
587 :     if x >= wtoi(Word.<< (0w1, itow b)) then
588 :     b+qlog (wtoi(Word.>> (itow x, itow b)), b div 2)
589 :     else qlog (x, b div 2)
590 :     fun loop (d,[],lg) = lg + qlog (d,pow2lgHBase)
591 :     | loop (_,h::t,lg) = loop (h,t,lg + lgBase)
592 :     in
593 :     loop (h,t,0)
594 :     end
595 :     end (* local *)
596 :    
597 :     (* find maximal maxpow s.t. radix^maxpow < base
598 :     * basepow = radix^maxpow
599 :     *)
600 :     fun mkPowers radix = let
601 :     val powers = let
602 :     val bnd = Int.quot (nbase, (~radix))
603 :     fun try (tp,l) =
604 :     (if tp <= bnd then try (radix*tp,tp::l)
605 :     else (tp::l))
606 :     handle _ => tp::l
607 :     in Vector.fromList(rev(try (radix,[1]))) end
608 :     val maxpow = Vector.length powers - 1
609 :     in
610 :     (maxpow, Vector.sub(powers,maxpow), powers)
611 :     end
612 :     val powers2 = mkPowers 2
613 :     val powers8 = mkPowers 8
614 :     val powers10 = mkPowers 10
615 :     val powers16 = mkPowers 16
616 :    
617 :     fun fmt (pow, radpow, puti) n = let
618 :     val pad = StringCvt.padLeft #"0" pow
619 :     fun ms0 (0,a) = (pad "")::a
620 :     | ms0 (i,a) = (pad (puti i))::a
621 :     fun ml (n,a) =
622 :     case divmodd (n, radpow) of
623 :     ([],d) => (puti d)::a
624 :     | (q,d) => ml (q, ms0 (d, a))
625 :     in
626 :     concat (ml (n,[]))
627 :     end
628 :    
629 :     val fmt2 = fmt (#1 powers2, #2 powers2, NumFormat.fmtInt StringCvt.BIN)
630 :     val fmt8 = fmt (#1 powers8, #2 powers8, NumFormat.fmtInt StringCvt.OCT)
631 :     val fmt10 = fmt (#1 powers10, #2 powers10, NumFormat.fmtInt StringCvt.DEC)
632 :     val fmt16 = fmt (#1 powers16, #2 powers16, NumFormat.fmtInt StringCvt.HEX)
633 :    
634 :     fun scan (bound,powers,geti) getc cs = let
635 :     fun get (l,cs) = if l = bound then NONE
636 :     else case getc cs of
637 :     NONE => NONE
638 :     | SOME(c,cs') => SOME(c, (l+1,cs'))
639 :     fun loop (acc,cs) =
640 :     case geti get (0,cs) of
641 :     NONE => (acc,cs)
642 :     | SOME(0,(sh,cs')) =>
643 :     loop(add(muld(acc,Vector.sub(powers,sh)),[]),cs')
644 :     | SOME(i,(sh,cs')) =>
645 :     loop(add(muld(acc,Vector.sub(powers,sh)),[i]),cs')
646 :     in
647 :     case geti get (0,cs) of
648 :     NONE => NONE
649 :     | SOME(0,(_,cs')) => SOME (loop([],cs'))
650 :     | SOME(i,(_,cs')) => SOME (loop([i],cs'))
651 :     end
652 :    
653 :     fun scan2 getc = scan(#1 powers2, #3 powers2, NumScan.scanInt StringCvt.BIN) getc
654 :     fun scan8 getc = scan(#1 powers8, #3 powers8, NumScan.scanInt StringCvt.OCT) getc
655 :     fun scan10 getc = scan(#1 powers10, #3 powers10, NumScan.scanInt StringCvt.DEC) getc
656 :     fun scan16 getc = scan(#1 powers16, #3 powers16, NumScan.scanInt StringCvt.HEX) getc
657 :    
658 :     end (* structure BigNat *)
659 :    
660 : leunga 755
661 : monnier 26 structure BN = BigNat
662 :    
663 :     datatype sign = POS | NEG
664 :     datatype int = BI of {
665 :     sign : sign,
666 :     digits : BN.bignat
667 :     }
668 :    
669 :     val zero = BI{sign=POS, digits=BN.zero}
670 :     val one = BI{sign=POS, digits=BN.one}
671 :     val minus_one = BI{sign=NEG, digits=BN.one}
672 :     fun posi digits = BI{sign=POS, digits=digits}
673 :     fun negi digits = BI{sign=NEG, digits=digits}
674 :     fun zneg [] = zero
675 :     | zneg digits = BI{sign=NEG, digits=digits}
676 :    
677 :     local
678 :     val minNeg = valOf Int.minInt
679 :     val bigNatMinNeg = BN.addOne (BN.bignat (~(minNeg+1)))
680 :     val bigIntMinNeg = negi bigNatMinNeg
681 :     in
682 :    
683 :     fun toInt (BI{digits=[], ...}) = 0
684 :     | toInt (BI{sign=POS, digits}) = BN.int digits
685 :     | toInt (BI{sign=NEG, digits}) =
686 :     (~(BN.int digits)) handle _ =>
687 :     if digits = bigNatMinNeg then minNeg else raise Overflow
688 :    
689 :     fun fromInt 0 = zero
690 :     | fromInt i =
691 :     if i < 0
692 :     then if (i = minNeg)
693 :     then bigIntMinNeg
694 :     else BI{sign=NEG, digits= BN.bignat (~i)}
695 :     else BI{sign=POS, digits= BN.bignat i}
696 :     end (* local *)
697 :    
698 :     (* The following assumes LargeInt = Int32.
699 :     * If IntInf is provided, it will be LargeInt and toLarge and fromLarge
700 :     * will be the identity function.
701 :     *)
702 :     local
703 :     val minNeg = valOf LargeInt.minInt
704 :     val maxDigit = LargeInt.fromInt BN.maxDigit
705 :     val nbase = LargeInt.fromInt BN.nbase
706 :     val lgBase = Word.fromInt BN.lgBase
707 :     val notNbase = Word32.notb(Word32.fromInt BN.nbase)
708 :     fun largeNat (0 : LargeInt.int) = []
709 :     | largeNat i = let
710 :     fun bn (0w0 : Word32.word) = []
711 :     | bn i = let
712 :     fun dmbase n = (Word32.>> (n, lgBase), Word32.andb (n, notNbase))
713 :     val (q,r) = dmbase i
714 :     in
715 :     (Word32.toInt r)::(bn q)
716 :     end
717 :     in
718 :     if i <= maxDigit then [LargeInt.toInt i] else bn (Word32.fromLargeInt i)
719 :     end
720 :    
721 :     fun large [] = 0
722 :     | large [d] = LargeInt.fromInt d
723 :     | large [d,e] = ~(nbase*(LargeInt.fromInt e)) + (LargeInt.fromInt d)
724 :     | large (d::r) = ~(nbase*large r) + (LargeInt.fromInt d)
725 :    
726 :     val bigNatMinNeg = BN.addOne (largeNat (~(minNeg+1)))
727 :     val bigIntMinNeg = negi bigNatMinNeg
728 :     in
729 :    
730 :     fun toLarge (BI{digits=[], ...}) = 0
731 :     | toLarge (BI{sign=POS, digits}) = large digits
732 :     | toLarge (BI{sign=NEG, digits}) =
733 :     (~(large digits)) handle _ =>
734 :     if digits = bigNatMinNeg then minNeg else raise Overflow
735 :    
736 :     fun fromLarge 0 = zero
737 :     | fromLarge i =
738 :     if i < 0
739 :     then if (i = minNeg)
740 :     then bigIntMinNeg
741 :     else BI{sign=NEG, digits= largeNat (~i)}
742 :     else BI{sign=POS, digits= largeNat i}
743 :     end (* local *)
744 :    
745 :     fun negSign POS = NEG
746 :     | negSign NEG = POS
747 :    
748 :     fun subtNat (m, []) = {sign=POS, digits=m}
749 :     | subtNat ([], n) = {sign=NEG, digits=n}
750 :     | subtNat (m,n) =
751 :     ({sign=POS,digits = BN.subt(m,n)})
752 :     handle BN.Negative => ({sign=NEG,digits = BN.subt(n,m)})
753 :    
754 :     val precision = NONE
755 :     val minInt = NONE
756 :     val maxInt = NONE
757 :    
758 :     fun ~ (i as BI{digits=[], ...}) = i
759 :     | ~ (BI{sign=POS, digits}) = BI{sign=NEG, digits=digits}
760 :     | ~ (BI{sign=NEG, digits}) = BI{sign=POS, digits=digits}
761 :    
762 :     fun op * (_,BI{digits=[], ...}) = zero
763 :     | op * (BI{digits=[], ...},_) = zero
764 :     | op * (BI{sign=POS, digits=d1}, BI{sign=NEG, digits=d2}) =
765 :     BI{sign=NEG,digits=BN.mult(d1,d2)}
766 :     | op * (BI{sign=NEG, digits=d1}, BI{sign=POS, digits=d2}) =
767 :     BI{sign=NEG,digits=BN.mult(d1,d2)}
768 :     | op * (BI{digits=d1,...}, BI{digits=d2,...}) =
769 :     BI{sign=POS,digits=BN.mult(d1,d2)}
770 :    
771 :     fun op + (BI{digits=[], ...}, i2) = i2
772 :     | op + (i1, BI{digits=[], ...}) = i1
773 :     | op + (BI{sign=POS, digits=d1}, BI{sign=NEG, digits=d2}) =
774 :     BI(subtNat(d1, d2))
775 :     | op + (BI{sign=NEG, digits=d1}, BI{sign=POS, digits=d2}) =
776 :     BI(subtNat(d2, d1))
777 :     | op + (BI{sign, digits=d1}, BI{digits=d2, ...}) =
778 :     BI{sign=sign, digits=BN.add(d1, d2)}
779 :    
780 :     fun op - (i1, BI{digits=[], ...}) = i1
781 :     | op - (BI{digits=[], ...}, BI{sign, digits}) =
782 :     BI{sign=negSign sign, digits=digits}
783 :     | op - (BI{sign=POS, digits=d1}, BI{sign=POS, digits=d2}) =
784 :     BI(subtNat(d1, d2))
785 :     | op - (BI{sign=NEG, digits=d1}, BI{sign=NEG, digits=d2}) =
786 :     BI(subtNat(d2, d1))
787 :     | op - (BI{sign, digits=d1}, BI{digits=d2, ...}) =
788 :     BI{sign=sign, digits=BN.add(d1, d2)}
789 :    
790 :     fun quotrem (BI{sign=POS,digits=m},BI{sign=POS,digits=n}) =
791 :     (case BN.divmod (m,n) of (q,r) => (posi q, posi r))
792 :     | quotrem (BI{sign=POS,digits=m},BI{sign=NEG,digits=n}) =
793 :     (case BN.divmod (m,n) of (q,r) => (zneg q, posi r))
794 :     | quotrem (BI{sign=NEG,digits=m},BI{sign=POS,digits=n}) =
795 :     (case BN.divmod (m,n) of (q,r) => (zneg q, zneg r))
796 :     | quotrem (BI{sign=NEG,digits=m},BI{sign=NEG,digits=n}) =
797 :     (case BN.divmod (m,n) of (q,r) => (posi q, zneg r))
798 :    
799 :     fun divmod (BI{sign=POS,digits=m},BI{sign=POS,digits=n}) =
800 :     (case BN.divmod (m,n) of (q,r) => (posi q, posi r))
801 :     | divmod (BI{sign=POS,digits=[]},BI{sign=NEG,digits=n}) = (zero,zero)
802 :     | divmod (BI{sign=POS,digits=m},BI{sign=NEG,digits=n}) = let
803 :     val (q,r) = BN.divmod (BN.subtOne m, n)
804 :     in (negi(BN.addOne q), zneg(BN.subtOne(BN.subt(n,r)))) end
805 :     | divmod (BI{sign=NEG,digits=m},BI{sign=POS,digits=n}) = let
806 :     val (q,r) = BN.divmod (BN.subtOne m, n)
807 :     in (negi(BN.addOne q), posi(BN.subtOne(BN.subt(n,r)))) end
808 :     | divmod (BI{sign=NEG,digits=m},BI{sign=NEG,digits=n}) =
809 :     (case BN.divmod (m,n) of (q,r) => (posi q, zneg r))
810 :    
811 :     fun op div arg = #1(divmod arg)
812 :     fun op mod arg = #2(divmod arg)
813 :     fun op quot arg = #1(quotrem arg)
814 :     fun op rem arg = #2(quotrem arg)
815 :    
816 :     fun compare (BI{sign=NEG,...},BI{sign=POS,...}) = LESS
817 :     | compare (BI{sign=POS,...},BI{sign=NEG,...}) = GREATER
818 :     | compare (BI{sign=POS,digits=d},BI{sign=POS,digits=d'}) = BN.cmp (d,d')
819 :     | compare (BI{sign=NEG,digits=d},BI{sign=NEG,digits=d'}) = BN.cmp (d',d)
820 :    
821 :     fun op < arg = case compare arg of LESS => true | _ => false
822 :     fun op > arg = case compare arg of GREATER => true | _ => false
823 :     fun op <= arg = case compare arg of GREATER => false | _ => true
824 :     fun op >= arg = case compare arg of LESS => false | _ => true
825 :    
826 :     fun abs (BI{sign=NEG, digits}) = BI{sign=POS, digits=digits}
827 :     | abs i = i
828 :    
829 :     fun max arg = case compare arg of GREATER => #1 arg | _ => #2 arg
830 :     fun min arg = case compare arg of LESS => #1 arg | _ => #2 arg
831 :    
832 :     fun sign (BI{sign=NEG,...}) = ~1
833 :     | sign (BI{digits=[],...}) = 0
834 :     | sign _ = 1
835 :    
836 :     fun sameSign (i,j) = sign i = sign j
837 :    
838 :     local
839 :     fun fmt' fmtFn i =
840 :     case i of
841 :     (BI{digits=[],...}) => "0"
842 :     | (BI{sign=NEG,digits}) => "~"^(fmtFn digits)
843 :     | (BI{sign=POS,digits}) => fmtFn digits
844 :     in
845 :     fun fmt StringCvt.BIN = fmt' (BN.fmt2)
846 :     | fmt StringCvt.OCT = fmt' (BN.fmt8)
847 :     | fmt StringCvt.DEC = fmt' (BN.fmt10)
848 :     | fmt StringCvt.HEX = fmt' (BN.fmt16)
849 :     end
850 :    
851 :     val toString = fmt StringCvt.DEC
852 :    
853 :     local
854 :     fun scan' scanFn getc cs = let
855 :     val cs' = NumScan.skipWS getc cs
856 :     fun cvt (NONE,_) = NONE
857 :     | cvt (SOME(i,cs),wr) = SOME(wr i, cs)
858 :     in
859 :     case (getc cs')
860 :     of (SOME((#"~" | #"-"), cs'')) => cvt(scanFn getc cs'',zneg)
861 :     | (SOME(#"+", cs'')) => cvt(scanFn getc cs'',posi)
862 :     | (SOME _) => cvt(scanFn getc cs',posi)
863 :     | NONE => NONE
864 :     (* end case *)
865 :     end
866 :     in
867 :     fun scan StringCvt.BIN = scan' (BN.scan2)
868 :     | scan StringCvt.OCT = scan' (BN.scan8)
869 :     | scan StringCvt.DEC = scan' (BN.scan10)
870 :     | scan StringCvt.HEX = scan' (BN.scan16)
871 :     end
872 :    
873 :     fun fromString s = StringCvt.scanString (scan StringCvt.DEC) s
874 :    
875 :     fun pow (_, 0) = one
876 :     | pow (BI{sign=POS,digits}, n) = posi(BN.exp(digits,n))
877 :     | pow (BI{sign=NEG,digits}, n) =
878 :     if Int.mod (n, 2) = 0
879 :     then posi(BN.exp(digits,n))
880 :     else zneg(BN.exp(digits,n))
881 :    
882 :     fun log2 (BI{sign=POS,digits}) = BN.log2 digits
883 :     | log2 _ = raise Domain
884 :    
885 : leunga 755 (*-------------------------------------------------------------------
886 :     * Bit level operators are implemented here.
887 :     * Allen Leung
888 :     * Last Updated: 12/13/2000
889 :     *
890 :     * Note:
891 :     * o The base is 30 so there is no way that the sign bit is 1 after
892 :     * andb, orb, or xorb. But notb require a hack.
893 :     * o I use Word.word as the intermediate type for
894 :     * computing results because the conversion back to int does not
895 :     * require a range check.
896 :     * o Negative values are assumed to have an infinite number of
897 :     * leading ones.
898 :     *-------------------------------------------------------------------*)
899 :     structure BitOps =
900 :     struct
901 :     structure W = Word
902 :     val i2w = W.fromInt
903 :     val w2i = W.toIntX
904 :     val op - = W.-
905 :    
906 :     val base = W.<<(0w1, i2w BN.lgBase)
907 :     val maxVal = W.-(base, 0w1)
908 :     fun stripSignBit w = W.andb(w, maxVal)
909 :    
910 :     fun notb x = ~(x + one)
911 :    
912 :     (* Internally we are store things in one's complement+sign form.
913 :     * But we have to simulate 2's complement arithmetic.
914 :     *)
915 :     fun binary (f,g) (BI{sign=sx,digits=xs}, BI{sign=sy,digits=ys}) =
916 :     let val sign = g(sx,sy) (* sign of result, if non-zero *)
917 :    
918 :     (* convert to two's complement;
919 :     * Compute (- x - borrow)
920 :     *)
921 :     fun twos(POS, x, borrow) = (x, 0w0)
922 :     | twos(NEG, 0w0, 0w0) = (0w0, 0w0) (* no borrow *)
923 :     | twos(NEG, x, borrow) =(base - x - borrow, 0w1) (* borrow *)
924 :    
925 :     (* convert to ones's complement *)
926 :     val ones = twos
927 :    
928 :     fun loop([], [], _, _, _) = []
929 :     | loop([], y::ys, bx, by, bz) =
930 :     loop1(0w0, [], i2w y, ys, bx, by, bz)
931 :     | loop(x::xs, [], bx, by, bz) =
932 :     loop1(i2w x, xs, 0w0, [], bx, by, bz)
933 :     | loop(x::xs, y::ys, bx, by, bz) =
934 :     loop1(i2w x, xs, i2w y, ys, bx, by, bz)
935 :     and loop1(x, xs, y, ys, bx, by, bz) =
936 :     let (* convert from ones complement *)
937 :     val (x, bx) = twos(sx, x, bx)
938 :     val (y, by) = twos(sy, y, by)
939 :     val z = f(x,y)
940 :     (* convert back to ones complement *)
941 :     val (z, bz) = ones(sign, z, bz)
942 :     val z = w2i z
943 :     val zs = loop(xs, ys, bx, by, bz)
944 :     in case (z, zs) of (* strip leading zero *)
945 :     (0, []) => []
946 :     | (z, zs) => z::zs
947 :     end
948 :    
949 :     in case loop(xs, ys, 0w0, 0w0, 0w0) of
950 :     [] => zero
951 :     | digits => BI{sign=sign, digits=digits}
952 :     end
953 :    
954 :    
955 :     val andb = binary (W.andb, fn (NEG,NEG) => NEG | _ => POS)
956 :     (* negative if any are negative *)
957 :     val orb = binary (W.orb, fn (POS,POS) => POS | _ => NEG)
958 :     (* negative if only one is negative *)
959 :     val xorb = binary (fn (x,y) => stripSignBit(W.xorb(x,y)),
960 :     fn (NEG,POS) => NEG
961 :     | (POS,NEG) => NEG
962 :     | _ => POS)
963 :    
964 :     fun shiftAmount(w) = {bytes=W.div(w, i2w BN.lgBase),
965 :     bits=W.mod(w, i2w BN.lgBase)}
966 :    
967 :     (* left shift; just shift the digits, no special treatment for
968 :     * signed versus unsigned.
969 :     *)
970 :     fun <<(i as BI{digits=[],sign}, w) = i (* 0 << n = 0 *)
971 :     | <<(i as BI{digits,sign}, w) =
972 :     let val {bytes, bits} = shiftAmount w
973 :     fun pad(0w0, digits) = digits
974 :     | pad(n, digits) = pad(n-0w1, 0::digits)
975 :     in if bits = 0w0 then BI{sign=sign,digits=pad(bytes, digits)}
976 :     else
977 :     let val shift = i2w BN.lgBase - bits
978 :     fun shiftAll([], 0w0) = []
979 :     | shiftAll([], carry) = [w2i carry]
980 :     | shiftAll(x::xs, carry) =
981 :     let val x = i2w x
982 :     val digit =
983 :     stripSignBit(W.orb(carry, W.<<(x, bits)))
984 :     val carry' = W.>>(x, shift)
985 :     in w2i digit::shiftAll(xs, carry')
986 :     end
987 :     in BI{sign=sign,digits=shiftAll(pad(bytes, digits), 0w0)}
988 :     end
989 :     end
990 :    
991 :     (*
992 :     * Right shift
993 :     *)
994 :     fun ~>>(i as BI{digits=[],sign}, w) = i (* 0 ~>> n = n *)
995 :     | ~>>(i as BI{digits,sign}, w) =
996 :     let val {bytes, bits} = shiftAmount w
997 :     fun drop(0w0, i) = i
998 :     | drop(n, []) = []
999 :     | drop(n, x::xs) = drop(n-0w1, xs)
1000 :     val digits =
1001 :     if bits = 0w0 then drop(bytes, digits)
1002 :     else
1003 :     let val shift = i2w BN.lgBase - bits
1004 :     fun shiftAll [] = ([], 0w0)
1005 :     | shiftAll(x::xs) =
1006 :     let val (zs, borrow) = shiftAll xs
1007 :     val x = i2w x
1008 :     val z = w2i(W.orb(borrow, W.>>(x, bits)))
1009 :     val borrow' = stripSignBit(W.<<(x, shift))
1010 :     in case (z,zs) of
1011 :     (0, []) => ([], borrow') (* strip leading zero *)
1012 :     | _ => (z::zs, borrow')
1013 :     end
1014 :     val (zs, _) = shiftAll(drop(bytes, digits))
1015 :     in zs
1016 :     end
1017 :     in case digits of
1018 :     [] => zero
1019 :     | _ => BI{digits=digits, sign=sign}
1020 :     end
1021 :    
1022 :     end
1023 :    
1024 :    
1025 :     val notb = BitOps.notb
1026 :     val andb = BitOps.andb
1027 :     val orb = BitOps.orb
1028 :     val xorb = BitOps.xorb
1029 :     val << = BitOps.<<
1030 :     val ~>> = BitOps.~>>
1031 :    
1032 : jhr 1194 (* these are not in the BASIS signature, but they are useful since IntInf.int
1033 :     * is not a builtin type yet.
1034 :     *)
1035 :     fun == (BI{sign=s1, digits=d1}, BI{sign=s2, digits=d2}) =
1036 :     (s1 = s2) andalso BN.eq(d1, d2)
1037 :     fun != (BI{sign=s1, digits=d1}, BI{sign=s2, digits=d2}) =
1038 :     (s1 <> s2) orelse BN.neq(d1, d2)
1039 :    
1040 : monnier 26 end (* structure IntInf *)
1041 : monnier 411

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0