atlas  0.6
Classes | Typedefs | Functions | Variables
atlas::arithmetic Namespace Reference

Classes

class  Rational
 
class  Split_integer
 

Typedefs

typedef long long int Numer_t
 
typedef unsigned long long int Denom_t
 
typedef std::vector< RationalRationalList
 

Functions

std::ostream & operator<< (std::ostream &strm, const Split_integer &s)
 
Denom_t unsigned_gcd (Denom_t a, Denom_t b)
 
Denom_t lcm (Denom_t a, Denom_t b, Denom_t &gcd, Denom_t &mult_a)
 
Denom_t modProd (Denom_t a, Denom_t b, Denom_t n)
 
Denom_t power (Denom_t x, unsigned int n)
 
std::ostream & operator<< (std::ostream &out, const Rational &frac)
 
template<typename I >
divide (I, Denom_t)
 
template<typename I >
Denom_t remainder (I, Denom_t)
 
Denom_t gcd (Numer_t, Denom_t)
 
Denom_t div_gcd (Denom_t a, Denom_t b)
 
Denom_t modAdd (Denom_t, Denom_t, Denom_t)
 
Denom_t divide (Denom_t a, Denom_t b)
 

Variables

Denom_t dummy_gcd
 
Denom_t dummy_mult
 

Typedef Documentation

typedef unsigned long long int atlas::arithmetic::Denom_t
typedef long long int atlas::arithmetic::Numer_t

Function Documentation

Denom_t atlas::arithmetic::div_gcd ( Denom_t  a,
Denom_t  b 
)
inline
template<typename I >
I atlas::arithmetic::divide ( a,
Denom_t  b 
)
inline

The result of |divide(a,b)| is the unique integer $q$ with $a = q.b + r$, and $0 r < b$. Here the sign of |a| may be arbitrary, the requirement for |r| assumes |b| positive, which is why it is passed as unsigned (also this better matches the specification of |remainder| below). Callers must make sure that $b$ is positive, since implicit conversion of a negative signed value to unsigned would wreak havoc.

Hardware division probably does not handle negative |a| correctly; for instance, divide(-1,2) should be -1, so that -1 = -1.2 + 1, but on my machine, -1/2 is 0 (which is the other value accepted by the C standard; Fokko.) [Note that the correct symmetry to apply to |a|, one that maps classes with the same quotient to each other, is not $a -a$ but $a -1-a$, where the latter value can be conveniently written as |~a| in C or C++. Amazingly Fokko's incorrect original expresion |-(-a/b -1)| never did any harm. MvL]

Denom_t atlas::arithmetic::divide ( Denom_t  a,
Denom_t  b 
)
inline
Denom_t atlas::arithmetic::gcd ( Numer_t  a,
Denom_t  b 
)
inline
Denom_t atlas::arithmetic::lcm ( Denom_t  a,
Denom_t  b,
Denom_t gcd,
Denom_t mult_a 
)
Denom_t atlas::arithmetic::modAdd ( Denom_t  a,
Denom_t  b,
Denom_t  n 
)
inline
Denom_t atlas::arithmetic::modProd ( Denom_t  a,
Denom_t  b,
Denom_t  n 
)

Synopsis: return a * b mod n.

Precondition: a < n; b < n.

NOTE: preliminary implementation. It assumes that |n <= 2^^(longBits/2)|, i.e., mudular numbers fit in a half-long Exit brutally if this is not fulfilled.

std::ostream & atlas::arithmetic::operator<< ( std::ostream &  strm,
const Split_integer s 
)
std::ostream & atlas::arithmetic::operator<< ( std::ostream &  out,
const Rational frac 
)
Denom_t atlas::arithmetic::power ( Denom_t  x,
unsigned int  n 
)
template<typename I >
Denom_t atlas::arithmetic::remainder ( a,
Denom_t  b 
)
inline
Denom_t atlas::arithmetic::unsigned_gcd ( Denom_t  a,
Denom_t  b 
)

The classical Euclidian algorithm for positive (indeed unsigned) numbers. It is assumed that |b != 0|, but |a| might be zero.

Variable Documentation

Denom_t atlas::arithmetic::dummy_gcd
Denom_t atlas::arithmetic::dummy_mult