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