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

# SCM Repository

[smlnj] Diff of /MLRISC/releases/release-110.84/library/probability.sml
 [smlnj] / MLRISC / releases / release-110.84 / library / probability.sml

# Diff of /MLRISC/releases/release-110.84/library/probability.sml

sml/branches/SMLNJ/src/MLRISC/library/probability.sml revision 245, Sat Apr 17 18:47:12 1999 UTC sml/trunk/src/MLRISC/library/probability.sml revision 1136, Tue Mar 12 19:44:02 2002 UTC
# Line 1  Line 1
1    (* probability.sml
2     *
3     * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
4     *
5     * A representation of probabilities for branch prediction.
6     *)
7
8  signature PROBABILITY =  signature PROBABILITY =
9  sig  sig
eqtype prob
10
11     val prob     : int * int -> prob      type prob
12     val zero     : prob
13     val one      : prob      exception BadProb
14     val <        : prob * prob -> bool
15     val >        : prob * prob -> bool      val never : prob    (* 0% probability *)
16     val >=       : prob * prob -> bool      val unlikely : prob (* very close to 0% *)
17     val <=       : prob * prob -> bool      val likely : prob   (* very close to 100% *)
18     val !=       : prob * prob -> bool      val always : prob   (* 100% probability *)
19     val ==       : prob * prob -> bool
20     val compare  : prob * prob -> order      val prob : (int * int) -> prob
21     val avg      : (prob * int) list -> int      val fromFreq : int list -> prob list
22     val avg_prob : (prob * prob) list -> prob
23     val +        : prob * prob -> prob      val + : (prob * prob) -> prob
24     val -        : prob * prob -> prob      val - : (prob * prob) -> prob
25     val *        : prob * real -> prob      val * : (prob * prob) -> prob
26     val /        : prob * real -> prob      val / : (prob * int) -> prob
27     val toString : prob -> string
28        val percent : int -> prob
29
30     val toReal   : prob -> real     val toReal   : prob -> real
31     val fromReal : real -> prob      val toString : prob -> string
32
33  end  end
34
35  structure Probability :> PROBABILITY =  structure Probability :> PROBABILITY =
36  struct  struct
37
38     structure W = Word    (* Probabilities are represented as positive rationals.  Zero is
39       * represented as PROB(0w0, 0w0) and one is represented as
40       * PROB(0w1, 0w1).  There are several invariants about PROB(n, d):
41       *    1) n <= d
42       *    2) if n = 0w0, then d = 0w0 (uniqueness of zero)
43       *    3) if d = 0w1, then n = 0w1 (uniqueness of one)
44       *)
45        datatype prob = PROB of (word * word)
46
47     type prob = W.word      exception BadProb
48
49     val word = W.fromInt      val never = PROB(0w0, 0w0)
50        val unlikely = PROB(0w1, 0w1000)
51        val likely = PROB(0w999, 0w1000)
52        val always = PROB(0w1, 0w1)
53
54      (* Fast GCD on words.  This algorithm is based on the following
55       * observations:
56       *    - If u and v are both even, then gcd(u, v) = 2*gcd(u/2, v/2)
57       *    - If u is even and v is odd, then gcd(u, v) = gcd(u/2, v)
58       *    - If both are odd, then gcd(u, v) = gcd(abs(u-v), v)
59       *)
60        fun gcd (u : word, v : word) = let
61              fun isEven x = (Word.andb(x, 0w1) = 0w0)
62              fun divBy2 x = Word.>>(x, 0w1)
63              fun lp1 (g, u, v) =
64                    if isEven(Word.orb(u, v))
65                      then lp1 (Word.<<(g, 0w1), divBy2 u, divBy2 v)
66                      else lp2 (g, u, v)
67              and lp2 (g, 0w0, v) = g*v
68                | lp2 (g, u, v) =
69                    if (isEven u) then lp2 (g, divBy2 u, v)
70                    else if (isEven v) then lp2 (g, u, divBy2 v)
71                    else if (u < v) then lp2 (g, u, divBy2(v-u))
72                    else lp2 (g, divBy2(u-v), v)
73              in
74                lp1 (0w1, u, v)
75              end
76
77     val <<   = W.<<      fun normalize (0w0, _) = never
78     val >>   = W.>>        | normalize (n, d) = (case Word.compare(n, d)
79     val op + = W.+             of LESS => (case gcd(n, d)
80     val op - = W.-                   of 0w1 => PROB(n, d)
81                      | g => PROB(Word.div(n, g), Word.div(d, g))
82     infix << >>                  (* end case *))
83                | EQUAL => always
84     val shift   = 0w16              | GREATER => raise BadProb
85     val shift2  = 0w8            (* end case *))
86     val one     = 0w1 << shift
87     val half    = one >> 0w1      fun prob (n, d) =
88     val half'   = (0w1 << shift2) >> 0w1            if (n > d) orelse (n < 0) orelse (d <= 0)
89     val realOne = Real.fromInt(Word.toInt one)              then raise Domain
90     val zero    = 0w0              else normalize(Word.fromInt n, Word.fromInt d)
91     val op <    = W.<
92     val op >    = W.>      fun add (PROB(n1, d1), PROB(n2, d2)) = normalize(d2*n1 + d1*n2, d1*d2)
93     val op >=   = W.>=
94     val op <=   = W.<=      fun sub (PROB(n1, d1), PROB(n2, d2)) = let
95     val !=      = fn (i:word,j:word) => i <> j            val n1' = d2*n1
96     val ==      = fn (i:word,j:word) => i = j            val n2' = d1*n2
97     val compare = W.compare            in
98                if (n1' < n2') then raise BadProb else normalize(n1'-n2', d1*d2)
fun prob (x,y)   =
let val h = word y
in W.div((word x << shift) + (h >> 0w1),h) end
fun fromReal r   = Word.fromInt(Real.round(r * realOne))
fun toReal p     = Real.fromInt(Word.toInt p) / realOne
fun toString p   = Real.toString(Real.fromInt(
Real.round(toReal p * 100.0))/100.0)

