1 /*++
2 Copyright (c) 2012 Microsoft Corporation
3
4 Module Name:
5
6 factor_tactic.cpp
7
8 Abstract:
9
10 Polynomial factorization tactic.
11
12 Author:
13
14 Leonardo de Moura (leonardo) 2012-02-03
15
16 Revision History:
17
18 --*/
19 #include "tactic/tactical.h"
20 #include "ast/expr2polynomial.h"
21 #include "ast/rewriter/rewriter_def.h"
22
23 class factor_tactic : public tactic {
24
25 struct rw_cfg : public default_rewriter_cfg {
26 ast_manager & m;
27 arith_util m_util;
28 unsynch_mpq_manager m_qm;
29 polynomial::manager m_pm;
30 default_expr2polynomial m_expr2poly;
31 polynomial::factor_params m_fparams;
32 bool m_split_factors;
33
rw_cfgfactor_tactic::rw_cfg34 rw_cfg(ast_manager & _m, params_ref const & p):
35 m(_m),
36 m_util(_m),
37 m_pm(m.limit(), m_qm),
38 m_expr2poly(m, m_pm) {
39 updt_params(p);
40 }
41
updt_paramsfactor_tactic::rw_cfg42 void updt_params(params_ref const & p) {
43 m_split_factors = p.get_bool("split_factors", true);
44 m_fparams.updt_params(p);
45 }
46
mk_mulfactor_tactic::rw_cfg47 expr * mk_mul(unsigned sz, expr * const * args) {
48 SASSERT(sz > 0);
49 if (sz == 1)
50 return args[0];
51 return m_util.mk_mul(sz, args);
52 }
53
mk_zero_forfactor_tactic::rw_cfg54 expr * mk_zero_for(expr * arg) {
55 return m_util.mk_numeral(rational(0), m_util.is_int(arg));
56 }
57
58 // p1^k1 * p2^k2 = 0 --> p1*p2 = 0
mk_eqfactor_tactic::rw_cfg59 void mk_eq(polynomial::factors const & fs, expr_ref & result) {
60 expr_ref_buffer args(m);
61 expr_ref arg(m);
62 for (unsigned i = 0; i < fs.distinct_factors(); i++) {
63 m_expr2poly.to_expr(fs[i], true, arg);
64 args.push_back(arg);
65 }
66 result = m.mk_eq(mk_mul(args.size(), args.data()), mk_zero_for(arg));
67 }
68
69 // p1^k1 * p2^k2 = 0 --> p1 = 0 or p2 = 0
mk_split_eqfactor_tactic::rw_cfg70 void mk_split_eq(polynomial::factors const & fs, expr_ref & result) {
71 expr_ref_buffer args(m);
72 expr_ref arg(m);
73 for (unsigned i = 0; i < fs.distinct_factors(); i++) {
74 m_expr2poly.to_expr(fs[i], true, arg);
75 args.push_back(m.mk_eq(arg, mk_zero_for(arg)));
76 }
77 if (args.size() == 1)
78 result = args[0];
79 else
80 result = m.mk_or(args.size(), args.data());
81 }
82
flipfactor_tactic::rw_cfg83 decl_kind flip(decl_kind k) {
84 SASSERT(k == OP_LT || k == OP_GT || k == OP_LE || k == OP_GE);
85 switch (k) {
86 case OP_LT: return OP_GT;
87 case OP_LE: return OP_GE;
88 case OP_GT: return OP_LT;
89 case OP_GE: return OP_LE;
90 default:
91 UNREACHABLE();
92 return k;
93 }
94 }
95
96 // p1^{2*k1} * p2^{2*k2 + 1} >=< 0
97 // -->
98 // (p1^2)*p2 >=<0
mk_compfactor_tactic::rw_cfg99 void mk_comp(decl_kind k, polynomial::factors const & fs, expr_ref & result) {
100 SASSERT(k == OP_LT || k == OP_GT || k == OP_LE || k == OP_GE);
101 expr_ref_buffer args(m);
102 expr_ref arg(m);
103 for (unsigned i = 0; i < fs.distinct_factors(); i++) {
104 m_expr2poly.to_expr(fs[i], true, arg);
105 if (fs.get_degree(i) % 2 == 0)
106 arg = m_util.mk_power(arg, m_util.mk_numeral(rational(2), m_util.is_int(arg)));
107 args.push_back(arg);
108 }
109 expr * lhs = mk_mul(args.size(), args.data());
110 result = m.mk_app(m_util.get_family_id(), k, lhs, mk_zero_for(lhs));
111 }
112
113 // See mk_split_strict_comp and mk_split_nonstrict_comp
split_even_oddfactor_tactic::rw_cfg114 void split_even_odd(bool strict, polynomial::factors const & fs, expr_ref_buffer & even_eqs, expr_ref_buffer & odd_factors) {
115 expr_ref arg(m);
116 for (unsigned i = 0; i < fs.distinct_factors(); i++) {
117 m_expr2poly.to_expr(fs[i], true, arg);
118 if (fs.get_degree(i) % 2 == 0) {
119 expr * eq = m.mk_eq(arg, mk_zero_for(arg));
120 if (strict)
121 even_eqs.push_back(m.mk_not(eq));
122 else
123 even_eqs.push_back(eq);
124 }
125 else {
126 odd_factors.push_back(arg);
127 }
128 }
129 }
130
131 // Strict case
132 // p1^{2*k1} * p2^{2*k2 + 1} >< 0
133 // -->
134 // p1 != 0 and p2 >< 0
135 //
136 // Nonstrict
137 // p1^{2*k1} * p2^{2*k2 + 1} >=< 0
138 // -->
139 // p1 = 0 or p2 >=< 0
140 //
mk_split_compfactor_tactic::rw_cfg141 void mk_split_comp(decl_kind k, polynomial::factors const & fs, expr_ref & result) {
142 SASSERT(k == OP_LT || k == OP_GT || k == OP_LE || k == OP_GE);
143 bool strict = (k == OP_LT) || (k == OP_GT);
144 expr_ref_buffer args(m);
145 expr_ref_buffer odd_factors(m);
146 split_even_odd(strict, fs, args, odd_factors);
147 if (odd_factors.empty()) {
148 if (k == OP_LT) {
149 result = m.mk_false();
150 return;
151 }
152 if (k == OP_GE) {
153 result = m.mk_true();
154 return;
155 }
156 }
157 else {
158 args.push_back(m.mk_app(m_util.get_family_id(), k, mk_mul(odd_factors.size(), odd_factors.data()), mk_zero_for(odd_factors[0])));
159 }
160 SASSERT(!args.empty());
161 if (args.size() == 1)
162 result = args[0];
163 else if (strict)
164 result = m.mk_and(args.size(), args.data());
165 else
166 result = m.mk_or(args.size(), args.data());
167 }
168
factorfactor_tactic::rw_cfg169 br_status factor(func_decl * f, expr * lhs, expr * rhs, expr_ref & result) {
170 polynomial_ref p1(m_pm);
171 polynomial_ref p2(m_pm);
172 scoped_mpz d1(m_qm);
173 scoped_mpz d2(m_qm);
174 m_expr2poly.to_polynomial(lhs, p1, d1);
175 m_expr2poly.to_polynomial(rhs, p2, d2);
176 TRACE("factor_tactic_bug",
177 tout << "lhs: " << mk_ismt2_pp(lhs, m) << "\n";
178 tout << "p1: " << p1 << "\n";
179 tout << "d1: " << d1 << "\n";
180 tout << "rhs: " << mk_ismt2_pp(rhs, m) << "\n";
181 tout << "p2: " << p2 << "\n";
182 tout << "d2: " << d2 << "\n";);
183 scoped_mpz lcm(m_qm);
184 m_qm.lcm(d1, d2, lcm);
185 m_qm.div(lcm, d1, d1);
186 m_qm.div(lcm, d2, d2);
187 m_qm.neg(d2);
188 polynomial_ref p(m_pm);
189 p = m_pm.addmul(d1, m_pm.mk_unit(), p1, d2, m_pm.mk_unit(), p2);
190 if (is_const(p))
191 return BR_FAILED;
192 polynomial::factors fs(m_pm);
193 TRACE("factor_tactic_bug", tout << "p: " << p << "\n";);
194 m_pm.factor(p, fs, m_fparams);
195 SASSERT(fs.distinct_factors() > 0);
196 TRACE("factor_tactic_bug", tout << "factors:\n"; fs.display(tout); tout << "\n";);
197 if (fs.distinct_factors() == 1 && fs.get_degree(0) == 1)
198 return BR_FAILED;
199 if (m.is_eq(f)) {
200 if (m_split_factors)
201 mk_split_eq(fs, result);
202 else
203 mk_eq(fs, result);
204 }
205 else {
206 decl_kind k = f->get_decl_kind();
207 if (m_qm.is_neg(fs.get_constant()))
208 k = flip(k);
209
210 if (m_split_factors)
211 mk_split_comp(k, fs, result);
212 else
213 mk_comp(k, fs, result);
214 }
215 return BR_DONE;
216 }
217
reduce_appfactor_tactic::rw_cfg218 br_status reduce_app(func_decl * f, unsigned num, expr * const * args, expr_ref & result, proof_ref & result_pr) {
219 if (num != 2)
220 return BR_FAILED;
221 if (m.is_eq(f) && (m_util.is_arith_expr(args[0]) || m_util.is_arith_expr(args[1])) && (!m.is_bool(args[0])))
222 return factor(f, args[0], args[1], result);
223 if (f->get_family_id() != m_util.get_family_id())
224 return BR_FAILED;
225 switch (f->get_decl_kind()) {
226 case OP_LT:
227 case OP_GT:
228 case OP_LE:
229 case OP_GE:
230 return factor(f, args[0], args[1], result);
231 }
232 return BR_FAILED;
233 }
234 };
235
236 struct rw : public rewriter_tpl<rw_cfg> {
237 rw_cfg m_cfg;
238
rwfactor_tactic::rw239 rw(ast_manager & m, params_ref const & p):
240 rewriter_tpl<rw_cfg>(m, m.proofs_enabled(), m_cfg),
241 m_cfg(m, p) {
242 }
243 };
244
245 struct imp {
246 ast_manager & m;
247 rw m_rw;
248
impfactor_tactic::imp249 imp(ast_manager & _m, params_ref const & p):
250 m(_m),
251 m_rw(m, p) {
252 }
253
254
updt_paramsfactor_tactic::imp255 void updt_params(params_ref const & p) {
256 m_rw.cfg().updt_params(p);
257 }
258
operator ()factor_tactic::imp259 void operator()(goal_ref const & g,
260 goal_ref_buffer & result) {
261 tactic_report report("factor", *g);
262 bool produce_proofs = g->proofs_enabled();
263
264 expr_ref new_curr(m);
265 proof_ref new_pr(m);
266 unsigned size = g->size();
267 for (unsigned idx = 0; !g->inconsistent() && idx < size; idx++) {
268 expr * curr = g->form(idx);
269 m_rw(curr, new_curr, new_pr);
270 if (produce_proofs) {
271 proof * pr = g->pr(idx);
272 new_pr = m.mk_modus_ponens(pr, new_pr);
273 }
274 g->update(idx, new_curr, new_pr, g->dep(idx));
275 }
276 g->inc_depth();
277 result.push_back(g.get());
278 }
279 };
280
281 imp * m_imp;
282 params_ref m_params;
283 public:
factor_tactic(ast_manager & m,params_ref const & p)284 factor_tactic(ast_manager & m, params_ref const & p):
285 m_params(p) {
286 m_imp = alloc(imp, m, p);
287 }
288
translate(ast_manager & m)289 tactic * translate(ast_manager & m) override {
290 return alloc(factor_tactic, m, m_params);
291 }
292
~factor_tactic()293 ~factor_tactic() override {
294 dealloc(m_imp);
295 }
296
updt_params(params_ref const & p)297 void updt_params(params_ref const & p) override {
298 m_params = p;
299 m_imp->m_rw.cfg().updt_params(p);
300 }
301
collect_param_descrs(param_descrs & r)302 void collect_param_descrs(param_descrs & r) override {
303 r.insert("split_factors", CPK_BOOL,
304 "(default: true) apply simplifications such as (= (* p1 p2) 0) --> (or (= p1 0) (= p2 0)).");
305 polynomial::factor_params::get_param_descrs(r);
306 }
307
operator ()(goal_ref const & in,goal_ref_buffer & result)308 void operator()(goal_ref const & in,
309 goal_ref_buffer & result) override {
310 try {
311 (*m_imp)(in, result);
312 }
313 catch (z3_error & ex) {
314 throw ex;
315 }
316 catch (z3_exception & ex) {
317 throw tactic_exception(ex.msg());
318 }
319 }
320
cleanup()321 void cleanup() override {
322 imp * d = alloc(imp, m_imp->m, m_params);
323 std::swap(d, m_imp);
324 dealloc(d);
325 }
326
327
328 };
329
mk_factor_tactic(ast_manager & m,params_ref const & p)330 tactic * mk_factor_tactic(ast_manager & m, params_ref const & p) {
331 return clean(alloc(factor_tactic, m, p));
332 }
333
334
335
336