Home My Page Projects Code Snippets Project Openings diderot

# SCM Repository

[diderot] View of /trunk/src/compiler/fields/rational.sml
 [diderot] / trunk / src / compiler / fields / rational.sml

# View of /trunk/src/compiler/fields/rational.sml

Thu Jun 24 13:43:16 2010 UTC (9 years, 3 months ago) by jhr
Original Path: trunk/src/compiler/common/rational.sml
File size: 3194 byte(s)
```  Fix bugs
```
```(* rational.sml
*
* COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
*
* Support for rational numbers.
*)

signature RATIONAL =
sig

eqtype rat

val ~ : rat -> rat
val + : rat * rat -> rat
val - : rat * rat -> rat
val * : rat * rat -> rat
val div : rat * rat -> rat

(*
val min : rat * rat -> rat
val max : rat * rat -> rat
*)
val abs : rat -> rat

val sign : rat -> int
val sameSign : rat * rat -> bool

(*
val > : rat * rat -> bool
val >= : rat * rat -> bool
val < : rat * rat -> bool
val <= : rat * rat -> bool

val compare : rat * rat -> order
*)

val / : LargeInt.int * LargeInt.int -> rat

val fromInt : int -> rat
val fromLargeInt : LargeInt.int -> rat

val toString : rat -> string

end

structure Rational :> RATIONAL =
struct

structure II = IntInf

(* invariants:
*   denom > 0
*   gcd(num, denom) = 1
*)
datatype rat = R of {num : II.int, denom : II.int}

val zero = R{num=0, denom=1}

fun gcd (a : II.int, 0) = a
| gcd (a, b) = if (a > b)
then gcd(a-b, b)
else gcd(a, b-a)

fun mkRat (0, _) = zero
| mkRat (n, 1) = R{num=n, denom=1}
| mkRat (num, denom) = let
val d = gcd(II.abs num, denom)
in
R{num = num div d, denom = denom div d}
end

fun neg (R{num, denom}) = R{num = ~num, denom = denom}

fun add (R{num=n1, denom=d1}, R{num=n2, denom=d2}) = let
val d = gcd(d1, d2)
val a1 = d2 div d
val a2 = d1 div d
val lcm = a1 * d1
in
mkRat (a1*n1 + a2*n2, lcm)
end

fun sub (R{num=n1, denom=d1}, R{num=n2, denom=d2}) = let
val d = gcd(d1, d2)
val a1 = d2 div d
val a2 = d1 div d
val lcm = a1 * d1
in
mkRat (a1*n1 - a2*n2, lcm)
end

fun mul (R{num=n1, denom=d1}, R{num=n2, denom=d2}) =
mkRat (n1*n2, d1*d2)

fun divide (_, R{num=0, ...}) = raise Div
| divide (R{num=n1, denom=d1}, R{num=n2, denom=d2}) = let
val n = n1 * d2
val d = n2 * d1
in
if (d < 0) then mkRat(~n, ~d) else mkRat(n, d)
end

fun abs (R{num, denom}) = R{num = II.abs num, denom = denom}

fun sign (R{num, ...}) = II.sign num

fun sameSign (R{num=n1, ...}, R{num=n2, ...}) = II.sameSign(n1, n2)

(*
val > : rat * rat -> bool
val >= : rat * rat -> bool
val < : rat * rat -> bool
val <= : rat * rat -> bool

val compare : rat * rat -> order

val min : rat * rat -> rat
val max : rat * rat -> rat
*)

fun op / (_, 0) = raise Div
| op / (a, b) = if (b < 0)
then mkRat(~a, ~b)
else mkRat(a, b)

fun fromInt n = mkRat(II.fromInt n, 1)
fun fromLargeInt n = mkRat(n, 1)

fun toString (R{num, denom = 1}) = II.toString num
| toString (R{num, denom}) =
String.concat[II.toString num, "/", II.toString denom]

(* bind operators *)
val ~ : rat -> rat = neg
val op + : rat * rat -> rat = add
val op - : rat * rat -> rat = sub
val op * : rat * rat -> rat = mul
val op div : rat * rat -> rat = divide
(*
val > : rat * rat -> bool
val >= : rat * rat -> bool
val < : rat * rat -> bool
val <= : rat * rat -> bool
*)

end
```