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

revision 1136, Tue Mar 12 19:44:02 2002 UTC revision 1153, Wed Mar 20 19:04:04 2002 UTC
# Line 24  Line 24
24      val - : (prob * prob) -> prob      val - : (prob * prob) -> prob
25      val * : (prob * prob) -> prob      val * : (prob * prob) -> prob
26      val / : (prob * int) -> prob      val / : (prob * int) -> prob
27        val not : prob -> prob              (* not p == always - p *)
28
29      val percent : int -> prob      val percent : int -> prob
30
31      (* combine a conditional branch probability (trueProb) with a
32       * prediction heuristic (takenProb) using Dempster-Shafer theory.
33       *)
34        val combineProb2 : {trueProb : prob, takenProb : prob} -> {t : prob, f : prob}
35
36      val toReal : prob -> real      val toReal : prob -> real
37      val toString : prob -> string      val toString : prob -> string
38
# Line 46  Line 52
52
54
55      val never = PROB(0w0, 0w0)      val never = PROB(0w0, 0w1)
56      val unlikely = PROB(0w1, 0w1000)      val unlikely = PROB(0w1, 0w1000)
57      val likely = PROB(0w999, 0w1000)      val likely = PROB(0w999, 0w1000)
58      val always = PROB(0w1, 0w1)      val always = PROB(0w1, 0w1)
# Line 135  Line 141
141              concat [toStr n, "/", toStr d]              concat [toStr n, "/", toStr d]
142            end            end
143
144      (* combine a conditional branch probability (trueProb) with a
145       * prediction heuristic (takenProb) using Dempster-Shafer theory.
146       * The basic equations (from Wu-Larus 1994) are:
147       *    t = trueProb*takenProb / d
148       *    f = ((1-trueProb)*(1-takenProb)) / d
149       * where
150       *    d = trueProb*takenProb + ((1-trueProb)*(1-takenProb))
151       *)
152        fun combineProb2 {trueProb=PROB(n1, d1), takenProb=PROB(n2, d2)} = let
153            (* compute sd/sn, where
154             *    sn/sd = (trueProb*takenProb) + (1-trueProb)*(1-takenProb)
155             *)
156              val d12 = d1*d2
157              val n12 = n1*n2
158              val (sn, sd) = let
159                    val n = d12 + 0w2*n12 - (d2*n1) - (d1*n2)
160                    in
161                      (d12, n)
162                    end
163            (* compute the true probability *)
164              val t as PROB(tn, td) = normalize(n12*sn, d12*sd)
165              val maxDenom = 0wx8000
166              val t as PROB(tn, td) = if td > maxDenom
167                    then let
168                    (* round down a bit to avoid future overflow *)
169                      fun lp (d, i) = let
170                            val d' = Word.>>(d, 0w1)
171                            in
172                              if (d' > maxDenom) then lp(d', i+0w1) else (d', i)
173                            end
174                      val (d, i) = lp(td, 0w1)
175                      val n = Word.>>(tn, i)
176                      in
177                        PROB(if n > 0w0 then n else 0w1, d)
178                      end
179                    else t
180            (* compute the false probability *)
181              val f = PROB(td-tn, td)
182              in
183                {t = t, f = f}
184              end
185
186        fun not (PROB(n, d)) = PROB(d-n, n)
187