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< Rational >	RationalList

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 >
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

typedef std::vector<Rational> atlas::arithmetic::RationalList

Function Documentation

Denom_t atlas::arithmetic::div_gcd ( Denom_t  a, Denom_t  b  )

inline

template<typename I >

I atlas::arithmetic::divide ( I  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 ( I  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