Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- Class List
- Class Index
- Class Hierarchy
- Class Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
Classes | Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
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