Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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 
34 #include <gecode/int/arithmetic.hh>
35 
36 namespace 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));
72  mll(x0.min(),x1.min()))));
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 
100  GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
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 
121  GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
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 
143  ExecStatus
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());
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 
201  PropCost
202  MultDom::cost(const Space&, const ModEventDelta& med) const {
203  if (IntView::me(med) == ME_INT_DOM)
205  else
207  }
208 
209  ExecStatus
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));
235  mll(x0.min(),x1.min()))));
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 
263  GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
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 
284  GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
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),
299  MinusView(x0),MinusView(x1),x2)));
300  rewrite_pnn:
301  std::swap(x0,x1);
302  rewrite_npn:
304  ::post(home(*this),
305  MinusView(x0),x1,MinusView(x2))));
306  }
307  return prop_mult_dom<IntView>(home,*this,x0,x1,x2);
308  }
309 
310  ExecStatus
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());
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::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition: mult.hpp:331
long long int mll(long long int x, long long int y)
Multiply x and \y.
Definition: mult.hpp:48
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: mult.cpp:202
Bounds consistent positive multiplication propagator.
Definition: arithmetic.hh:648
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:516
IntView x1
Definition: pattern.hpp:116
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:70
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.cpp:48
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
Minus integer view.
Definition: view.hpp:282
Operations for square and square-root propagators.
Definition: arithmetic.hh:302
Cheap.
Definition: core.hpp:513
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:144
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition: mult.hpp:244
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Computation spaces.
Definition: core.hpp:1742
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3576
Base-class for both propagators and branchers.
Definition: core.hpp:628
IntType floor_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition: div.hpp:75
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: pow.hpp:386
MultDom(Space &home, MultDom &p)
Constructor for cloning p.
Definition: mult.hpp:350
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.cpp:210
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: mult.cpp:197
IntView x2
Definition: pattern.hpp:116
IntType ceil_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition: div.hpp:69
Gecode toplevel namespace
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:703
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:311
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
IntType floor_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:87
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Home class for posting propagators
Definition: core.hpp:856
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:82
IntView x0
Three views.
Definition: pattern.hpp:116
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition: mult.hpp:109
MultBnd(Space &home, MultBnd &p)
Constructor for cloning p.
Definition: mult.hpp:263
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:82
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4805
Propagation cost.
Definition: core.hpp:486
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: mult.cpp:43
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: pow.hpp:149
bool neg(const View &x)
Test whether x is negative.
Definition: mult.hpp:76
Gecode::IntSet d(v, 7)
Integer view for integer variables.
Definition: view.hpp:129
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Expensive.
Definition: core.hpp:514
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
Gecode::FloatVal c(-8, 8)
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.hpp:66
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Propagation has not computed fixpoint.
Definition: core.hpp:475
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
Execution is okay.
Definition: core.hpp:476
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
ExecStatus
Definition: core.hpp:472