LatBuilder::GenSeq::CoprimeIntegers< COMPRESS, TRAV > Class Template Reference

Indexed sequence of integers coprime with a specified modulus. More...

#include <CoprimeIntegers.h>

Inherits LatBuilder::Traversal::Policy< CoprimeIntegers< COMPRESS, TRAV >, TRAV >.

Classes
struct	RebindTraversal
	Rebinds the traversal type. More...

Public Types
typedef Modulus	value_type
	Value type.
typedef size_t	size_type
	Size type.
typedef TRAV	Traversal
	Traversal type.

Public Member Functions
	CoprimeIntegers (value_type modulus=1, Traversal trav=Traversal())
	Constructor. More...
template<class TRAV2 >
	CoprimeIntegers (const CoprimeIntegers< COMPRESS, TRAV2 > &other, Traversal trav=Traversal())
	Cross-traversal copy-constructor.
template<class TRAV2 >
RebindTraversal< TRAV2 >::Type	rebind (TRAV2 trav) const
	Returns a copy of this object, but using a different traversal policy.
value_type	modulus () const
	Returns the modulus.
size_type	size () const
	Returns the size of the sequence. More...
value_type	operator[] (size_type i) const
	Returns the element at index i.

Static Public Member Functions
static std::string	name ()

Friends
template<LatBuilder::Compress , class >
class	CoprimeIntegers

Detailed Description

template<Compress COMPRESS = Compress::NONE, class TRAV = Traversal::Forward>
class LatBuilder::GenSeq::CoprimeIntegers< COMPRESS, TRAV >

Indexed sequence of integers coprime with a specified modulus.

This class assigns a unique index \(i\) to each integer \(k \in \mathbb Z_n^* = \{1,\dots,n-1\}\) that is coprime with \(n\), in a particular order intrinsic to the Chinese remainder theorem.

Let \(n = n_1 \times \dots \times n_\ell\), where \(n_j = b_j^{p_j}\) for \(j=1,\dots,\ell\), and where \(b_1 < \dots < b_\ell\) are \(\ell\) distinct prime numbers with respective integer powers \(p_1,\dots,p_\ell\). The Chinese remainder theorem states that there is an isomorphism between \(\mathbb Z_n^*\) and \(Z_n = \mathbb Z_{n_1}^* \times \dots \times \mathbb Z_{n_\ell}^*\) that maps \(k \in \mathbb Z_n\) to \(\boldsymbol k = (k_1, \dots, k_\ell) = (k \bmod n_1, \dots, k \bmod n_\ell) \in Z_n\). Note that \(k\) and \(n\) are coprime if and only if \(k_j \bmod b_j \neq 0\) for each \(j=1,\dots,\ell\).

The sequence is sorted such that element \(\boldsymbol k\) has index

\[ \sum_{j=1}^\ell \left( k_j - \left\lfloor \frac{k_j}{b_j} \right\rfloor - 1 \right) \prod_{i=1}^{j-1} \varphi(n_i). \]

For example, \(i=0\) corresponds to \(\boldsymbol k = (1, 1, \dots, 1)\) and \(i=1\), to \(\boldsymbol k = (3, 1, \dots, 1)\) if \(b_1 = 2\) and \(p_1 \geq 2\), or to \(\boldsymbol k = (2, 1, \dots, 1)\) if \(b_1 > 2\).

Symmetric compression (see LatBuilder::Compress::SYMMETRIC) consists in applying the transformation \(k \mapsto \min(k, n-k)\). Because either the sequence element \(k\) or the sequence element \(n-k\) is needed to obtain the value \(\min(n,n-k)\), it suffices to consider only the first half of the sequence, i.e. the elements associated with the lower half of all possible values for \(k_\ell\). This works because \(k\) sits in the first half if and only if \(n-k\) sits in the second half: if \((k_1, \dots, k_\ell)\) maps to \(k\), then \((n_1 - k_1, \dots, n_\ell - k_\ell)\) maps to \(n - k\). This is easy to prove by observing that \((n - k) \bmod n_j = n_j - k_j\).

Source: http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Template Parameters

COMPRESS	Type of compression.
TRAV	Traversal policy.

See also

LatBuilder::Compress

Examples:

quantiles.cc, tutorial/FilteredCBC.cc, tutorial/FilteredRCBC.cc, tutorial/GenSeqCoprimeIntegers.cc, tutorial/GenSeqRandom.cc, tutorial/GenSeqVector.cc, tutorial/LatSeqCBC.cc, tutorial/LatSeqCBC1.cc, tutorial/LatSeqExhaustive.cc, tutorial/LatSeqKorobov.cc, tutorial/LatSeqRandom.cc, tutorial/MeritSeqCBC.cc, tutorial/MeritSeqCBCSignals.cc, tutorial/MeritSeqCoordUniform.cc, tutorial/MeritSeqNonCBC.cc, tutorial/WeightedFigureOfMerit.cc, tutorial/WeightedFigureOfMeritCBC.cc, and tutorial/WeightedFigureOfMeritSignals.cc.

Constructor & Destructor Documentation

template<Compress COMPRESS, class TRAV >

LatBuilder::GenSeq::CoprimeIntegers< COMPRESS, TRAV >::CoprimeIntegers	(	value_type	modulus = 1,
		Traversal	trav = Traversal()
	)

Constructor.

Parameters

modulus	Modulus relative to which all numbers in the sequence are coprime.
trav	Traversal instance.

References LatBuilder::egcd(), LatBuilder::intPow(), and LatBuilder::primeFactorsMap().

Member Function Documentation

template<Compress COMPRESS = Compress::NONE, class TRAV = Traversal::Forward>

size_type LatBuilder::GenSeq::CoprimeIntegers< COMPRESS, TRAV >::size ( ) const

inline

Returns the size of the sequence.

The size is the value of Euler's totient function.

---

The documentation for this class was generated from the following file:

• latbuilder/include/latbuilder/GenSeq/CoprimeIntegers.h