fun p * r = fromReal(Real.*(toReal p, r))
fun p / r = fromReal(Real./(toReal p, r))

fun avg [] = 0
| avg l  =
let fun f([],s,n)       = (s,n)
| f((p,i)::l,s,n) = f(l,W.*(p,word i) + s,n+0w1)
val (sum,n) = f(l,zero,0w0)
in  Word.toInt(W.div(sum,n))
end

fun avg_prob [] = zero
| avg_prob l =
let fun f([],s,n)       = (s,n)
| f((p,i)::l,s,n) = f(l,W.*((p+half')>>shift2,(i+half')>>shift2) + s,
n+0w1)
val (sum,n) = f(l,zero,0w0)
in  W.div(sum,n)
99     end     end
100
101        fun mul (PROB(n1, d1), PROB(n2, d2)) = normalize (n1*n2, d1*d2)
102
103        fun divide (PROB(n, d), m) = if (m <= 0)
105              else if (n = 0w0) then never
106              else normalize(n, d * Word.fromInt m)
107
108        fun percent n =
109              if (n < 0) then raise BadProb
110              else normalize(Word.fromInt n, 0w100)
111
112        fun fromFreq l = let
113              fun sum ([], tot) = tot
114                | sum (w::r, tot) = if (w < 0)
116                    else sum(r, Word.fromInt w + tot)
117              val tot = sum (l, 0w0)
118              in
119                List.map (fn w => normalize(Word.fromInt w, tot)) l
120              end
121
122        fun toReal (PROB(0w0, _)) = 0.0
123          | toReal (PROB(_, 0w1)) = 1.0
124          | toReal (PROB(n, d)) = let
125              fun toReal n = Real.fromLargeInt(Word.toLargeIntX n)
126              in
127                toReal n / toReal d
128              end
129
130        fun toString (PROB(0w0, _)) = "0"
131          | toString (PROB(_, 0w1)) = "1"
132          | toString (PROB(n, d)) = let
133              val toStr = Word.fmt StringCvt.DEC
134              in
135                concat [toStr n, "/", toStr d]
136              end
137
138        val op + = add
139        val op - = sub
140        val op * = mul
141        val op / = divide
142
143  end  end
144
(*
* \$Log\$
*)

Legend:
 Removed from v.245 changed lines Added in v.1136