Generated on for Gecode by doxygen 1.17.0
Gecode::Int::Arithmetic Namespace Reference

Numerical (arithmetic) propagators. More...

Classes

class  AbsBnd
 Bounds consistent absolute value propagator. More...
class  AbsDom
 Domain consistent absolute value propagator. More...
class  ArgMax
 Argument maximum propagator. More...
class  DivBnd
 Bounds consistent division propagator. More...
class  DivMod
 Integer division/modulo propagator. More...
class  DivPlusBnd
 Bounds consistent positive division propagator. More...
class  Gcd
 Bounds propagator for \(\gcd(x_0,x_1)=x_2\). More...
class  MaxBnd
 Bounds consistent ternary maximum propagator. More...
class  MaxDom
 Domain consistent ternary maximum propagator. More...
class  MultBnd
 Bounds consistent multiplication propagator. More...
class  MultDom
 Domain consistent multiplication propagator. More...
class  MultPlusBnd
 Bounds consistent positive multiplication propagator. More...
class  MultPlusDom
 Domain consistent positive multiplication propagator. More...
class  MultZeroOne
 Bounds or domain consistent propagator for \(x_0\times x_1=x_0\). More...
class  NaryMaxBnd
 Bounds consistent n-ary maximum propagator. More...
class  NaryMaxDom
 Domain consistent n-ary maximum propagator. More...
class  NrootBnd
 Bounds consistent n-th root propagator. More...
class  NrootDom
 Domain consistent n-th root propagator. More...
class  NrootPlusBnd
 Positive bounds consistent n-th root propagator. More...
class  NrootPlusDom
 Domain consistent n-th root propagator. More...
class  OpenMax
 Track maxima; negated views implement min(x) = -max(-x). More...
class  PowBnd
 Bounds consistent power propagator. More...
class  PowDom
 Domain consistent power propagator. More...
class  PowOps
 Operations for power and nroot propagators. More...
class  PowPlusBnd
 Bounds consistent positive power propagator. More...
class  PowPlusDom
 Domain consistent positive power propagator. More...
class  Product
 Bounds propagator for an exact n-ary product. More...
struct  ProductInterval
 A representable, conservative interval for an exact product. More...
class  ProductMod
 Bounds propagator for a fixed-modulus n-ary product. More...
class  ProductModVar
 Bounds propagator for a variable-modulus n-ary product. More...
struct  ProductWideInterval
 An interval whose endpoints have not been restricted to integer limits. More...
class  RangesMapNroot
 Mapping integer to n-th root. More...
class  RangesMapPow
 Mapping ranges to powers. More...
class  ReDivides
 Reified bounds propagator for divisibility. More...
class  ReGcd
 Reified bounds propagator for \(\gcd(x_0,x_1)=x_2\). More...
class  ReProduct
 Reified bounds propagator for an exact n-ary product. More...
class  ReProductMod
 Reified bounds propagator for a fixed-modulus n-ary product. More...
class  ReProductModVar
 Reified bounds propagator for a variable-modulus product. More...
class  SqrOps
 Operations for square and square-root propagators. More...
class  ValuesMapNroot
 Mapping integer (must be an n-th power) to n-th root. More...
class  ValuesMapNrootSigned
 Mapping integer (must be an n-th power) to n-th root (signed). More...
class  ValuesMapPow
 Mapping integer to power. More...

Enumerations

enum  MaxPropStatus { MPS_ASSIGNED = 1<<0 , MPS_REMOVED = 1<<1 , MPS_NEW_BOUND = 1<<2 }
 Status of propagation for nary max. More...

Functions

template<class View, template< class View0, class View1 > class Eq>
ExecStatus prop_abs_bnd (Space &home, Propagator &p, View x0, View x1)
bool divides_value (int divisor, int dividend)
ExecStatus divides_bnd (Space &home, IntView divisor, IntView dividend)
 Enforce divisibility with bounds reasoning only.
RelTest divides_status (const IntView &x0, const IntView &x1)
int gcd_value (int a, int b)
int gcd_max_abs (const IntView &x)
bool gcd_excludes_zero_bnd (const IntView &x)
int gcd_upper (const IntView &x0, const IntView &x1)
 Upper bound on a gcd from the operand bounds.
