Global Constraint Catalog: Cgcd

5.158. gcd

DESCRIPTION

LINKS

Origin

Constraint

$𝚐𝚌𝚍 (𝚇, 𝚈, 𝚉)$

Arguments

$𝚇$	$𝚍𝚟𝚊𝚛$
$𝚈$	$𝚍𝚟𝚊𝚛$
$𝚉$	$𝚍𝚟𝚊𝚛$

Restrictions

𝚇 > 0

𝚈 > 0

𝚉 > 0

Purpose

Enforce the fact that $𝚉$ is the greatest common divisor of $𝚇$ and $𝚈$ .

Example

(24, 60, 12)

The $𝚐𝚌𝚍$ constraint holds since 12 is the greatest common divisor of 24 and 60.

Typical

𝚇 > 1

𝚈 > 1

Symmetry

Arguments are permutable w.r.t. permutation $(𝚇, 𝚈)$ $(𝚉)$ .

Arg. properties

Functional dependency: $𝚇$ determined by $𝚈$ and $𝚉$ .

Algorithm

In [DenmatGotliebDucasse07] a filtering algorithm for the $𝚐𝚌𝚍$ constraint was automatically derived from the Euclidian algorithm by using constructive disjunction and abstract interpretation in order to approximate the behaviour of the while loop of the Euclidian algorithm.

Keywords

constraint arguments: ternary constraint, pure functional dependency.

constraint type: arithmetic constraint, predefined constraint.

filtering: abstract interpretation.

modelling: functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.158. gcd