finite modulo-N arithmetic. More...
#include <vnl_finite.h>
Public Member Functions | |
vnl_finite_int (int x=0) | |
Creates a finite int element. | |
vnl_finite_int (Base const &x) | |
~vnl_finite_int () | |
operator int () const | |
operator int () | |
operator long () const | |
operator long () | |
operator short () const | |
operator short () | |
Base & | operator= (Base const &x) |
Assignment. | |
Base & | operator= (int x) |
bool | operator== (Base const &x) const |
Comparison of finite int numbers. | |
bool | operator!= (Base const &x) const |
bool | operator== (int x) const |
bool | operator!= (int x) const |
Base | operator- () const |
Unary minus - returns the additive inverse. | |
Base | operator+ () const |
Unary plus - returns the current number. | |
bool | operator! () const |
Unary not - returns true if finite int number is equal to zero. | |
Base & | operator+= (Base const &r) |
Plus&assign: replace lhs by lhs + rhs. | |
Base & | operator+= (int r) |
Base & | operator-= (Base const &r) |
Minus&assign: replace lhs by lhs - rhs. | |
Base & | operator-= (int r) |
Base & | operator*= (int r) |
Multiply&assign: replace lhs by lhs * rhs. | |
Base & | operator*= (Base const &r) |
Multiply&assign: replace lhs by lhs * rhs. | |
Base | reciproc () const |
Multiplicative inverse. | |
Base & | operator/= (Base const &r) |
Divide&assign. Uses r.reciproc() for efficient computation. | |
Base & | operator++ () |
Pre-increment (++r). | |
Base & | operator-- () |
Pre-decrement (--r). | |
Base | operator++ (int) |
Post-increment (r++). | |
Base | operator-- (int) |
Post-decrement (r--). | |
bool | is_unit () const |
Return true only when x is a unit in this ring. | |
bool | is_zero_divisor () const |
Return true only when x is a zero divisor, i.e., is not a unit. | |
unsigned int | additive_order () const |
The additive order of x is the smallest nonnegative r such that r*x == 0. | |
unsigned int | multiplicative_order () const |
The multiplicative order of x is the smallest r (>0) such that x^r == 1. | |
Base | pow (int r) |
Return the r-th power of this number. | |
unsigned int | log () const |
Return the smallest nonnegative exponent r for which x=g^r, where g is the smallest generator. | |
Static Public Member Functions | |
static unsigned int | cardinality () |
The number of different finite_int numbers of this type. | |
static unsigned int | totient () |
Return the Euler totient function, i.e., the number of units of this ring. | |
static vcl_vector< unsigned int > | decompose () |
Write N as the unique product of prime factors. | |
static bool | is_field () |
Return true when N is a prime number, i.e., when this ring is a field. | |
static Base | smallest_generator () |
Return the smallest multiplicative generator of the units in this ring. | |
static Base | exp (int r) |
Return the inverse of log(), i.e., return g^r where g is the smallest generator. | |
static unsigned int | gcd (unsigned int l, unsigned int n) |
Calculate the greatest common divisor of l and N. | |
static unsigned int | gcd (unsigned int l) |
Private Types | |
typedef vnl_finite_int< N > | Base |
Private Member Functions | |
void | set_log (unsigned int r) const |
private function to set cached value of lp1_ when available. | |
Private Attributes | |
int | val_ |
value of this number (smallest nonnegative representation) | |
unsigned int | mo_ |
cached value for multiplicative order | |
unsigned int | lp1_ |
cached value for 1+log() | |
Related Functions | |
(Note that these are not member functions.) | |
template<int N> | |
vcl_ostream & | operator<< (vcl_ostream &s, vnl_finite_int< N > const &r) |
formatted output. | |
template<int N> | |
vcl_istream & | operator>> (vcl_istream &s, vnl_finite_int< N > &r) |
simple input. | |
template<int N> | |
vnl_finite_int< N > | operator+ (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2) |
Returns the sum of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator+ (vnl_finite_int< N > const &r1, int r2) |
Returns the sum of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator+ (int r2, vnl_finite_int< N > const &r1) |
Returns the sum of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator- (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2) |
Returns the difference of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator- (vnl_finite_int< N > const &r1, int r2) |
Returns the difference of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator- (int r2, vnl_finite_int< N > const &r1) |
Returns the difference of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator* (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2) |
Returns the product of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator* (vnl_finite_int< N > const &r1, int r2) |
Returns the product of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator* (int r2, vnl_finite_int< N > const &r1) |
Returns the product of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator/ (vnl_finite_int< N > const &r1, vnl_finite_int< N > const &r2) |
Returns the quotient of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator/ (vnl_finite_int< N > const &r1, int r2) |
Returns the quotient of two finite int numbers. | |
template<int N> | |
vnl_finite_int< N > | operator/ (int r1, vnl_finite_int< N > const &r2) |
Returns the quotient of two finite int numbers. | |
template<int N> | |
bool | operator== (int r1, vnl_finite_int< N > const &r2) |
template<int N> | |
bool | operator!= (int r1, vnl_finite_int< N > const &r2) |
template<int N> | |
vnl_finite_int< N > | vnl_math_squared_magnitude (vnl_finite_int< N > const &x) |
template<int N> | |
vnl_finite_int< N > | vnl_math_sqr (vnl_finite_int< N > const &x) |
template<int N> | |
bool | vnl_math_isnan (vnl_finite_int< N > const &) |
template<int N> | |
bool | vnl_math_isfinite (vnl_finite_int< N > const &x) |
finite modulo-N arithmetic.
The templated vnl_finite_int<N> provides arithmetic "modulo N", i.e., arithmetic in the finite (Galois) field GF(N) in case N is a prime or just in the finite ring (or semi-field) of integers modulo N otherwise. In that case division makes no sense (unless no zero divisor is involved), but all other operations remain valid.
Definition at line 48 of file vnl_finite.h.
typedef vnl_finite_int<N> vnl_finite_int< N >::Base [private] |
Definition at line 52 of file vnl_finite.h.
vnl_finite_int< N >::vnl_finite_int | ( | int | x = 0 | ) | [inline] |
Creates a finite int element.
Default constructor gives 0. Also serves as automatic cast from int to vnl_finite_int.
Definition at line 60 of file vnl_finite.h.
vnl_finite_int< N >::vnl_finite_int | ( | Base const & | x | ) | [inline] |
Definition at line 62 of file vnl_finite.h.
vnl_finite_int< N >::~vnl_finite_int | ( | ) | [inline] |
Definition at line 64 of file vnl_finite.h.
unsigned int vnl_finite_int< N >::additive_order | ( | ) | const [inline] |
The additive order of x is the smallest nonnegative r such that r*x == 0.
Definition at line 186 of file vnl_finite.h.
static unsigned int vnl_finite_int< N >::cardinality | ( | ) | [inline, static] |
The number of different finite_int numbers of this type.
Definition at line 55 of file vnl_finite.h.
static vcl_vector<unsigned int> vnl_finite_int< N >::decompose | ( | ) | [inline, static] |
Write N as the unique product of prime factors.
Definition at line 161 of file vnl_finite.h.
static Base vnl_finite_int< N >::exp | ( | int | r | ) | [inline, static] |
Return the inverse of log(), i.e., return g^r where g is the smallest generator.
Definition at line 242 of file vnl_finite.h.
static unsigned int vnl_finite_int< N >::gcd | ( | unsigned int | l, |
unsigned int | n | ||
) | [inline, static] |
Calculate the greatest common divisor of l and N.
Definition at line 249 of file vnl_finite.h.
static unsigned int vnl_finite_int< N >::gcd | ( | unsigned int | l | ) | [inline, static] |
Definition at line 254 of file vnl_finite.h.
static bool vnl_finite_int< N >::is_field | ( | ) | [inline, static] |
Return true when N is a prime number, i.e., when this ring is a field.
Definition at line 172 of file vnl_finite.h.
bool vnl_finite_int< N >::is_unit | ( | ) | const [inline] |
Return true only when x is a unit in this ring.
In a field, all numbers except 0 are units. The total number of units is given by the Euler totient function.
Definition at line 180 of file vnl_finite.h.
bool vnl_finite_int< N >::is_zero_divisor | ( | ) | const [inline] |
Return true only when x is a zero divisor, i.e., is not a unit.
Definition at line 183 of file vnl_finite.h.
unsigned int vnl_finite_int< N >::log | ( | ) | const [inline] |
Return the smallest nonnegative exponent r for which x=g^r, where g is the smallest generator.
Definition at line 228 of file vnl_finite.h.
unsigned int vnl_finite_int< N >::multiplicative_order | ( | ) | const [inline] |
The multiplicative order of x is the smallest r (>0) such that x^r == 1.
Definition at line 189 of file vnl_finite.h.
vnl_finite_int< N >::operator int | ( | ) | const [inline] |
Definition at line 66 of file vnl_finite.h.
vnl_finite_int< N >::operator int | ( | ) | [inline] |
Definition at line 67 of file vnl_finite.h.
vnl_finite_int< N >::operator long | ( | ) | const [inline] |
Definition at line 68 of file vnl_finite.h.
vnl_finite_int< N >::operator long | ( | ) | [inline] |
Definition at line 69 of file vnl_finite.h.
vnl_finite_int< N >::operator short | ( | ) | const [inline] |
Definition at line 70 of file vnl_finite.h.
vnl_finite_int< N >::operator short | ( | ) | [inline] |
Definition at line 71 of file vnl_finite.h.
bool vnl_finite_int< N >::operator! | ( | ) | const [inline] |
Unary not - returns true if finite int number is equal to zero.
Definition at line 89 of file vnl_finite.h.
bool vnl_finite_int< N >::operator!= | ( | Base const & | x | ) | const [inline] |
Definition at line 80 of file vnl_finite.h.
bool vnl_finite_int< N >::operator!= | ( | int | x | ) | const [inline] |
Definition at line 82 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator*= | ( | int | r | ) | [inline] |
Multiply&assign: replace lhs by lhs * rhs.
Definition at line 98 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator*= | ( | Base const & | r | ) | [inline] |
Multiply&assign: replace lhs by lhs * rhs.
Definition at line 105 of file vnl_finite.h.
Base vnl_finite_int< N >::operator+ | ( | ) | const [inline] |
Unary plus - returns the current number.
Definition at line 87 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator++ | ( | ) | [inline] |
Pre-increment (++r).
Definition at line 152 of file vnl_finite.h.
Base vnl_finite_int< N >::operator++ | ( | int | ) | [inline] |
Post-increment (r++).
Definition at line 156 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator+= | ( | Base const & | r | ) | [inline] |
Plus&assign: replace lhs by lhs + rhs.
Definition at line 92 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator+= | ( | int | r | ) | [inline] |
Definition at line 93 of file vnl_finite.h.
Base vnl_finite_int< N >::operator- | ( | ) | const [inline] |
Unary minus - returns the additive inverse.
Definition at line 85 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator-- | ( | ) | [inline] |
Pre-decrement (--r).
Definition at line 154 of file vnl_finite.h.
Base vnl_finite_int< N >::operator-- | ( | int | ) | [inline] |
Post-decrement (r--).
Definition at line 158 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator-= | ( | Base const & | r | ) | [inline] |
Minus&assign: replace lhs by lhs - rhs.
Definition at line 95 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator-= | ( | int | r | ) | [inline] |
Definition at line 96 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator/= | ( | Base const & | r | ) | [inline] |
Divide&assign. Uses r.reciproc() for efficient computation.
Definition at line 146 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator= | ( | Base const & | x | ) | [inline] |
Assignment.
Definition at line 74 of file vnl_finite.h.
Base& vnl_finite_int< N >::operator= | ( | int | x | ) | [inline] |
Definition at line 75 of file vnl_finite.h.
bool vnl_finite_int< N >::operator== | ( | Base const & | x | ) | const [inline] |
Comparison of finite int numbers.
Note that finite ints have no order, so < and > make no sense.
Definition at line 79 of file vnl_finite.h.
bool vnl_finite_int< N >::operator== | ( | int | x | ) | const [inline] |
Definition at line 81 of file vnl_finite.h.
Base vnl_finite_int< N >::pow | ( | int | r | ) | [inline] |
Return the r-th power of this number.
Definition at line 219 of file vnl_finite.h.
Base vnl_finite_int< N >::reciproc | ( | ) | const [inline] |
Multiplicative inverse.
Uses exp() and log() for efficient computation, unless log() is not defined.
Definition at line 133 of file vnl_finite.h.
void vnl_finite_int< N >::set_log | ( | unsigned int | r | ) | const [inline, private] |
private function to set cached value of lp1_ when available.
Definition at line 258 of file vnl_finite.h.
static Base vnl_finite_int< N >::smallest_generator | ( | ) | [inline, static] |
Return the smallest multiplicative generator of the units in this ring.
This is only possible if the units form a cyclic group for multiplication. If not, smallest_generator() returns 1 to indicate this fact. Note that the multiplication group of a finite field is always cyclic.
Definition at line 201 of file vnl_finite.h.
static unsigned int vnl_finite_int< N >::totient | ( | ) | [inline, static] |
Return the Euler totient function, i.e., the number of units of this ring.
This number also equals the periodicity of the exponent: every unit, when raised to this power, yields 1.
Definition at line 117 of file vnl_finite.h.
bool operator!= | ( | int | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Definition at line 385 of file vnl_finite.h.
vnl_finite_int< N > operator* | ( | vnl_finite_int< N > const & | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns the product of two finite int numbers.
Definition at line 331 of file vnl_finite.h.
vnl_finite_int< N > operator* | ( | vnl_finite_int< N > const & | r1, |
int | r2 | ||
) | [related] |
Returns the product of two finite int numbers.
Definition at line 339 of file vnl_finite.h.
vnl_finite_int< N > operator* | ( | int | r2, |
vnl_finite_int< N > const & | r1 | ||
) | [related] |
Returns the product of two finite int numbers.
Definition at line 347 of file vnl_finite.h.
vnl_finite_int< N > operator+ | ( | vnl_finite_int< N > const & | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns the sum of two finite int numbers.
Definition at line 283 of file vnl_finite.h.
vnl_finite_int< N > operator+ | ( | vnl_finite_int< N > const & | r1, |
int | r2 | ||
) | [related] |
Returns the sum of two finite int numbers.
Definition at line 291 of file vnl_finite.h.
vnl_finite_int< N > operator+ | ( | int | r2, |
vnl_finite_int< N > const & | r1 | ||
) | [related] |
Returns the sum of two finite int numbers.
Definition at line 299 of file vnl_finite.h.
vnl_finite_int< N > operator- | ( | vnl_finite_int< N > const & | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns the difference of two finite int numbers.
Definition at line 307 of file vnl_finite.h.
vnl_finite_int< N > operator- | ( | vnl_finite_int< N > const & | r1, |
int | r2 | ||
) | [related] |
Returns the difference of two finite int numbers.
Definition at line 315 of file vnl_finite.h.
vnl_finite_int< N > operator- | ( | int | r2, |
vnl_finite_int< N > const & | r1 | ||
) | [related] |
Returns the difference of two finite int numbers.
Definition at line 323 of file vnl_finite.h.
vnl_finite_int< N > operator/ | ( | vnl_finite_int< N > const & | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns the quotient of two finite int numbers.
Uses r2.reciproc() for efficient computation.
Definition at line 356 of file vnl_finite.h.
vnl_finite_int< N > operator/ | ( | vnl_finite_int< N > const & | r1, |
int | r2 | ||
) | [related] |
Returns the quotient of two finite int numbers.
Definition at line 364 of file vnl_finite.h.
vnl_finite_int< N > operator/ | ( | int | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Returns the quotient of two finite int numbers.
Definition at line 372 of file vnl_finite.h.
vcl_ostream & operator<< | ( | vcl_ostream & | s, |
vnl_finite_int< N > const & | r | ||
) | [related] |
formatted output.
Definition at line 267 of file vnl_finite.h.
bool operator== | ( | int | r1, |
vnl_finite_int< N > const & | r2 | ||
) | [related] |
Definition at line 380 of file vnl_finite.h.
vcl_istream & operator>> | ( | vcl_istream & | s, |
vnl_finite_int< N > & | r | ||
) | [related] |
simple input.
Definition at line 275 of file vnl_finite.h.
bool vnl_math_isfinite | ( | vnl_finite_int< N > const & | x | ) | [related] |
Definition at line 405 of file vnl_finite.h.
bool vnl_math_isnan | ( | vnl_finite_int< N > const & | ) | [related] |
Definition at line 400 of file vnl_finite.h.
vnl_finite_int< N > vnl_math_sqr | ( | vnl_finite_int< N > const & | x | ) | [related] |
Definition at line 395 of file vnl_finite.h.
vnl_finite_int< N > vnl_math_squared_magnitude | ( | vnl_finite_int< N > const & | x | ) | [related] |
Definition at line 390 of file vnl_finite.h.
unsigned int vnl_finite_int< N >::lp1_ [mutable, private] |
cached value for 1+log()
Definition at line 261 of file vnl_finite.h.
unsigned int vnl_finite_int< N >::mo_ [mutable, private] |
cached value for multiplicative order
Definition at line 260 of file vnl_finite.h.
int vnl_finite_int< N >::val_ [private] |
value of this number (smallest nonnegative representation)
Definition at line 50 of file vnl_finite.h.