Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
mult.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 /*
39 * Bounds consistent multiplication
40 *
41 */
42 Actor*
44 return new (home) MultBnd(home,*this);
45 }
46
49 if (pos(x0)) {
50 if (pos(x1) || pos(x2)) goto rewrite_ppp;
51 if (neg(x1) || neg(x2)) goto rewrite_pnn;
52 goto prop_pxx;
53 }
54 if (neg(x0)) {
55 if (neg(x1) || pos(x2)) goto rewrite_nnp;
56 if (pos(x1) || neg(x2)) goto rewrite_npn;
57 goto prop_nxx;
58 }
59 if (pos(x1)) {
60 if (pos(x2)) goto rewrite_ppp;
61 if (neg(x2)) goto rewrite_npn;
62 goto prop_xpx;
63 }
64 if (neg(x1)) {
65 if (pos(x2)) goto rewrite_nnp;
66 if (neg(x2)) goto rewrite_pnn;
67 goto prop_xnx;
68 }
69
70 assert(any(x0) && any(x1));
71 GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
72 mll(x0.min(),x1.min()))));
73 GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
74 mll(x0.max(),x1.min()))));
75
76 if (x0.assigned()) {
77 assert((x0.val() == 0) && (x2.val() == 0));
78 return home.ES_SUBSUMED(*this);
79 }
80
81 if (x1.assigned()) {
82 assert((x1.val() == 0) && (x2.val() == 0));
83 return home.ES_SUBSUMED(*this);
84 }
85
86 return ES_NOFIX;
87
88 prop_xpx:
89 std::swap(x0,x1);
90 prop_pxx:
91 assert(pos(x0) && any(x1) && any(x2));
92
93 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
94 GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
95
96 if (pos(x2)) goto rewrite_ppp;
97 if (neg(x2)) goto rewrite_pnn;
98
101
102 if (x0.assigned() && x1.assigned()) {
103 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
104 return home.ES_SUBSUMED(*this);
105 }
106
107 return ES_NOFIX;
108
109 prop_xnx:
110 std::swap(x0,x1);
111 prop_nxx:
112 assert(neg(x0) && any(x1) && any(x2));
113
114 GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
115 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
116
117 if (pos(x2)) goto rewrite_nnp;
118 if (neg(x2)) goto rewrite_npn;
119
122
123 if (x0.assigned() && x1.assigned()) {
124 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
125 return home.ES_SUBSUMED(*this);
126 }
127
128 return ES_NOFIX;
129
130 rewrite_ppp:
132 ::post(home(*this),x0,x1,x2)));
133 rewrite_nnp:
135 ::post(home(*this),MinusView(x0),MinusView(x1),x2)));
136 rewrite_pnn:
137 std::swap(x0,x1);
138 rewrite_npn:
140 ::post(home(*this),MinusView(x0),x1,MinusView(x2))));
141 }
142
145 if (x0 == x1) {
146 SqrOps ops;
147 return PowBnd<SqrOps>::post(home,x0,x2,ops);
148 }
149 if (x0 == x2)
151 if (x1 == x2)
153 if (pos(x0)) {
154 if (pos(x1) || pos(x2)) goto post_ppp;
155 if (neg(x1) || neg(x2)) goto post_pnn;
156 } else if (neg(x0)) {
157 if (neg(x1) || pos(x2)) goto post_nnp;
158 if (pos(x1) || neg(x2)) goto post_npn;
159 } else if (pos(x1)) {
160 if (pos(x2)) goto post_ppp;
161 if (neg(x2)) goto post_npn;
162 } else if (neg(x1)) {
163 if (pos(x2)) goto post_nnp;
164 if (neg(x2)) goto post_pnn;
165 }
166 {
167 long long int a = mll(x0.min(),x1.min());
168 long long int b = mll(x0.min(),x1.max());
169 long long int c = mll(x0.max(),x1.min());
170 long long int d = mll(x0.max(),x1.max());
171 GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
172 GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
173 (void) new (home) MultBnd(home,x0,x1,x2);
174 }
175 return ES_OK;
176
177 post_ppp:
179 ::post(home,x0,x1,x2);
180 post_nnp:
183 post_pnn:
184 std::swap(x0,x1);
185 post_npn:
188 }
189
190
191
192 /*
193 * Domain consistent multiplication
194 *
195 */
196 Actor*
198 return new (home) MultDom(home,*this);
199 }
200
202 MultDom::cost(const Space&, const ModEventDelta& med) const {
203 if (IntView::me(med) == ME_INT_DOM)
205 else
207 }
208
211 if (IntView::me(med) != ME_INT_DOM) {
212 if (pos(x0)) {
213 if (pos(x1) || pos(x2)) goto rewrite_ppp;
214 if (neg(x1) || neg(x2)) goto rewrite_pnn;
215 goto prop_pxx;
216 }
217 if (neg(x0)) {
218 if (neg(x1) || pos(x2)) goto rewrite_nnp;
219 if (pos(x1) || neg(x2)) goto rewrite_npn;
220 goto prop_nxx;
221 }
222 if (pos(x1)) {
223 if (pos(x2)) goto rewrite_ppp;
224 if (neg(x2)) goto rewrite_npn;
225 goto prop_xpx;
226 }
227 if (neg(x1)) {
228 if (pos(x2)) goto rewrite_nnp;
229 if (neg(x2)) goto rewrite_pnn;
230 goto prop_xnx;
231 }
232
233 assert(any(x0) && any(x1));
234 GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
235 mll(x0.min(),x1.min()))));
236 GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
237 mll(x0.max(),x1.min()))));
238
239 if (x0.assigned()) {
240 assert((x0.val() == 0) && (x2.val() == 0));
241 return home.ES_SUBSUMED(*this);
242 }
243
244 if (x1.assigned()) {
245 assert((x1.val() == 0) && (x2.val() == 0));
246 return home.ES_SUBSUMED(*this);
247 }
248
249 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
250
251 prop_xpx:
252 std::swap(x0,x1);
253 prop_pxx:
254 assert(pos(x0) && any(x1) && any(x2));
255
256 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
257 GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
258
259 if (pos(x2)) goto rewrite_ppp;
260 if (neg(x2)) goto rewrite_pnn;
261
264
265 if (x0.assigned() && x1.assigned()) {
266 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
267 return home.ES_SUBSUMED(*this);
268 }
269
270 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
271
272 prop_xnx:
273 std::swap(x0,x1);
274 prop_nxx:
275 assert(neg(x0) && any(x1) && any(x2));
276
277 GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
278 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
279
280 if (pos(x2)) goto rewrite_nnp;
281 if (neg(x2)) goto rewrite_npn;
282
285
286 if (x0.assigned() && x1.assigned()) {
287 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
288 return home.ES_SUBSUMED(*this);
289 }
290
291 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
292
293 rewrite_ppp:
295 ::post(home(*this),x0,x1,x2)));
296 rewrite_nnp:
298 ::post(home(*this),
300 rewrite_pnn:
301 std::swap(x0,x1);
302 rewrite_npn:
304 ::post(home(*this),
306 }
307 return prop_mult_dom<IntView>(home,*this,x0,x1,x2);
308 }
309
312 if (x0 == x1) {
313 SqrOps ops;
314 return PowDom<SqrOps>::post(home,x0,x2,ops);
315 }
316 if (x0 == x2)
318 if (x1 == x2)
320 if (pos(x0)) {
321 if (pos(x1) || pos(x2)) goto post_ppp;
322 if (neg(x1) || neg(x2)) goto post_pnn;
323 } else if (neg(x0)) {
324 if (neg(x1) || pos(x2)) goto post_nnp;
325 if (pos(x1) || neg(x2)) goto post_npn;
326 } else if (pos(x1)) {
327 if (pos(x2)) goto post_ppp;
328 if (neg(x2)) goto post_npn;
329 } else if (neg(x1)) {
330 if (pos(x2)) goto post_nnp;
331 if (neg(x2)) goto post_pnn;
332 }
333 {
334 long long int a = mll(x0.min(),x1.min());
335 long long int b = mll(x0.min(),x1.max());
336 long long int c = mll(x0.max(),x1.min());
337 long long int d = mll(x0.max(),x1.max());
338 GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
339 GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
340 (void) new (home) MultDom(home,x0,x1,x2);
341 }
342 return ES_OK;
343
344 post_ppp:
346 ::post(home,x0,x1,x2);
347 post_nnp:
350 post_pnn:
351 std::swap(x0,x1);
352 post_npn:
355 }
356
357}}}
358
359// STATISTICS: int-prop
360
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
bool neg
Is atomic formula negative.
Base-class for both propagators and branchers.
Definition core.hpp:628
Home class for posting propagators
Definition core.hpp:856
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition mult.cpp:48
MultBnd(Space &home, MultBnd &p)
Constructor for cloning p.
Definition mult.hpp:263
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition mult.cpp:43
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition mult.cpp:144
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition mult.cpp:197
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition mult.cpp:202
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition mult.cpp:311
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition mult.cpp:210
MultDom(Space &home, MultDom &p)
Constructor for cloning p.
Definition mult.hpp:350
Bounds consistent positive multiplication propagator.
Domain consistent positive multiplication propagator.
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition mult.hpp:109
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition pow.hpp:149
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition pow.hpp:386
Operations for square and square-root propagators.
Integer view for integer variables.
Definition view.hpp:129
int min(void) const
Return minimum of domain.
Definition int.hpp:58
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition int.hpp:66
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
int val(void) const
Return assigned value (only if assigned)
Definition int.hpp:70
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Minus integer view.
Definition view.hpp:282
Propagation cost.
Definition core.hpp:486
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:4805
@ HI
Expensive.
Definition core.hpp:514
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3576
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
bool pos(const View &x)
Test whether x is postive.
Definition mult.hpp:70
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition mult.hpp:82
long long int mll(long long int x, long long int y)
Multiply x and \y.
Definition mult.hpp:48
ExecStatus prop_mult_dom(Space &home, Propagator &p, View x0, View x1, View x2)
Definition mult.hpp:272
IntType ceil_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition div.hpp:69
IntType floor_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition div.hpp:75
IntType floor_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:87
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:82
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475