ExecStatus multiple_bounds (Home home, IntView x, int d)
 Tighten a view to the extreme multiples of a positive divisor.
template<class View>
bool gcd_support_min (View x, int a, int g, int &bound)
 Probe at most 64 multiples for a coprime quotient at an endpoint.
ExecStatus gcd_coprime_bounds (Home home, IntView x, int a, int g)
 With an assigned operand, exclude endpoints lacking a coprime quotient.
ExecStatus gcd_divisor_bounds (Home home, IntView g, int a)
 A fixed quotient of an assigned operand admits at most one GCD divisor.
RelTest gcd_abs_status (const IntView &x0, const IntView &x1)
 Status of abs(x0)=x1 using bounds, assignments, and domain membership.
RelTest gcd_status (const IntView &x0, const IntView &x1, const IntView &x2)
template<class View>
ExecStatus prop_max_bnd (Space &home, View x0, View x1, View x2)
template<class View>
ExecStatus prop_nary_max_bnd (Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
long long int mll (long long int x, long long int y)
 Multiply x and y.
long long int ll (int x)
 Cast x into a long long int.
long long int ill (int x)
 Increment x by one.
long long int dll (int x)
 Decrement x by one.
template<class View>
bool pos (const View &x)
 Test whether x is positive.
template<class View>
bool neg (const View &x)
 Test whether x is negative.
template<class View>
bool any (const View &x)
 Test whether x is neither positive nor negative.
template<class VA, class VB, class VC>
ExecStatus prop_mult_plus_bnd (Space &home, Propagator &p, VA x0, VB x1, VC x2)
template<class View>
ExecStatus prop_mult_dom (Space &home, Propagator &p, View x0, View x1, View x2)
template<class Ops, bool minus>
ExecStatus prop_nroot_plus_bnd (Space &home, IntView x0, IntView x1, const Ops &ops)
template<class Ops>
ExecStatus prop_nroot_bnd (Space &home, IntView x0, IntView x1, const Ops &ops)
template<class VA, class VB, class Ops>
ExecStatus prop_pow_plus_bnd (Space &home, VA x0, VB x1, const Ops &ops)
template<class Ops>
ExecStatus prop_pow_bnd (Space &home, IntView x0, IntView x1, const Ops &ops)
bool product_mod_interval_mul (ProductInterval a, ProductInterval b, ProductInterval &p)
 Multiply intervals exactly; saturation would make modular deductions unsound.
bool product_mod_interval (const ViewArray< IntView > &x, ProductInterval &p, int a=1)
 Return exact representable product bounds, or false on overflow.
bool product_mod_intervals (const ViewArray< IntView > &x, ProductInterval *prefix, ProductInterval *suffix, int a=1)
 Build all cofactor bounds in linear time, without modular saturation.
int product_mod_coefficient (const ViewArray< IntView > &x, int m, int &free_count)
 Reduce assigned factors and count the remaining factor occurrences.
void product_mod_fold (ViewArray< IntView > &x, int m, int &c, int &a)
 Fold assigned occurrences into modular and representable exact coefficients.
void product_mod_units (ViewArray< IntView > &x)
 Drop assigned units without changing a product with an unknown modulus.
ExecStatus product_mod_nonzero (Space &home, ViewArray< IntView > &x, bool &modified)
 A nonzero residue excludes bounds-visible zero factors.
RelTest product_mod_status (const ViewArray< IntView > &x, const IntView &y, int m)
 Determine the fixed-modulus relation algebraically.
long long int product_mod_inverse (long long int a, long long int m)
 Extended Euclid for a modular inverse (arguments are coprime).
ProductInterval product_mod_congruence (ProductInterval x, int c, int m, int y)
 Extreme solutions to c*x = y modulo m, or an empty interval.
bool product_mod_var_mod_factor (const ViewArray< IntView > &x, const IntView &m)
 Whether the modulus occurs among the factors.
bool product_mod_var_exact (const ViewArray< IntView > &x, long long int &p)
 Compute the exact assigned product when it fits in a signed 64-bit value.
bool product_mod_var_divisor_bounds (int lower, int upper, long long int d, int &least, int &greatest)
 Tighten divisor bounds for a nonzero difference without enumeration.
ExecStatus product_mod_var_ranges (Home home, ViewArray< IntView > &x, IntView m, IntView y)
 Propagate a nonnegative representable product with a variable modulus.
RelTest product_mod_var_status (const ViewArray< IntView > &x, const IntView &m, const IntView &y)
 Determine algebraic status; evaluate the residue only when fully assigned.
ProductInterval product_interval_mul (ProductInterval a, int bmin, int bmax)
 Multiply two representable intervals, clipping out-of-range endpoints.
ProductInterval product_interval_mul (ProductInterval a, ProductInterval b)
 Multiply two representable intervals.
int product_power_abs (int x, int n)
 Compute a nonnegative power, saturating at the integer limit.
ProductInterval product_power_interval (IntView x, int n)
 Bounds for a repeated occurrence viewed as an integer power.
bool product_power_le (int x, int n, int limit)
int product_floor_root (int x, int n)
 Floor and ceiling of a nonnegative integer root.
int product_ceil_root (int x, int n)
ProductWideInterval product_quotient_bounds (long long int ymin, long long int ymax, int qmin, int qmax)
 Quotient bounds for a zero-free divisor, before clipping the endpoints.
ProductInterval product_quotient_interval (int ymin, int ymax, int qmin, int qmax)
 Compute a saturated hull of quotients by a zero-free interval.
ProductInterval product_quotient_hull (ProductInterval y, ProductInterval q)
 Hull of quotients by the nonzero parts of a cofactor interval.
ProductInterval product_root_interval (ProductInterval x, int n, ProductInterval d)
 Invert integer power bounds; min greater than max denotes no support.
ProductInterval product_interval (const ViewArray< IntView > &x, int omit=-1)
 Compute product bounds, optionally omitting one factor.
bool product_value (const int *v, int n, int &p)
 Evaluate a tuple without overflowing internal arithmetic.
RelTest product_status (const ViewArray< IntView > &x, const IntView &y)
 Determine the relation when bounds or assignments prove it.

Detailed Description

Numerical (arithmetic) propagators.

Enumeration Type Documentation

◆ MaxPropStatus

Status of propagation for nary max.

Enumerator
MPS_ASSIGNED 

All views are assigned.

MPS_REMOVED 

A view is removed.

MPS_NEW_BOUND 

Telling has found a new upper bound.

Definition at line 175 of file max.hpp.

Function Documentation

◆ prop_abs_bnd()

template<class View, template< class View0, class View1 > class Eq>
ExecStatus Gecode::Int::Arithmetic::prop_abs_bnd ( Space & home,
Propagator & p,
View x0,
View x1 )

Definition at line 42 of file abs.hpp.

◆ divides_value()

bool Gecode::Int::Arithmetic::divides_value ( int divisor,
int dividend )
inline

Definition at line 39 of file divides.hpp.

◆ divides_bnd()

ExecStatus Gecode::Int::Arithmetic::divides_bnd ( Space & home,
IntView divisor,
IntView dividend )
inline

Enforce divisibility with bounds reasoning only.

Definition at line 45 of file divides.hpp.

◆ divides_status()

RelTest Gecode::Int::Arithmetic::divides_status ( const IntView & x0,
const IntView & x1 )
inline

Definition at line 75 of file divides.hpp.

◆ gcd_value()

int Gecode::Int::Arithmetic::gcd_value ( int a,
int b )
inline

Definition at line 39 of file gcd.hpp.

◆ gcd_max_abs()

int Gecode::Int::Arithmetic::gcd_max_abs ( const IntView & x)
inline

Definition at line 50 of file gcd.hpp.

◆ gcd_excludes_zero_bnd()

bool Gecode::Int::Arithmetic::gcd_excludes_zero_bnd ( const IntView & x)
inline

Definition at line 56 of file gcd.hpp.

◆ gcd_upper()

int Gecode::Int::Arithmetic::gcd_upper ( const IntView & x0,
const IntView & x1 )
inline

Upper bound on a gcd from the operand bounds.

Definition at line 62 of file gcd.hpp.

◆ multiple_bounds()

ExecStatus Gecode::Int::Arithmetic::multiple_bounds ( Home home,
IntView x,
int d )
inline

Tighten a view to the extreme multiples of a positive divisor.

Definition at line 73 of file gcd.hpp.

◆ gcd_support_min()

template<class View>
bool Gecode::Int::Arithmetic::gcd_support_min ( View x,
int a,
int g,
int & bound )
inline

Probe at most 64 multiples for a coprime quotient at an endpoint.

Definition at line 91 of file gcd.hpp.

◆ gcd_coprime_bounds()

ExecStatus Gecode::Int::Arithmetic::gcd_coprime_bounds ( Home home,
IntView x,
int a,
int g )
inline

With an assigned operand, exclude endpoints lacking a coprime quotient.

Definition at line 108 of file gcd.hpp.

◆ gcd_divisor_bounds()

ExecStatus Gecode::Int::Arithmetic::gcd_divisor_bounds ( Home home,
IntView g,
int a )
inline

A fixed quotient of an assigned operand admits at most one GCD divisor.

Definition at line 125 of file gcd.hpp.

◆ gcd_abs_status()

RelTest Gecode::Int::Arithmetic::gcd_abs_status ( const IntView & x0,
const IntView & x1 )
inline

Status of abs(x0)=x1 using bounds, assignments, and domain membership.

Definition at line 142 of file gcd.hpp.

◆ gcd_status()

RelTest Gecode::Int::Arithmetic::gcd_status ( const IntView & x0,
const IntView & x1,
const IntView & x2 )
inline

Definition at line 169 of file gcd.hpp.

◆ prop_max_bnd()

template<class View>
ExecStatus Gecode::Int::Arithmetic::prop_max_bnd ( Space & home,
View x0,
View x1,
View x2 )
inline

Definition at line 45 of file max.hpp.

◆ prop_nary_max_bnd()

template<class View>
ExecStatus Gecode::Int::Arithmetic::prop_nary_max_bnd ( Space & home,
Propagator & p,
ViewArray< View > & x,
View y,
PropCond pc )
inline

Definition at line 183 of file max.hpp.

◆ mll()

long long int Gecode::Int::Arithmetic::mll ( long long int x,
long long int y )
inline

Multiply x and y.

Definition at line 48 of file mult.hpp.

◆ ll()

long long int Gecode::Int::Arithmetic::ll ( int x)
inline

Cast x into a long long int.

Definition at line 53 of file mult.hpp.

◆ ill()

long long int Gecode::Int::Arithmetic::ill ( int x)
inline

Increment x by one.

Definition at line 58 of file mult.hpp.

◆ dll()

long long int Gecode::Int::Arithmetic::dll ( int x)
inline

Decrement x by one.

Definition at line 63 of file mult.hpp.

◆ pos()

template<class View>
bool Gecode::Int::Arithmetic::pos ( const View & x)
inline

Test whether x is positive.

Definition at line 70 of file mult.hpp.

◆ neg()

template<class View>
bool Gecode::Int::Arithmetic::neg ( const View & x)
inline

Test whether x is negative.

Definition at line 76 of file mult.hpp.

◆ any()

template<class View>
bool Gecode::Int::Arithmetic::any ( const View & x)
inline

Test whether x is neither positive nor negative.

Definition at line 82 of file mult.hpp.

◆ prop_mult_plus_bnd()

template<class VA, class VB, class VC>
ExecStatus Gecode::Int::Arithmetic::prop_mult_plus_bnd ( Space & home,
Propagator & p,
VA x0,
VB x1,
VC x2 )
inline

Definition at line 178 of file mult.hpp.

◆ prop_mult_dom()

template<class View>
ExecStatus Gecode::Int::Arithmetic::prop_mult_dom ( Space & home,
Propagator & p,
View x0,
View x1,
View x2 )
inline

Definition at line 272 of file mult.hpp.

◆ prop_nroot_plus_bnd()

template<class Ops, bool minus>
ExecStatus Gecode::Int::Arithmetic::prop_nroot_plus_bnd ( Space & home,
IntView x0,
IntView x1,
const Ops & ops )
inline

Definition at line 48 of file nroot.hpp.

◆ prop_nroot_bnd()

template<class Ops>
ExecStatus Gecode::Int::Arithmetic::prop_nroot_bnd ( Space & home,
IntView x0,
IntView x1,
const Ops & ops )
inline

Definition at line 152 of file nroot.hpp.

◆ prop_pow_plus_bnd()

template<class VA, class VB, class Ops>
ExecStatus Gecode::Int::Arithmetic::prop_pow_plus_bnd ( Space & home,
VA x0,
VB x1,
const Ops & ops )
inline

Definition at line 47 of file pow.hpp.

◆ prop_pow_bnd()

template<class Ops>
ExecStatus Gecode::Int::Arithmetic::prop_pow_bnd ( Space & home,
IntView x0,
IntView x1,
const Ops & ops )
inline

Definition at line 122 of file pow.hpp.

◆ product_mod_interval_mul()

bool Gecode::Int::Arithmetic::product_mod_interval_mul ( ProductInterval a,
ProductInterval b,
ProductInterval & p )
inline

Multiply intervals exactly; saturation would make modular deductions unsound.

Definition at line 39 of file product-mod.hpp.

◆ product_mod_interval()

bool Gecode::Int::Arithmetic::product_mod_interval ( const ViewArray< IntView > & x,
ProductInterval & p,
int a = 1 )
inline

Return exact representable product bounds, or false on overflow.

Definition at line 57 of file product-mod.hpp.

◆ product_mod_intervals()

bool Gecode::Int::Arithmetic::product_mod_intervals ( const ViewArray< IntView > & x,
ProductInterval * prefix,
ProductInterval * suffix,
int a = 1 )
inline

Build all cofactor bounds in linear time, without modular saturation.

Definition at line 70 of file product-mod.hpp.

◆ product_mod_coefficient()

int Gecode::Int::Arithmetic::product_mod_coefficient ( const ViewArray< IntView > & x,
int m,
int & free_count )
inline

Reduce assigned factors and count the remaining factor occurrences.

Definition at line 90 of file product-mod.hpp.

◆ product_mod_fold()

void Gecode::Int::Arithmetic::product_mod_fold ( ViewArray< IntView > & x,
int m,
int & c,
int & a )
inline

Fold assigned occurrences into modular and representable exact coefficients.

Definition at line 108 of file product-mod.hpp.

◆ product_mod_units()

void Gecode::Int::Arithmetic::product_mod_units ( ViewArray< IntView > & x)
inline

Drop assigned units without changing a product with an unknown modulus.

Definition at line 123 of file product-mod.hpp.

◆ product_mod_nonzero()

ExecStatus Gecode::Int::Arithmetic::product_mod_nonzero ( Space & home,
ViewArray< IntView > & x,
bool & modified )
inline

A nonzero residue excludes bounds-visible zero factors.

Definition at line 131 of file product-mod.hpp.

◆ product_mod_status()

RelTest Gecode::Int::Arithmetic::product_mod_status ( const ViewArray< IntView > & x,
const IntView & y,
int m )
inline

Determine the fixed-modulus relation algebraically.

Definition at line 146 of file product-mod.hpp.

◆ product_mod_inverse()

long long int Gecode::Int::Arithmetic::product_mod_inverse ( long long int a,
long long int m )
inline

Extended Euclid for a modular inverse (arguments are coprime).

Definition at line 179 of file product-mod.hpp.

◆ product_mod_congruence()

ProductInterval Gecode::Int::Arithmetic::product_mod_congruence ( ProductInterval x,
int c,
int m,
int y )
inline

Extreme solutions to c*x = y modulo m, or an empty interval.

Definition at line 195 of file product-mod.hpp.

◆ product_mod_var_mod_factor()

bool Gecode::Int::Arithmetic::product_mod_var_mod_factor ( const ViewArray< IntView > & x,
const IntView & m )
inline

Whether the modulus occurs among the factors.

Definition at line 367 of file product-mod.hpp.

◆ product_mod_var_exact()

bool Gecode::Int::Arithmetic::product_mod_var_exact ( const ViewArray< IntView > & x,
long long int & p )
inline

Compute the exact assigned product when it fits in a signed 64-bit value.

Definition at line 376 of file product-mod.hpp.

◆ product_mod_var_divisor_bounds()

bool Gecode::Int::Arithmetic::product_mod_var_divisor_bounds ( int lower,
int upper,
long long int d,
int & least,
int & greatest )
inline

Tighten divisor bounds for a nonzero difference without enumeration.

Definition at line 392 of file product-mod.hpp.

◆ product_mod_var_ranges()

ExecStatus Gecode::Int::Arithmetic::product_mod_var_ranges ( Home home,
ViewArray< IntView > & x,
IntView m,
IntView y )
inline

Propagate a nonnegative representable product with a variable modulus.

Definition at line 430 of file product-mod.hpp.

◆ product_mod_var_status()

RelTest Gecode::Int::Arithmetic::product_mod_var_status ( const ViewArray< IntView > & x,
const IntView & m,
const IntView & y )
inline

Determine algebraic status; evaluate the residue only when fully assigned.

Definition at line 526 of file product-mod.hpp.

◆ product_interval_mul() [1/2]

ProductInterval Gecode::Int::Arithmetic::product_interval_mul ( ProductInterval a,
int bmin,
int bmax )
inline

Multiply two representable intervals, clipping out-of-range endpoints.

Definition at line 45 of file product.hpp.

◆ product_interval_mul() [2/2]

ProductInterval Gecode::Int::Arithmetic::product_interval_mul ( ProductInterval a,
ProductInterval b )
inline

Multiply two representable intervals.

Definition at line 64 of file product.hpp.

◆ product_power_abs()

int Gecode::Int::Arithmetic::product_power_abs ( int x,
int n )
inline

Compute a nonnegative power, saturating at the integer limit.

Definition at line 70 of file product.hpp.

◆ product_power_interval()

ProductInterval Gecode::Int::Arithmetic::product_power_interval ( IntView x,
int n )
inline

Bounds for a repeated occurrence viewed as an integer power.

Definition at line 83 of file product.hpp.

◆ product_power_le()

bool Gecode::Int::Arithmetic::product_power_le ( int x,
int n,
int limit )
inline

Definition at line 99 of file product.hpp.

◆ product_floor_root()

int Gecode::Int::Arithmetic::product_floor_root ( int x,
int n )
inline

Floor and ceiling of a nonnegative integer root.

Definition at line 111 of file product.hpp.

◆ product_ceil_root()

int Gecode::Int::Arithmetic::product_ceil_root ( int x,
int n )
inline

Definition at line 122 of file product.hpp.

◆ product_quotient_bounds()

ProductWideInterval Gecode::Int::Arithmetic::product_quotient_bounds ( long long int ymin,
long long int ymax,
int qmin,
int qmax )
inline

Quotient bounds for a zero-free divisor, before clipping the endpoints.

Definition at line 135 of file product.hpp.

◆ product_quotient_interval()

ProductInterval Gecode::Int::Arithmetic::product_quotient_interval ( int ymin,
int ymax,
int qmin,
int qmax )
inline

Compute a saturated hull of quotients by a zero-free interval.

Definition at line 157 of file product.hpp.

◆ product_quotient_hull()

ProductInterval Gecode::Int::Arithmetic::product_quotient_hull ( ProductInterval y,
ProductInterval q )
inline

Hull of quotients by the nonzero parts of a cofactor interval.

Definition at line 171 of file product.hpp.

◆ product_root_interval()

ProductInterval Gecode::Int::Arithmetic::product_root_interval ( ProductInterval x,
int n,
ProductInterval d )
inline

Invert integer power bounds; min greater than max denotes no support.

Definition at line 189 of file product.hpp.

◆ product_interval()

ProductInterval Gecode::Int::Arithmetic::product_interval ( const ViewArray< IntView > & x,
int omit = -1 )
inline

Compute product bounds, optionally omitting one factor.

Definition at line 222 of file product.hpp.

◆ product_value()

bool Gecode::Int::Arithmetic::product_value ( const int * v,
int n,
int & p )
inline

Evaluate a tuple without overflowing internal arithmetic.

Definition at line 238 of file product.hpp.

◆ product_status()

RelTest Gecode::Int::Arithmetic::product_status ( const ViewArray< IntView > & x,
const IntView & y )
inline

Determine the relation when bounds or assignments prove it.

Definition at line 258 of file product.hpp.