Regina 7.0 Calculation Engine
|
Represents an element of a cyclotomic field. More...
#include <maths/cyclotomic.h>
Public Types | |
using | Coefficient = Rational |
The type of each coefficient of the polynomial that is used to store a field element. More... | |
Public Member Functions | |
Cyclotomic () | |
Creates an uninitialised field element. More... | |
Cyclotomic (size_t field) | |
Creates the zero element of the given cyclotomic field. More... | |
Cyclotomic (size_t field, int value) | |
Creates the given integer element within the given cyclotomic field. More... | |
Cyclotomic (size_t field, const Rational &value) | |
Creates the given rational element within the given cyclotomic field. More... | |
Cyclotomic (const Cyclotomic &value) | |
Creates a copy of the given field element, within the same cyclotomic field. More... | |
Cyclotomic (Cyclotomic &&value) noexcept | |
Moves the contents of the given field element to this new field element. More... | |
template<typename iterator > | |
Cyclotomic (size_t field, iterator begin, iterator end) | |
Creates a new field element from the given sequence of coefficients. More... | |
Cyclotomic (size_t field, std::initializer_list< Rational > coefficients) | |
Creates a new field element from a hard-coded sequence of coefficients. More... | |
~Cyclotomic () | |
Destroys this field element. More... | |
void | init (size_t field) |
Initialises this to be the zero element of the given cyclotomic field. More... | |
size_t | field () const |
Returns the order n of the underlying cyclotomic field to which this element belongs. More... | |
size_t | degree () const |
Returns the degree of the polynomial that defines the underlying cyclotomic field. More... | |
const Rational & | operator[] (size_t exp) const |
Returns an individual rational coefficient of the polynomial representation of this field element. More... | |
Rational & | operator[] (size_t exp) |
Offers access to an individual rational coefficient of the polynomial representation of this field element. More... | |
Polynomial< Rational > | polynomial () const |
Returns the full polynomial representation of this field element. More... | |
std::complex< double > | evaluate (size_t whichRoot=1) const |
Returns the value of this cyclotomic field element as a complex number. More... | |
bool | operator== (const Cyclotomic &rhs) const |
Tests whether or not this and the given argument are the same element of the same cyclotomic field. More... | |
bool | operator!= (const Cyclotomic &rhs) const |
Tests whether or not this and the given argument are the same element of the same cyclotomic field. More... | |
Cyclotomic & | operator= (const Cyclotomic &value) |
Sets this to a copy of the given field element. More... | |
Cyclotomic & | operator= (Cyclotomic &&value) noexcept |
Moves the contents of the given field element to this field element. More... | |
Cyclotomic & | operator= (const Rational &scalar) |
Sets this field element to the given rational. More... | |
void | swap (Cyclotomic &other) noexcept |
Swaps the contents of this and the given field element. More... | |
void | negate () |
Negates this field element. More... | |
void | invert () |
Inverts this field element. More... | |
Cyclotomic | inverse () const |
Returns the inverse of this field element. More... | |
Cyclotomic & | operator*= (const Rational &scalar) |
Multiplies this field element by the given rational. More... | |
Cyclotomic & | operator/= (const Rational &scalar) |
Divides this field element by the given rational. More... | |
Cyclotomic & | operator+= (const Cyclotomic &other) |
Adds the given field element to this. More... | |
Cyclotomic & | operator-= (const Cyclotomic &other) |
Subtracts the given field element from this. More... | |
Cyclotomic & | operator*= (const Cyclotomic &other) |
Multiplies this by the given field element. More... | |
Cyclotomic & | operator/= (const Cyclotomic &other) |
Divides this by the given field element. More... | |
void | writeTextShort (std::ostream &out, bool utf8=false, const char *variable=nullptr) const |
Writes this field element to the given output stream, using the given variable name instead of x . More... | |
std::string | str (const char *variable) const |
Returns this field element as a human-readable string, using the given variable name instead of x . More... | |
std::string | utf8 (const char *variable) const |
Returns this field element as a human-readable string using unicode characters, using the given variable name instead of x . More... | |
void | writeTextLong (std::ostream &out) const |
A default implementation for detailed output. More... | |
std::string | str () const |
Returns a short text representation of this object. More... | |
std::string | utf8 () const |
Returns a short text representation of this object using unicode characters. More... | |
std::string | detail () const |
Returns a detailed text representation of this object. More... | |
Static Public Member Functions | |
static const Polynomial< Integer > & | cyclotomic (size_t n) |
Returns the nth cyclotomic polynomial Φ_n . More... | |
Friends | |
Cyclotomic | operator+ (const Cyclotomic &lhs, const Cyclotomic &rhs) |
Adds the two given cyclotomic field elements. More... | |
Cyclotomic | operator- (const Cyclotomic &lhs, const Cyclotomic &rhs) |
Subtracts the two given cyclotomic field elements. More... | |
Cyclotomic | operator* (const Cyclotomic &lhs, const Cyclotomic &rhs) |
Multiplies the two given cyclotomic field elements. More... | |
Represents an element of a cyclotomic field.
The cyclotomic field of order n extends the rationals with a primitive nth root of unity. This is isomorphic to the polynomial field ℚ[x]/Φ_n
, where Φ_n
is the nth cyclotomic polynomial.
Using this isomorphism, each element of the cyclotomic field can be uniquely represented as a rational polynomial of degree strictly less than deg(Φ_n) = φ(n)
, where φ
denotes Euler's totient function. This class stores field elements using such a polynomial representation, and does not store complex numbers directly. If you require the complex value of a field element (as a floating point approximation), you can call evaluate().
Each object of this class stores both the value of the field element and the order n of the underlying field. This means that you can freely work with elements of different fields simultaneously, though of course most operations (such as addition, multplication and so on) require all operands to belong to the same field.
This class requires that the order n is strictly positive.
This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.
Although this class makes use of global data in its implementation, all of its methods are thread-safe.
The type of each coefficient of the polynomial that is used to store a field element.
|
inline |
|
inlineexplicit |
Creates the zero element of the given cyclotomic field.
field | the order of the underlying cyclotomic field; this must be strictly positive. |
|
inline |
Creates the given integer element within the given cyclotomic field.
The polynomial representation of this element will simply be an integer constant.
field | the order of the underlying cyclotomic field; this must be strictly positive. |
value | the value of this element; that is, the integer constant. |
|
inline |
Creates the given rational element within the given cyclotomic field.
The polynomial representation of this element will simply be a rational constant.
field | the order of the underlying cyclotomic field; this must be strictly positive. |
value | the value of this element; that is, the rational constant. |
|
inline |
Creates a copy of the given field element, within the same cyclotomic field.
This constructor induces a deep copy of value.
value | the field element to copy. |
|
inlinenoexcept |
Moves the contents of the given field element to this new field element.
This is a fast (constant time) operation.
The element that was passed (value) will no longer be usable.
value | the field element to move. |
|
inline |
Creates a new field element from the given sequence of coefficients.
The coefficients should describe the field element's polynomial representation, and should be given in order from the constant coefficient upwards. See operator[] for details on what this polynomial representation means.
There should be at most deg(Φ_n) = φ(n)
coefficients in the list, where n is the given order of the underlying field; any missing coefficients are assumed to be zero. In particular, an empty sequence is allowed (and represents the zero field element).
field | the order of the underlying cyclotomic field; this must be strictly positive. |
begin | the beginning of a sequence of at most φ(n) coefficients, as described above. |
end | a past-the-end iterator indicating the end of the sequence of coefficients. |
|
inline |
Creates a new field element from a hard-coded sequence of coefficients.
The coefficients should describe the field element's polynomial representation, and should be given in order from the constant coefficient upwards. See operator[] for details on what this polynomial representation means.
There should be at most deg(Φ_n) = φ(n)
coefficients in the list, where n is the given order of the underlying field; any missing coefficients are assumed to be zero. In particular, an empty sequence is allowed (and represents the zero field element).
field | the order of the underlying cyclotomic field; this must be strictly positive. |
coefficients | a sequence of at most φ(n) coefficients, as described above. |
|
inline |
Destroys this field element.
This is safe even if the field element was never initialised.
|
static |
Returns the nth cyclotomic polynomial Φ_n
.
Cyclotomic polynomials are cached after they are computed, and so after the first call to cyclotomic(n)
, all subsequent calls with the same value of n will be essentially instantaneous.
Although it queries and manipulates a global cache, this routine is thread-safe.
n | indicates which cyclotomic polynomial to return. |
Φ_n
.
|
inline |
Returns the degree of the polynomial that defines the underlying cyclotomic field.
This is the degree of the cyclotomic polynomial Φ_n
, and also the value of Euler's totient function φ(n)
, where n is the order of the field as returned by field().
A value of zero indicates that this field element has not yet been initialised (for instance, it was created using the default constructor).
|
inherited |
Returns a detailed text representation of this object.
This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.
std::complex< double > regina::Cyclotomic::evaluate | ( | size_t | whichRoot = 1 | ) | const |
Returns the value of this cyclotomic field element as a complex number.
The evaluation depends upon which primitive root of unity is used to build the underlying cyclotomic field of order n. This ambiguity is resolved as follows.
Suppose the polynomial representation of this field element in ℚ[x]/Φ_n
(as described in the Cyclotomic class notes) is f(x)
. Then the evaluation of this field element will be f(ρ)
, where ρ is the n
th root of unity ρ = exp(2πi × k/n)
, and where k is the argument whichRoot as passed to this routine.
whichRoot | indicates which root of unity will be used to convert the polynomial representation of this field element into a complex number. |
|
inline |
Returns the order n of the underlying cyclotomic field to which this element belongs.
A value of zero indicates that this field element has not yet been initialised (for instance, it was created using the default constructor).
|
inline |
Initialises this to be the zero element of the given cyclotomic field.
This is safe even if this element was previously initialised as an element of a different field - all prior information about this field element will be safely discarded.
field | the order of the cyclotomic field to which this field element will now belong; this must be strictly positive. |
Cyclotomic regina::Cyclotomic::inverse | ( | ) | const |
Returns the inverse of this field element.
This field element is not changed.
void regina::Cyclotomic::invert | ( | ) |
Inverts this field element.
This field element is changed directly.
|
inline |
Negates this field element.
This field element is changed directly.
|
inline |
Tests whether or not this and the given argument are the same element of the same cyclotomic field.
If this and rhs have different underlying fields then this test will always return true
(indicating that the elements are not equal), even if they take the same numerical value when evaluated as complex numbers.
If either this or rhs have not been initialised (typically because they were created using the default constructor), then this comparison will return true
. If both field elements have not been initialised, then this comparison will return false
.
rhs | the value to compare with this. |
false
if this and rhs are the same element of the same cyclotomic field, or true
if they are not. Cyclotomic & regina::Cyclotomic::operator*= | ( | const Cyclotomic & | other | ) |
Multiplies this by the given field element.
other | the field element to multiply this by. |
|
inline |
Multiplies this field element by the given rational.
This has the effect of multiplying the polynomial representation by a scalar constant.
scalar | the rational to multiply this by. |
|
inline |
Adds the given field element to this.
other | the field element to add to this. |
|
inline |
Subtracts the given field element from this.
other | the field element to subtract from this. |
|
inline |
Divides this by the given field element.
other | the field element to divide this by. |
|
inline |
Divides this field element by the given rational.
This has the effect of dividing the polynomial representation by a scalar constant.
scalar | the rational to divide this by. |
|
inline |
Sets this to a copy of the given field element.
This assignment operator is safe even if this and value belong to different cyclotomic fields, or if this and/or value has not yet been initialised. The underlying field for this element will simply be changed to match the underlying field for value, and all old information stored for this element (if any) will be safely discarded. If value is uninitialised then this field element will become uninitialised also.
This operator induces a deep copy of value.
value | the new value to assign to this field element. |
|
inline |
Sets this field element to the given rational.
The underlying cyclotomic field will be left unchanged.
The polynomial representation for this field element will simply be a constant.
scalar | the new rational value of this field element. |
|
inlinenoexcept |
Moves the contents of the given field element to this field element.
This is a fast (constant time) operation.
This assignment operator is safe even if this and value belong to different cyclotomic fields, or if this and/or value has not yet been initialised. The underlying field for this element will simply be changed to match the underlying field for value, and all old information stored for this element (if any) will be safely discarded. If value is uninitialised then this field element will become uninitialised also.
The element that was passed (value) will no longer be usable.
value | the field element to move. |
|
inline |
Tests whether or not this and the given argument are the same element of the same cyclotomic field.
If this and rhs have different underlying fields then this test will always return false
, even if they take the same numerical value when evaluated as complex numbers.
If either this or rhs have not been initialised (typically because they were created using the default constructor), then this comparison will return false
. If both field elements have not been initialised, then this comparison will return true
.
rhs | the value to compare with this. |
true
if and only if this and rhs are the same element of the same cyclotomic field.
|
inline |
Offers access to an individual rational coefficient of the polynomial representation of this field element.
The polynomial representation expresses this field element as a member of ℚ[x]/Φ_n
, using a rational polynomial of degree strictly less than deg(Φ_n) = φ(n)
; that is, strictly less than the value returned by degree(). See the Cyclotomic class notes for further details.
In particular, for a field element e, the operator e[i]
will give access to the coefficient of x^i
in this polynomial representation.
This routine returns a non-constant reference: you can use this to directly edit the coefficients (and therefore the value of the field element). Note that there is also a constant (read-only) variant of this routine.
exp | indicates which coefficient to access; this must be between 0 and degree()-1 inclusive. |
|
inline |
Returns an individual rational coefficient of the polynomial representation of this field element.
The polynomial representation expresses this field element as a member of ℚ[x]/Φ_n
, using a rational polynomial of degree strictly less than deg(Φ_n) = φ(n)
; that is, strictly less than the value returned by degree(). See the Cyclotomic class notes for further details.
In particular, for a field element e, the operator e[i]
will return the coefficient of x^i
in this polynomial representation.
This is a constant (read-only) routine; note that there is a non-constant (read-write) variant of this routine also.
exp | indicates which coefficient to return; this must be between 0 and degree()-1 inclusive. |
|
inline |
Returns the full polynomial representation of this field element.
The polynomial representation expresses this field element as a member of ℚ[x]/Φ_n
, using a rational polynomial of degree strictly less than deg(Φ_n) = φ(n)
; that is, strictly less than the value returned by degree(). See the Cyclotomic class notes for further details.
|
inherited |
Returns a short text representation of this object.
This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.
Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str()
and repr()
functions.
str()
will use precisely this function, and for most classes the Python repr()
function will incorporate this into its output.
|
inline |
Returns this field element as a human-readable string, using the given variable name instead of x
.
The field element will be written using its rational polynomial representation. The underlying field will not be indicated in the output, since this is often already understood. If required, it can be accessed by calling c.field()
.
variable | the symbol to use for the polynomial variable. This may be null , in which case the default variable x will be used. |
|
inlinenoexcept |
Swaps the contents of this and the given field element.
This is a fast (constant time) operation.
This and the given field element do not need to belong to the same cyclotomic field, and indeed one or both of them may be uninitialised. The underlying fields (if different) will be swapped accordingly.
other | the field element whose contents should be swapped with this. |
|
inherited |
Returns a short text representation of this object using unicode characters.
Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.
Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.
|
inline |
Returns this field element as a human-readable string using unicode characters, using the given variable name instead of x
.
The field element will be written using its rational polynomial representation. The underlying field will not be indicated in the output, since this is often already understood. If required, it can be accessed by calling c.field()
.
This is similar to the output from str(), except that it uses unicode characters to make the output more pleasant to read. In particular, it makes use of superscript digits for exponents.
The string is encoded in UTF-8.
variable | the symbol to use for the polynomial variable. This may be null , in which case the default variable x will be used. |
|
inlineinherited |
A default implementation for detailed output.
This routine simply calls T::writeTextShort() and appends a final newline.
out | the output stream to which to write. |
void regina::Cyclotomic::writeTextShort | ( | std::ostream & | out, |
bool | utf8 = false , |
||
const char * | variable = nullptr |
||
) | const |
Writes this field element to the given output stream, using the given variable name instead of x
.
The field element will be written using its rational polynomial representation. The underlying field will not be indicated in the output, since this is often already understood. If required, it can be accessed by calling c.field()
.
If utf8 is passed as true
then unicode superscript characters will be used for exponents; these will be encoded using UTF-8. This will make the output nicer, but will require more complex fonts to be available on the user's machine.
out | the output stream to which to write. |
utf8 | true if unicode superscript characters may be used. |
variable | the symbol to use for the polynomial variable. This may be null , in which case the default variable x will be used. |
|
friend |
Multiplies the two given cyclotomic field elements.
lhs | the first field element to multiply. |
rhs | the second field element to multiply. |
|
friend |
Adds the two given cyclotomic field elements.
lhs | the first field element to add. |
rhs | the second field element to add. |
|
friend |
Subtracts the two given cyclotomic field elements.
lhs | the field element to subtract from. |
rhs | the field element to subtract. |