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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 651, Thu Jun 1 18:34:03 2000 UTC revision 1136, Tue Mar 12 19:44:02 2002 UTC
# Line 1  Line 1 
1  (*  (* probability.sml
  * Probability datatype (what the hell is this?)  
2   *   *
3   * -- Allen   * 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        exception BadProb
48    
49        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     type prob = W.word      fun normalize (0w0, _) = never
78          | normalize (n, d) = (case Word.compare(n, d)
79               of LESS => (case gcd(n, d)
80                     of 0w1 => PROB(n, d)
81                      | g => PROB(Word.div(n, g), Word.div(d, g))
82                    (* end case *))
83                | EQUAL => always
84                | GREATER => raise BadProb
85              (* end case *))
86    
87        fun prob (n, d) =
88              if (n > d) orelse (n < 0) orelse (d <= 0)
89                then raise Domain
90                else normalize(Word.fromInt n, Word.fromInt d)
91    
92        fun add (PROB(n1, d1), PROB(n2, d2)) = normalize(d2*n1 + d1*n2, d1*d2)
93    
94        fun sub (PROB(n1, d1), PROB(n2, d2)) = let
95              val n1' = d2*n1
96              val n2' = d1*n2
97              in
98                if (n1' < n2') then raise BadProb else normalize(n1'-n2', d1*d2)
99              end
100    
101        fun mul (PROB(n1, d1), PROB(n2, d2)) = normalize (n1*n2, d1*d2)
102    
103     val word = W.fromInt      fun divide (PROB(n, d), m) = if (m <= 0)
104              then raise BadProb
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)
115                    then raise BadProb
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     val <<   = W.<<      fun toString (PROB(0w0, _)) = "0"
131     val >>   = W.>>        | toString (PROB(_, 0w1)) = "1"
132     val op + = W.+        | toString (PROB(n, d)) = let
133     val op - = W.-            val toStr = Word.fmt StringCvt.DEC
134              in
135     infix << >>              concat [toStr n, "/", toStr d]
   
    val shift   = 0w16  
    val shift2  = 0w8  
    val one     = 0w1 << shift  
    val half    = one >> 0w1  
    val half'   = (0w1 << shift2) >> 0w1  
    val realOne = Real.fromInt(Word.toInt one)  
    val zero    = 0w0  
    val op <    = W.<  
    val op >    = W.>  
    val op >=   = W.>=  
    val op <=   = W.<=  
    val !=      = fn (i:word,j:word) => i <> j  
    val ==      = fn (i:word,j:word) => i = j  
    val compare = W.compare  
   
    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)  
136     end     end
137    
138        val op + = add
139        val op - = sub
140        val op * = mul
141        val op / = divide
142    
143  end  end
144    

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

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0