Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
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
COMPRESSType of compression.
TRAVTraversal 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
modulusModulus relative to which all numbers in the sequence are coprime.
travTraversal 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: