src/Provers/Arith/fast_lin_arith.ML
changeset 23520 483fe92f00c1
parent 23297 06f108974fa1
child 23577 c5b93c69afd3
equal deleted inserted replaced
23519:a4ffa756d8eb 23520:483fe92f00c1
   183 (* If nth rs v < 0, le should be negated.
   183 (* If nth rs v < 0, le should be negated.
   184    Instead this swap is taken into account in ratrelmin2.
   184    Instead this swap is taken into account in ratrelmin2.
   185 *)
   185 *)
   186 
   186 
   187 fun ratrelmin2 (x as (r, ler), y as (s, les)) =
   187 fun ratrelmin2 (x as (r, ler), y as (s, les)) =
   188   case Rat.cmp (r, s)
   188   case Rat.ord (r, s)
   189    of EQUAL => (r, (not ler) andalso (not les))
   189    of EQUAL => (r, (not ler) andalso (not les))
   190     | LESS => x
   190     | LESS => x
   191     | GREATER => y;
   191     | GREATER => y;
   192 
   192 
   193 fun ratrelmax2 (x as (r, ler), y as (s, les)) =
   193 fun ratrelmax2 (x as (r, ler), y as (s, les)) =
   194   case Rat.cmp (r, s)
   194   case Rat.ord (r, s)
   195    of EQUAL => (r, ler andalso les)
   195    of EQUAL => (r, ler andalso les)
   196     | LESS => y
   196     | LESS => y
   197     | GREATER => x;
   197     | GREATER => x;
   198 
   198 
   199 val ratrelmin = foldr1 ratrelmin2;
   199 val ratrelmin = foldr1 ratrelmin2;
   207   in Rat.add r (if up then nth else Rat.neg nth) end;
   207   in Rat.add r (if up then nth else Rat.neg nth) end;
   208 
   208 
   209 fun ratmiddle (r, s) = Rat.mult (Rat.add r s) (Rat.inv Rat.two);
   209 fun ratmiddle (r, s) = Rat.mult (Rat.add r s) (Rat.inv Rat.two);
   210 
   210 
   211 fun choose2 d ((lb, exactl), (ub, exactu)) =
   211 fun choose2 d ((lb, exactl), (ub, exactu)) =
   212   let val ord = Rat.cmp_zero lb in
   212   let val ord = Rat.sign lb in
   213   if (ord = LESS orelse exactl) andalso (ord = GREATER orelse exactu)
   213   if (ord = LESS orelse exactl) andalso (ord = GREATER orelse exactu)
   214     then Rat.zero
   214     then Rat.zero
   215     else if not d then
   215     else if not d then
   216       if ord = GREATER
   216       if ord = GREATER
   217         then if exactl then lb else ratmiddle (lb, ub)
   217         then if exactl then lb else ratmiddle (lb, ub)
   235 
   235 
   236 fun elim1 v x =
   236 fun elim1 v x =
   237   map (fn (a,le,bs) => (Rat.add a (Rat.neg (Rat.mult (nth bs v) x)), le,
   237   map (fn (a,le,bs) => (Rat.add a (Rat.neg (Rat.mult (nth bs v) x)), le,
   238                         nth_map v (K Rat.zero) bs));
   238                         nth_map v (K Rat.zero) bs));
   239 
   239 
   240 fun single_var v (_, _, cs) = case filter_out (curry (op =) EQUAL o Rat.cmp_zero) cs
   240 fun single_var v (_, _, cs) = case filter_out (curry (op =) EQUAL o Rat.sign) cs
   241  of [x] => x =/ nth cs v
   241  of [x] => x =/ nth cs v
   242   | _ => false;
   242   | _ => false;
   243 
   243 
   244 (* The base case:
   244 (* The base case:
   245    all variables occur only with positive or only with negative coefficients *)
   245    all variables occur only with positive or only with negative coefficients *)
   246 fun pick_vars discr (ineqs,ex) =
   246 fun pick_vars discr (ineqs,ex) =
   247   let val nz = filter_out (fn (_,_,cs) => forall (curry (op =) EQUAL o Rat.cmp_zero) cs) ineqs
   247   let val nz = filter_out (fn (_,_,cs) => forall (curry (op =) EQUAL o Rat.sign) cs) ineqs
   248   in case nz of [] => ex
   248   in case nz of [] => ex
   249      | (_,_,cs) :: _ =>
   249      | (_,_,cs) :: _ =>
   250        let val v = find_index (not o curry (op =) EQUAL o Rat.cmp_zero) cs
   250        let val v = find_index (not o curry (op =) EQUAL o Rat.sign) cs
   251            val d = nth discr v;
   251            val d = nth discr v;
   252            val pos = not (Rat.cmp_zero (nth cs v) = LESS);
   252            val pos = not (Rat.sign (nth cs v) = LESS);
   253            val sv = filter (single_var v) nz;
   253            val sv = filter (single_var v) nz;
   254            val minmax =
   254            val minmax =
   255              if pos then if d then Rat.roundup o fst o ratrelmax
   255              if pos then if d then Rat.roundup o fst o ratrelmax
   256                          else ratexact true o ratrelmax
   256                          else ratexact true o ratrelmax
   257                     else if d then Rat.rounddown o fst o ratrelmin
   257                     else if d then Rat.rounddown o fst o ratrelmin