Generated on for Gecode by doxygen 1.18.0
gcd.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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 <algorithm>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 forceinline int
39 gcd_value(int a, int b) {
40 unsigned int x = static_cast<unsigned int>((a < 0) ? -a : a);
41 unsigned int y = static_cast<unsigned int>((b < 0) ? -b : b);
42 while (y != 0U) {
43 unsigned int t = x % y;
44 x = y; y = t;
45 }
46 return static_cast<int>(x);
47 }
48
49 forceinline int
50 gcd_max_abs(const IntView& x) {
51 return std::max((x.min() < 0) ? -x.min() : x.min(),
52 (x.max() < 0) ? -x.max() : x.max());
53 }
54
55 forceinline bool
57 return (x.min() > 0) || (x.max() < 0);
58 }
59
61 forceinline int
62 gcd_upper(const IntView& x0, const IntView& x1) {
63 const int a0=gcd_max_abs(x0);
64 const int a1=gcd_max_abs(x1);
65 int u=std::max(a0,a1);
66 if (gcd_excludes_zero_bnd(x0)) u=std::min(u,a0);
67 if (gcd_excludes_zero_bnd(x1)) u=std::min(u,a1);
68 return u;
69 }
70
72 inline ExecStatus
73 multiple_bounds(Home home, IntView x, int d) {
74 assert(d > 0);
75 const long long int l =
76 ceil_div_xx(static_cast<long long int>(x.min()),
77 static_cast<long long int>(d)) * d;
78 const long long int u =
79 floor_div_xx(static_cast<long long int>(x.max()),
80 static_cast<long long int>(d)) * d;
81 if (l > u)
82 return ES_FAILED;
83 GECODE_ME_CHECK(x.gq(home,static_cast<int>(l)));
84 GECODE_ME_CHECK(x.lq(home,static_cast<int>(u)));
85 return ES_OK;
86 }
87
89 template<class View>
90 inline bool
91 gcd_support_min(View x, int a, int g, int& bound) {
92 bound=x.min();
93 long long int v=ceil_div_xx(static_cast<long long int>(x.min()),
94 static_cast<long long int>(g))*g;
95 // Use the interval hull: interior holes must not affect a BND actor's
96 // fixpoint. The candidates are isolated arithmetic supports, not a
97 // domain enumeration. On exhaustion retain the original endpoint.
98 for (int budget=64; (budget > 0) && (v <= x.max()); --budget, v+=g)
99 if (gcd_value(a,static_cast<int>(v)) == g) {
100 bound=static_cast<int>(v);
101 return true;
102 }
103 return v <= x.max();
104 }
105
107 inline ExecStatus
108 gcd_coprime_bounds(Home home, IntView x, int a, int g) {
109 if ((a % g) != 0)
110 return ES_FAILED;
111 int l;
112 int negative_u;
113 if (!gcd_support_min(x,a,g,l) ||
114 !gcd_support_min(MinusView(x),a,g,negative_u))
115 return ES_FAILED;
116 // On budget exhaustion retain the original endpoint: never advance a
117 // partially checked bound, which could cause an unbounded closure walk.
118 GECODE_ME_CHECK(x.gq(home,l));
119 GECODE_ME_CHECK(x.lq(home,-negative_u));
120 return ES_OK;
121 }
122
124 inline ExecStatus
126 a=(a < 0) ? -a : a;
127 assert(a > 0);
128 GECODE_ME_CHECK(g.gq(home,1));
129 GECODE_ME_CHECK(g.lq(home,a));
130 const int q0=a/g.max();
131 const int q1=a/g.min();
132 if (q0 == q1) {
133 if ((a % q0) != 0)
134 return ES_FAILED;
135 GECODE_ME_CHECK(g.eq(home,a/q0));
136 }
137 return ES_OK;
138 }
139
141 inline RelTest
142 gcd_abs_status(const IntView& x0, const IntView& x1) {
143 if (x1.max() < 0)
144 return RT_FALSE;
145 const int l = ((x0.min() <= 0) && (x0.max() >= 0)) ? 0 :
146 std::min((x0.min() < 0) ? -x0.min() : x0.min(),
147 (x0.max() < 0) ? -x0.max() : x0.max());
148 const int u=gcd_max_abs(x0);
149 if ((x1.max() < l) || (x1.min() > u))
150 return RT_FALSE;
151 if (x0 == x1) {
152 if (x0.min() >= 0)
153 return RT_TRUE;
154 if (x0.max() < 0)
155 return RT_FALSE;
156 }
157 if (x0.assigned()) {
158 const int a=(x0.val() < 0) ? -x0.val() : x0.val();
159 if (!x1.in(a))
160 return RT_FALSE;
161 return x1.assigned() ? RT_TRUE : RT_MAYBE;
162 }
163 if (x1.assigned() && (x1.val() == 0) && !x0.in(0))
164 return RT_FALSE;
165 return RT_MAYBE;
166 }
167
168 inline RelTest
169 gcd_status(const IntView& x0, const IntView& x1, const IntView& x2) {
170 if (x2.max() < 0)
171 return RT_FALSE;
172 if (x2.min() > gcd_upper(x0,x1))
173 return RT_FALSE;
174 if (x0 == x1)
175 return gcd_abs_status(x0,x2);
176 if (x0.assigned() && (x0.val() == 0))
177 return gcd_abs_status(x1,x2);
178 if (x1.assigned() && (x1.val() == 0))
179 return gcd_abs_status(x0,x2);
180 if ((x0.assigned() && ((x0.val() == 1) || (x0.val() == -1))) ||
181 (x1.assigned() && ((x1.val() == 1) || (x1.val() == -1)))) {
182 if (!x2.in(1)) return RT_FALSE;
183 return x2.assigned() ? RT_TRUE : RT_MAYBE;
184 }
185 if (x2.assigned()) {
186 const int g=x2.val();
187 if (g == 0) {
188 if (!x0.in(0) || !x1.in(0)) return RT_FALSE;
189 } else if (g > 0) {
190 if ((x0.assigned() && ((x0.val() % g) != 0)) ||
191 (x1.assigned() && ((x1.val() % g) != 0)))
192 return RT_FALSE;
193 }
194 }
195 if (x0.assigned() && x1.assigned()) {
196 const int g=gcd_value(x0.val(),x1.val());
197 if (!x2.in(g)) return RT_FALSE;
198 return x2.assigned() ? RT_TRUE : RT_MAYBE;
199 }
200 return RT_MAYBE;
201 }
202
203 forceinline
205 : TernaryPropagator<IntView,PC_INT_BND>(home,y0,y1,y2) {}
206
207 inline ExecStatus
209 if (x0 == x1)
210 return AbsBnd<IntView>::post(home,x0,x2);
211 if (x0.assigned() && (x0.val() == 0))
212 return AbsBnd<IntView>::post(home,x1,x2);
213 if (x1.assigned() && (x1.val() == 0))
214 return AbsBnd<IntView>::post(home,x0,x2);
215 if ((x0.assigned() && ((x0.val() == 1) || (x0.val() == -1))) ||
216 (x1.assigned() && ((x1.val() == 1) || (x1.val() == -1)))) {
217 GECODE_ME_CHECK(x2.eq(home,1));
218 return ES_OK;
219 }
220 GECODE_ME_CHECK(x2.gq(home,0));
222 GECODE_ME_CHECK(x2.gq(home,1));
224 // Result narrowing can assign an aliased operand to zero.
225 if (x0.assigned() && (x0.val() != 0))
227 if (x1.assigned() && (x1.val() != 0))
229 if (x2.assigned()) {
230 const int g=x2.val();
231 if (g == 0) {
232 GECODE_ME_CHECK(x0.eq(home,0));
233 GECODE_ME_CHECK(x1.eq(home,0));
234 return ES_OK;
235 }
238 if (x0.assigned())
240 if (x1.assigned())
242 if (x0.assigned() && (x0.val() == 0))
243 return AbsBnd<IntView>::post(home,x1,x2);
244 if (x1.assigned() && (x1.val() == 0))
245 return AbsBnd<IntView>::post(home,x0,x2);
246 }
247 if (x0.assigned() && x1.assigned()) {
249 return ES_OK;
250 }
251 (void) new (home) Gcd(home,x0,x1,x2);
252 return ES_OK;
253 }
254
255 forceinline
256 Gcd::Gcd(Space& home, Gcd& p)
258
259 forceinline Actor*
261 return new (home) Gcd(home,*this);
262 }
263
264 forceinline PropCost
265 Gcd::cost(const Space&, const ModEventDelta&) const {
267 }
268
269 inline ExecStatus
271 const unsigned int s0=x0.size();
272 const unsigned int s1=x1.size();
273 const unsigned int s2=x2.size();
274 if (x0 == x1)
275 GECODE_REWRITE(*this,AbsBnd<IntView>::post(home(*this),x0,x2));
276 if (x0.assigned() && (x0.val() == 0))
277 GECODE_REWRITE(*this,AbsBnd<IntView>::post(home(*this),x1,x2));
278 if (x1.assigned() && (x1.val() == 0))
279 GECODE_REWRITE(*this,AbsBnd<IntView>::post(home(*this),x0,x2));
280 if ((x0.assigned() && ((x0.val() == 1) || (x0.val() == -1))) ||
281 (x1.assigned() && ((x1.val() == 1) || (x1.val() == -1)))) {
282 GECODE_ME_CHECK(x2.eq(home,1));
283 return home.ES_SUBSUMED(*this);
284 }
285 GECODE_ME_CHECK(x2.gq(home,0));
287 GECODE_ME_CHECK(x2.gq(home,1));
288 GECODE_ME_CHECK(x2.lq(home,gcd_upper(x0,x1)));
289 // Result narrowing can assign an aliased operand to zero.
290 if (x0.assigned() && (x0.val() != 0))
292 if (x1.assigned() && (x1.val() != 0))
294 if (x2.assigned()) {
295 const int g=x2.val();
296 if (g == 0) {
297 GECODE_ME_CHECK(x0.eq(home,0));
298 GECODE_ME_CHECK(x1.eq(home,0));
299 return home.ES_SUBSUMED(*this);
300 }
303 if (x0.assigned())
305 if (x1.assigned())
307 if (x0.assigned() && (x0.val() == 0))
308 GECODE_REWRITE(*this,AbsBnd<IntView>::post(home(*this),x1,x2));
309 if (x1.assigned() && (x1.val() == 0))
310 GECODE_REWRITE(*this,AbsBnd<IntView>::post(home(*this),x0,x2));
311 }
312 if (x0.assigned() && x1.assigned()) {
313 GECODE_ME_CHECK(x2.eq(home,gcd_value(x0.val(),x1.val())));
314 return home.ES_SUBSUMED(*this);
315 }
316 // A bounds update can jump over a hole to another non-multiple.
317 return ((s0 != x0.size()) || (s1 != x1.size()) || (s2 != x2.size()))
318 ? ES_NOFIX : ES_FIX;
319 }
320
321 template<ReifyMode rm>
322 forceinline
324 : Propagator(home), x0(y0), x1(y1), x2(y2), b(b0) {
325 home.notice(*this,AP_WEAKLY);
326 x0.subscribe(home,*this,PC_INT_BND);
327 x1.subscribe(home,*this,PC_INT_BND);
328 x2.subscribe(home,*this,PC_INT_BND);
329 b.subscribe(home,*this,PC_BOOL_VAL);
330 }
331
332 template<ReifyMode rm>
333 inline ExecStatus
335 if (b.one()) {
336 if (rm == RM_PMI)
337 return ES_OK;
338 return Gcd::post(home,x0,x1,x2);
339 }
340 if (b.zero() && (rm == RM_IMP))
341 return ES_OK;
342 (void) new (home) ReGcd<rm>(home,x0,x1,x2,b);
343 return ES_OK;
344 }
345
346 template<ReifyMode rm>
347 forceinline
349 : Propagator(home,p) {
350 x0.update(home,p.x0); x1.update(home,p.x1); x2.update(home,p.x2);
351 b.update(home,p.b);
352 }
353
354 template<ReifyMode rm>
355 forceinline Actor*
357 return new (home) ReGcd<rm>(home,*this);
358 }
359
360 template<ReifyMode rm>
361 forceinline PropCost
362 ReGcd<rm>::cost(const Space&, const ModEventDelta&) const {
364 }
365
366 template<ReifyMode rm>
367 forceinline void
369 x0.reschedule(home,*this,PC_INT_BND);
370 x1.reschedule(home,*this,PC_INT_BND);
371 x2.reschedule(home,*this,PC_INT_BND);
372 b.reschedule(home,*this,PC_BOOL_VAL);
373 }
374
375 template<ReifyMode rm>
376 inline ExecStatus
378 if (b.one()) {
379 if (rm == RM_PMI)
380 return home.ES_SUBSUMED(*this);
381 GECODE_REWRITE(*this,Gcd::post(home(*this),x0,x1,x2));
382 }
383 if (b.zero()) {
384 if (rm == RM_IMP)
385 return home.ES_SUBSUMED(*this);
386 const RelTest rt=gcd_status(x0,x1,x2);
387 if (rt == RT_TRUE) return ES_FAILED;
388 if (rt == RT_FALSE) return home.ES_SUBSUMED(*this);
389 return ES_FIX;
390 }
391
392 switch (gcd_status(x0,x1,x2)) {
393 case RT_FALSE:
394 if (rm != RM_PMI)
395 GECODE_ME_CHECK(b.zero(home));
396 return home.ES_SUBSUMED(*this);
397 case RT_TRUE:
398 if (rm != RM_IMP)
399 GECODE_ME_CHECK(b.one(home));
400 return home.ES_SUBSUMED(*this);
401 case RT_MAYBE:
402 return ES_FIX;
403 default: GECODE_NEVER;
404 }
405 }
406
407 template<ReifyMode rm>
408 forceinline size_t
410 x0.cancel(home,*this,PC_INT_BND);
411 x1.cancel(home,*this,PC_INT_BND);
412 x2.cancel(home,*this,PC_INT_BND);
413 b.cancel(home,*this,PC_BOOL_VAL);
414 home.ignore(*this,AP_WEAKLY);
415 (void) Propagator::dispose(home);
416 return sizeof(*this);
417 }
418
419}}}
420
421// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
static ExecStatus post(Home home, View x0, View x1)
Post bounds consistent propagator .
Definition abs.hpp:93
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition gcd.hpp:260
Gcd(Space &home, Gcd &p)
Constructor for cloning p.
Definition gcd.hpp:256
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator.
Definition gcd.hpp:208
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition gcd.hpp:270
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition gcd.hpp:265
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition gcd.hpp:362
BoolView b
Reification control.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition gcd.hpp:409
ReGcd(Home home, IntView x0, IntView x1, IntView x2, BoolView b)
Constructor for posting.
Definition gcd.hpp:323
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition gcd.hpp:356
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition gcd.hpp:377
virtual void reschedule(Space &home)
Reschedule propagator.
Definition gcd.hpp:368
IntView x0
Operands and greatest common divisor.
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2, BoolView b)
Post propagator.
Definition gcd.hpp:334
Boolean view for Boolean variables.
Definition view.hpp:1378
bool zero(void) const
Test whether view is assigned to be zero.
Definition bool.hpp:220
bool one(void) const
Test whether view is assigned to be one.
Definition bool.hpp:224
Integer view for integer variables.
Definition view.hpp:129
int min(void) const
Return minimum of domain.
Definition int.hpp:58
bool in(int n) const
Test whether n is contained in domain.
Definition int.hpp:107
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
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
MinusView(void)
Default constructor.
Definition minus.hpp:45
Propagation cost.
Definition core.hpp:493
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:5089
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
TernaryPropagator(Space &home, TernaryPropagator &p)
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition view.hpp:567
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
@ AP_WEAKLY
Definition core.hpp:575
@ RM_IMP
Implication for reification.
Definition int.hh:1162
@ RM_PMI
Inverse implication for reification.
Definition int.hh:1169
Numerical (arithmetic) propagators.
bool gcd_excludes_zero_bnd(const IntView &x)
Definition gcd.hpp:56
int gcd_upper(const IntView &x0, const IntView &x1)
Upper bound on a gcd from the operand bounds.
Definition gcd.hpp:62
RelTest gcd_abs_status(const IntView &x0, const IntView &x1)
Status of abs(x0)=x1 using bounds, assignments, and domain membership.
Definition gcd.hpp:142
ExecStatus gcd_coprime_bounds(Home home, IntView x, int a, int g)
With an assigned operand, exclude endpoints lacking a coprime quotient.
Definition gcd.hpp:108
ExecStatus multiple_bounds(Home home, IntView x, int d)
Tighten a view to the extreme multiples of a positive divisor.
Definition gcd.hpp:73
RelTest gcd_status(const IntView &x0, const IntView &x1, const IntView &x2)
Definition gcd.hpp:169
int gcd_value(int a, int b)
Definition gcd.hpp:39
bool gcd_support_min(View x, int a, int g, int &bound)
Probe at most 64 multiples for a coprime quotient at an endpoint.
Definition gcd.hpp:91
int gcd_max_abs(const IntView &x)
Definition gcd.hpp:50
ExecStatus gcd_divisor_bounds(Home home, IntView g, int a)
A fixed quotient of an assigned operand admits at most one GCD divisor.
Definition gcd.hpp:125
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:134
IntType floor_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:87
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:82
RelTest
Result of testing relation.
Definition view.hpp:1732
@ RT_TRUE
Relation does hold.
Definition view.hpp:1735
@ RT_MAYBE
Relation may hold or not.
Definition view.hpp:1734
@ RT_FALSE
Relation does not hold.
Definition view.hpp:1733
Gecode toplevel namespace
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56