Chris@10: (*
Chris@10:  * Copyright (c) 1997-1999 Massachusetts Institute of Technology
Chris@10:  * Copyright (c) 2003, 2007-11 Matteo Frigo
Chris@10:  * Copyright (c) 2003, 2007-11 Massachusetts Institute of Technology
Chris@10:  *
Chris@10:  * This program is free software; you can redistribute it and/or modify
Chris@10:  * it under the terms of the GNU General Public License as published by
Chris@10:  * the Free Software Foundation; either version 2 of the License, or
Chris@10:  * (at your option) any later version.
Chris@10:  *
Chris@10:  * This program is distributed in the hope that it will be useful,
Chris@10:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@10:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Chris@10:  * GNU General Public License for more details.
Chris@10:  *
Chris@10:  * You should have received a copy of the GNU General Public License
Chris@10:  * along with this program; if not, write to the Free Software
Chris@10:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
Chris@10:  *
Chris@10:  *)
Chris@10: 
Chris@10: (*
Chris@10:  * the oracle decrees whether the sign of an expression should
Chris@10:  * be changed.
Chris@10:  *
Chris@10:  * Say the expression (A - B) appears somewhere.  Elsewhere in the
Chris@10:  * expression dag the expression (B - A) may appear.
Chris@10:  * The oracle determines which of the two forms is canonical.
Chris@10:  *
Chris@10:  * Algorithm: evaluate the expression at a random input, and
Chris@10:  * keep the expression with the positive sign.
Chris@10:  *)
Chris@10: 
Chris@10: let make_memoizer hash equal =
Chris@10:   let table = ref Assoctable.empty 
Chris@10:   in 
Chris@10:   (fun f k ->
Chris@10:     match Assoctable.lookup hash equal k !table with
Chris@10:       Some value -> value
Chris@10:     | None ->
Chris@10:         let value = f k in
Chris@10:         begin	
Chris@10:           table := Assoctable.insert hash k value !table;
Chris@10:           value
Chris@10:         end)
Chris@10: 
Chris@10: let almost_equal x y = 
Chris@10:   let epsilon = 1.0E-8 in
Chris@10:   (abs_float (x -. y) < epsilon) ||
Chris@10:   (abs_float (x -. y) < epsilon *. (abs_float x +. abs_float y)) 
Chris@10: 
Chris@10: let absid = make_memoizer
Chris@10:     (fun x -> Expr.hash_float (abs_float x))
Chris@10:     (fun a b -> almost_equal a b || almost_equal (-. a) b)
Chris@10:     (fun x -> x)
Chris@10: 
Chris@10: let make_random_oracle () = make_memoizer 
Chris@10:     Variable.hash 
Chris@10:     Variable.same
Chris@10:     (fun _ -> (float (Random.bits())) /. 1073741824.0)
Chris@10: 
Chris@10: let the_random_oracle = make_random_oracle ()
Chris@10: 
Chris@10: let sum_list l = List.fold_right (+.) l 0.0
Chris@10: 
Chris@10: let eval_aux random_oracle =
Chris@10:   let memoizing = make_memoizer Expr.hash (==) in
Chris@10:   let rec eval x = 
Chris@10:     memoizing
Chris@10:       (function
Chris@10: 	| Expr.Num x -> Number.to_float x
Chris@10: 	| Expr.NaN x -> Expr.transcendent_to_float x
Chris@10: 	| Expr.Load v -> random_oracle v
Chris@10: 	| Expr.Store (v, x) -> eval x
Chris@10: 	| Expr.Plus l -> sum_list (List.map eval l)
Chris@10: 	| Expr.Times (a, b) -> (eval a) *. (eval b)
Chris@10: 	| Expr.CTimes (a, b) -> 
Chris@10: 	    1.098612288668109691395245236 +. 
Chris@10: 	       1.609437912434100374600759333 *. (eval a) *. (eval b)
Chris@10: 	| Expr.CTimesJ (a, b) -> 
Chris@10: 	    0.9102392266268373936142401657 +. 
Chris@10: 	      0.6213349345596118107071993881 *. (eval a) *. (eval b)
Chris@10: 	| Expr.Uminus x -> -. (eval x))
Chris@10:       x
Chris@10:   in eval
Chris@10: 
Chris@10: let eval = eval_aux the_random_oracle
Chris@10: 
Chris@10: let should_flip_sign node = 
Chris@10:   let v = eval node in
Chris@10:   let v' = absid v in
Chris@10:   not (almost_equal v v')
Chris@10: 
Chris@10: (*
Chris@10:  * determine with high probability if two expressions are equal.
Chris@10:  *
Chris@10:  * The test is randomized: if the two expressions have the
Chris@10:  * same value for NTESTS random inputs, then they are proclaimed
Chris@10:  * equal.  (Note that two distinct linear functions L1(x0, x1, ..., xn)
Chris@10:  * and L2(x0, x1, ..., xn) have the same value with probability
Chris@10:  * 0 for random x's, and thus this test is way more paranoid than
Chris@10:  * necessary.)
Chris@10:  *)
Chris@10: let likely_equal a b =
Chris@10:   let tolerance = 1.0e-8
Chris@10:   and ntests = 20
Chris@10:   in
Chris@10:   let rec loop n =
Chris@10:     if n = 0 then 
Chris@10:       true
Chris@10:     else
Chris@10:       let r = make_random_oracle () in
Chris@10:       let va = eval_aux r a
Chris@10:       and vb = eval_aux r b
Chris@10:       in
Chris@10:       if (abs_float (va -. vb)) > 
Chris@10: 	   tolerance *. (abs_float va +. abs_float vb +. 0.0001)
Chris@10:       then
Chris@10: 	false
Chris@10:       else
Chris@10: 	loop (n - 1)
Chris@10:   in
Chris@10:   match (a, b) with
Chris@10: 
Chris@10:     (* 
Chris@10:      * Because of the way eval is constructed, we have
Chris@10:      *     eval (Store (v, x)) == eval x
Chris@10:      * However, we never consider the two expressions equal
Chris@10:      *)
Chris@10:   | (Expr.Store _, _) -> false
Chris@10:   | (_, Expr.Store _) -> false
Chris@10: 
Chris@10:     (*
Chris@10:      * Expressions of the form ``Uminus (Store _)''
Chris@10:      * are artifacts of algsimp
Chris@10:      *)
Chris@10:   | ((Expr.Uminus (Expr.Store _)), _) -> false
Chris@10:   | (_, Expr.Uminus (Expr.Store _)) -> false
Chris@10: 
Chris@10:   | _ -> loop ntests
Chris@10: 
Chris@10: let hash x =
Chris@10:   let f = eval x in
Chris@10:   truncate (f *. 65536.0)