Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | Related Functions
vnl_finite_int< N > Class Template Reference

finite modulo-N arithmetic. More...

#include <vnl_finite.h>

List of all members.

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 ()
Baseoperator= (Base const &x)
 Assignment.
Baseoperator= (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.
Baseoperator+= (Base const &r)
 Plus&assign: replace lhs by lhs + rhs.
Baseoperator+= (int r)
Baseoperator-= (Base const &r)
 Minus&assign: replace lhs by lhs - rhs.
Baseoperator-= (int r)
Baseoperator*= (int r)
 Multiply&assign: replace lhs by lhs * rhs.
Baseoperator*= (Base const &r)
 Multiply&assign: replace lhs by lhs * rhs.
Base reciproc () const
 Multiplicative inverse.
Baseoperator/= (Base const &r)
 Divide&assign. Uses r.reciproc() for efficient computation.
Baseoperator++ ()
 Pre-increment (++r).
Baseoperator-- ()
 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)

Detailed Description

template<int N>
class vnl_finite_int< N >

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.


Member Typedef Documentation

template<int N>
typedef vnl_finite_int<N> vnl_finite_int< N >::Base [private]

Definition at line 52 of file vnl_finite.h.


Constructor & Destructor Documentation

template<int N>
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.

template<int N>
vnl_finite_int< N >::vnl_finite_int ( Base const &  x) [inline]

Definition at line 62 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::~vnl_finite_int ( ) [inline]

Definition at line 64 of file vnl_finite.h.


Member Function Documentation

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
static unsigned int vnl_finite_int< N >::gcd ( unsigned int  l) [inline, static]

Definition at line 254 of file vnl_finite.h.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
vnl_finite_int< N >::operator int ( ) const [inline]

Definition at line 66 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::operator int ( ) [inline]

Definition at line 67 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::operator long ( ) const [inline]

Definition at line 68 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::operator long ( ) [inline]

Definition at line 69 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::operator short ( ) const [inline]

Definition at line 70 of file vnl_finite.h.

template<int N>
vnl_finite_int< N >::operator short ( ) [inline]

Definition at line 71 of file vnl_finite.h.

template<int N>
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.

template<int N>
bool vnl_finite_int< N >::operator!= ( Base const &  x) const [inline]

Definition at line 80 of file vnl_finite.h.

template<int N>
bool vnl_finite_int< N >::operator!= ( int  x) const [inline]

Definition at line 82 of file vnl_finite.h.

template<int N>
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.

template<int N>
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.

template<int N>
Base vnl_finite_int< N >::operator+ ( ) const [inline]

Unary plus - returns the current number.

Definition at line 87 of file vnl_finite.h.

template<int N>
Base& vnl_finite_int< N >::operator++ ( ) [inline]

Pre-increment (++r).

Definition at line 152 of file vnl_finite.h.

template<int N>
Base vnl_finite_int< N >::operator++ ( int  ) [inline]

Post-increment (r++).

Definition at line 156 of file vnl_finite.h.

template<int N>
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.

template<int N>
Base& vnl_finite_int< N >::operator+= ( int  r) [inline]

Definition at line 93 of file vnl_finite.h.

template<int N>
Base vnl_finite_int< N >::operator- ( ) const [inline]

Unary minus - returns the additive inverse.

Definition at line 85 of file vnl_finite.h.

template<int N>
Base& vnl_finite_int< N >::operator-- ( ) [inline]

Pre-decrement (--r).

Definition at line 154 of file vnl_finite.h.

template<int N>
Base vnl_finite_int< N >::operator-- ( int  ) [inline]

Post-decrement (r--).

Definition at line 158 of file vnl_finite.h.

template<int N>
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.

template<int N>
Base& vnl_finite_int< N >::operator-= ( int  r) [inline]

Definition at line 96 of file vnl_finite.h.

template<int N>
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.

template<int N>
Base& vnl_finite_int< N >::operator= ( Base const &  x) [inline]

Assignment.

Definition at line 74 of file vnl_finite.h.

template<int N>
Base& vnl_finite_int< N >::operator= ( int  x) [inline]

Definition at line 75 of file vnl_finite.h.

template<int N>
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.

template<int N>
bool vnl_finite_int< N >::operator== ( int  x) const [inline]

Definition at line 81 of file vnl_finite.h.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.


Friends And Related Function Documentation

template<int N>
bool operator!= ( int  r1,
vnl_finite_int< N > const &  r2 
) [related]

Definition at line 385 of file vnl_finite.h.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
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.

template<int N>
vcl_ostream & operator<< ( vcl_ostream &  s,
vnl_finite_int< N > const &  r 
) [related]

formatted output.

Definition at line 267 of file vnl_finite.h.

template<int N>
bool operator== ( int  r1,
vnl_finite_int< N > const &  r2 
) [related]

Definition at line 380 of file vnl_finite.h.

template<int N>
vcl_istream & operator>> ( vcl_istream &  s,
vnl_finite_int< N > &  r 
) [related]

simple input.

Definition at line 275 of file vnl_finite.h.

template<int N>
bool vnl_math_isfinite ( vnl_finite_int< N > const &  x) [related]

Definition at line 405 of file vnl_finite.h.

template<int N>
bool vnl_math_isnan ( vnl_finite_int< N > const &  ) [related]

Definition at line 400 of file vnl_finite.h.

template<int N>
vnl_finite_int< N > vnl_math_sqr ( vnl_finite_int< N > const &  x) [related]

Definition at line 395 of file vnl_finite.h.

template<int N>
vnl_finite_int< N > vnl_math_squared_magnitude ( vnl_finite_int< N > const &  x) [related]

Definition at line 390 of file vnl_finite.h.


Member Data Documentation

template<int N>
unsigned int vnl_finite_int< N >::lp1_ [mutable, private]

cached value for 1+log()

Definition at line 261 of file vnl_finite.h.

template<int N>
unsigned int vnl_finite_int< N >::mo_ [mutable, private]

cached value for multiplicative order

Definition at line 260 of file vnl_finite.h.

template<int N>
int vnl_finite_int< N >::val_ [private]

value of this number (smallest nonnegative representation)

Definition at line 50 of file vnl_finite.h.


The documentation for this class was generated from the following file: