- Generated on Fri Aug 17 2018 17:21:02 for LatNet Builder Manual by
1.8.14
|
LatNet Builder Manual
2.0.1-11
Software Package for Constructing Highly Uniform Point Sets
|
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 LatticeTraits< LatticeType::ORDINARY >::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 |
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
| COMPRESS | Type of compression. |
| TRAV | Traversal policy. |
| LatBuilder::GenSeq::CoprimeIntegers< COMPRESS, TRAV >::CoprimeIntegers | ( | value_type | modulus = 1, |
| Traversal | trav = Traversal() |
||
| ) |
Constructor.
| modulus | Modulus relative to which all numbers in the sequence are coprime. |
| trav | Traversal instance. |
References LatBuilder::egcd(), LatBuilder::intPow(), and LatBuilder::primeFactorsMap().
|
inline |
Returns the size of the sequence.
The size is the value of Euler's totient function.
1.8.14