1(* Author: Michael Norrish *)
2
3(* very simple-minded implementation of arbitrary precision natural
4   numbers *)
5
6   (* use "Arbnumcore.sig"; use "Arbnumcore.sml"; *)
7
8structure Arbnumcore :> Arbnumcore =
9struct
10
11open IntInf
12
13type num = int
14
15val zero = 0
16val one = 1
17val two = 2
18
19fun times2 x = 2 * x
20fun div2 x = x div 2
21fun mod2 x = x mod 2
22fun pow (x, y) = IntInf.pow (x, IntInf.toInt y)
23val log2 = IntInf.fromInt o IntInf.log2
24
25fun plus1 x = x + 1
26fun plus2 x = x + 2
27fun less1 x = if x = 0 then raise Fail "Can't take one off zero" else x - 1
28fun less2 x = if x < 2 then raise Fail "Can't take one off zero" else x - 2
29
30fun toBinString x = fmt StringCvt.BIN x
31fun toOctString x = fmt StringCvt.OCT x
32fun toHexString x = fmt StringCvt.HEX x
33
34(*
35  val fromString  : string -> num (* decimal *)
36  val genFromString : StringCvt.radix -> string -> num
37  val fromHexString : string -> num
38  val fromOctString : string -> num
39  val fromBinString : string -> num
40*)
41
42local
43   val radix = fn StringCvt.HEX => "HEX"
44                | StringCvt.OCT => "OCT"
45                | StringCvt.BIN => "BIN"
46                | StringCvt.DEC => "DEC"
47   fun err rdx = Fail ("String not " ^ radix rdx)
48in
49   fun genFromString rdx s =
50      case IntInf.scan rdx Substring.getc (Substring.full s) of
51         SOME (i, r) => if Substring.size r = 0 then i else raise (err rdx)
52       | _ => raise (err rdx)
53   val fromHexString = genFromString StringCvt.HEX
54   val fromOctString = genFromString StringCvt.OCT
55   val fromBinString = genFromString StringCvt.BIN
56   val fromString = genFromString StringCvt.DEC
57end
58
59fun fromLargeInt n = if n < 0 then raise Overflow else n
60fun fromInt n = if Int.< (n, 0) then raise Overflow else IntInf.fromInt n
61
62val toInt = IntInf.toInt
63fun toLargeInt n = n
64
65fun floor x =
66   let
67      val y = Real.toLargeInt IEEEReal.TO_NEGINF x
68   in
69      if y < 0 then raise Overflow else y
70   end
71
72val toReal = Real.fromLargeInt
73
74fun asList x = [toInt x]
75
76fun (x - y) = if x < y then 0 else IntInf.- (x, y)
77
78val divmod = divMod
79
80local
81   fun gcd' i j =
82      let
83         val r = i mod j
84      in
85         if r = 0 then j else gcd' j r
86      end
87in
88   fun gcd (i, j) =
89      if i = 0
90         then j
91      else if j = 0
92         then i
93      else if i < j
94         then gcd' j i
95      else gcd' i j
96end
97
98(* Basic Integer square root *)
99
100fun isqrt n =
101   if n < two
102      then n
103   else let
104           fun iter a =
105              let
106                 val a2 = a * a
107              in
108                 if a2 <= n andalso n <= a2 + times2 a
109                    then a
110                 else iter (div2 ((a2 + n) div a))
111              end
112        in
113           iter one
114        end
115
116end
117