next up previous contents index
Next: The smod kernel of Up: Number Types and Linear Previous: Modular Arithmetic in LEDA   Contents   Index


The mod kernel of type residual ( residual )

Definition

Type residual::mod provides the basic modular arithmetic modulo primes of maximal size 226. Here numbers modulo the prime p are represented by integral doubles in [0, ... p - 1]. This type cannot be instantiated, so there are only static functions and no constructors. The following functions have the common precondition that p is a prime between 2 and 226.

#include < LEDA/numbers/residual.h >

Operations

double residual::reduce_of_positive(double a, double p)
    returns a modulo p for nonnegative integral 0 < = a < 254

double residual::reduce(double a, double p)
    returns a modulo p for any integral a with |a|< 254

double residual::add(double a, double b, double p)
    returns (a + b)modp where a, b are integral with |a|,|b|< 252

double residual::sub(double a, double b, double p)
    returns (a - b)modp where a, b are integral with |a|,|b|< 252

double residual::mul(double a, double b, double p)
    returns (a*b)modp where a, b are integral with |a*b|< 253

double residual::div(double a, double b, double p)
    returns (a*b-1)modp where a, b are integral with |a|< 226 and b! = 0modp

double residual::negate(double a, double p)
    returns - amodp for nonnegative a < p

double residual::inverse(double a, double p)
    returns the inverse of a modulo p for intergal 0 < = a < p < 232


next up previous contents index
Next: The smod kernel of Up: Number Types and Linear Previous: Modular Arithmetic in LEDA   Contents   Index
root 2008-01-09