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>

## 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$$.

Template Parameters
 COMPRESS Type of compression. TRAV Traversal policy.
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