CoCoALib-0.9905 date: 23 May 2007


CoCoA::SmallFpImpl Class Reference

#include <SmallFpImpl.H>

Collaboration diagram for CoCoA::SmallFpImpl:

Collaboration graph
[legend]
List of all members.

Public Types

typedef SmallFpElem_t value_t

Public Member Functions

 SmallFpImpl (unsigned long p)
 SmallFpImpl (const ZZ &P)
void myAssignZero (value_t &lhs) const
 lhs = 0
void myAssign (value_t &lhs, value_t x) const
 lhs = x
void myAssign (value_t &lhs, long n) const
 lhs = n
void myAssign (value_t &lhs, const ZZ &N) const
 lhs = N
void myNegate (value_t &lhs, value_t x) const
 lhs = -x
void myAdd (value_t &lhs, value_t x, value_t y) const
 lhs = x+y
void mySub (value_t &lhs, value_t x, value_t y) const
 lhs = x-y
void myMul (value_t &lhs, value_t x, value_t y) const
 lhs = x*y
void myDiv (value_t &lhs, value_t x, value_t y) const
 lhs = x/y
bool myIsDivisible (value_t &lhs, value_t x, value_t y) const
 lhs = x/y, if y is non-zero
void myPower (value_t &lhs, value_t x, unsigned long n) const
 lhs = x^n
void myOutput (std::ostream &out, value_t x) const
 out << x
void myOutput (OpenMathOutput &OMOut, value_t x) const
 OMOut << x.
bool myIsPrintAtom (value_t x) const
bool myIsPrintedWithMinus (value_t x) const
bool myIsZero (value_t x) const
 x == 0
bool myIsOne (value_t x) const
 x == 1
bool myIsMinusOne (value_t x) const
 x == -1
bool myIsInteger (ZZ &N, value_t x) const
 copy value of x into n, result is always true
bool myIsZeroAddMul (value_t &lhs, value_t y, value_t z) const
bool myIsEqual (value_t x, value_t y) const

Static Public Attributes

static const std::size_t DatumSize = sizeof(value_t)

Private Member Functions

 SmallFpImpl (const SmallFpImpl &)
SmallFpImploperator= (const SmallFpImpl &)
value_t myReduceMod (value_t n) const

Static Private Member Functions

static value_t CheckCtorArg (unsigned long p)
static value_t CheckCtorArg (const ZZ &P)
static value_t CalcRecip (value_t p)
static value_t CalcDrop (value_t p)
static value_t CalcIterLimit (value_t p)

Private Attributes

const value_t myModulus
const value_t myRecip
const unsigned short myMulShift1
const unsigned short myMulShift2
const value_t myDrop
const value_t myIterLimit

Detailed Description

      Copyright (c)  2005 John Abbott
      Permission is granted to copy, distribute and/or modify this document
      under the terms of the GNU Free Documentation License, Version 1.2;
      with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
      A copy of the licence is included in the file COPYING in this directory.



User documentation for SmallFpImpl
==================================

The class [SmallFpImpl] is NOT INTENDED for use by "casual" CoCoALib
users.  If you wish to compute in finite fields see the documentation in
QuotientRing.txt (in particular the function [NewZmod]), or possibly the
documentation in RingFp.txt, RingFpLog.txt, and RingFpDouble.txt.

The class [SmallFpImpl] offers the possibility of highly efficient
arithmetic in small prime finite fields.  This efficiency comes at a
cost: the interface is rather unnatural and intolerant of mistakes.  The
emphasis is unequivocally on speed rather than safety or convenience.

The full speed of [SmallFpImpl] depends on many of its functions being
inlined.

A [SmallFpImpl] object cannot be used as a CoCoA [ring], even though the
implementation is rather reminiscent of a [ring] implementation class.
ALL OPERATIONS on values must be effected by calling member functions
of the [SmallFpImpl] class.  Here is a brief summary.

  SmallFpImpl ModP(p);         // create SmallFpImpl object
  int n;
  ZZ N;
  SmallFpImpl::value_t a, b, c;

  ModP.myAssign(a, b);         // a = b;
  ModP.myAssign(a, n);         // a = n%p; (reduce mod p)
  ModP.myAssign(a, N);         // a = N%p; (reduce mod p)
  ModP.myNegate(a, b);         // a = -b;

  ModP.myAdd(a, b, c);         // a = (b+c)%p;
  ModP.mySub(a, b, c);         // a = (b-c)%p;
  ModP.myMul(a, b, c);         // a = (b*c)%p;
  ModP.myDiv(a, b, c);         // a = (b*inv(c))%p;
                                  where inv(c) is inverse of c
  ModP.myPower(a, b, c);       // a = (b^c)%p;
                                  where ^ means "to the power of"

  ModP.myIsZero(a);            // a == 0
  ModP.myIsOne(a);             // a == 1
  ModP.myIsMinusOne(a);        // a == -1
  ModP.myIsInteger(N, a);      // N = a (find a preimage); always returns true.
  ModP.myIsEqual(a, b);        // a == b

  ModP.myOutput(out, a);       // out << a;


Example using myDrop and myIterLimit
------------------------------------

ModP.myAssign(InnerProd, 0);
size_t k=0;
for (size_t i=0; i < n; ++i)
{
  InnerProd += v1[i]*v2[i];
  if (++k < ModP.myIterLimit) continue;
  if (InnerProd > ModP.myDrop)
    InnerProd -= ModP.myDrop;
}
InnerProd %= p;//???BUG BUG???



Maintainer documentation for SmallFpImpl
========================================

Most functions are implemented inline, and no sanity checks are
performed (except when CoCoA_DEBUG is enabled).  The constructor
does do some checking.

[SmallFpImpl::value_t] should be an unsigned integral type; it is a
typedef to a type specified in CoCoA/config.H -- this should allow
fairly easy platform-specific customization.

This code is valid only if the square of [myModulus] can be represented
in a [SmallFpImpl::value_t] -- the constructor checks this condition.
Most functions do not require [myModulus] to be prime, though division
becomes only a partial map if it is composite; and the function
myIsDivisible is correct only if [myModulus] is prime.  Currently the
constructor rejects non-prime moduli.

The code assumes that each value modulo p is represented as the least
non-negative residue (i.e. the values are represented as integers in
the range 0 to p-1 inclusive).  This decision is linked to the fact
that [SmallFpImpl::value_t] is an unsigned type.

Note that [myMul] and [myIsZeroAddMul] have "fancy" implementations:
the normal remaindering operation is rather slow on many processors,
and the code given here is usefully faster on Athlons and Mac G5.
The benefit arises from the fact that a "reciprocal" of the modulus
can be precomputed inside the constructor.

The constants [myDrop] and [myIterLimit] are to allow efficient
exploitation of non-reduced multiplication (e.g. when trying to
compute an inner product modulo p).

The return type of [NumBits] is [unsigned short], which should offer
a large enough range for the forseeable future.  Would [size_t] be
better?  If so, then the data members [myMulShift1] and [myMulShift2]
should be made into [size_t] too.


Bugs, Shortcomings, and other ideas
===================================

How to distinguish between "homogeneous" [myAssign], and [myAssign] from
a [long]?  The latter must reduce its argument, the former must not!

Need functions for (fast) non-reducing addition and multiplication;
and [myDrop] and [myIterLimit] need to be publicly accessible.
Also need a good example to show how to use them.

Why don't [myMulShift1] and [myMulShift2] have sensible names???
(as used in SmallFpLogImpl, for instance -- have a look).

Can multiplication be made any faster?  It is a nuisance to have to
check twice whether the value is less than [myModulus].  To be honest
I do not yet have a proof that the "nifty reduction modulo p" is
always correct (it is OK for p < 32768, checked by exhaustive search).

Values are printed out as least non-negative residues.  Perhaps the user
should be allowed to choose symmetric residues instead?

Should there be a function for accessing the value of [myModulus]?
If so, what should the type of the result be?

No example programs in examples/.

Definition at line 44 of file SmallFpImpl.H.


Member Typedef Documentation

typedef SmallFpElem_t CoCoA::SmallFpImpl::value_t
 

Definition at line 53 of file SmallFpImpl.H.


Constructor & Destructor Documentation

CoCoA::SmallFpImpl::SmallFpImpl unsigned long  p  ) 
 

CoCoA::SmallFpImpl::SmallFpImpl const ZZ P  ) 
 

CoCoA::SmallFpImpl::SmallFpImpl const SmallFpImpl  )  [private]
 


Member Function Documentation

SmallFpImpl& CoCoA::SmallFpImpl::operator= const SmallFpImpl  )  [private]
 

void CoCoA::SmallFpImpl::myAssignZero value_t lhs  )  const [inline]
 

lhs = 0

Definition at line 113 of file SmallFpImpl.H.

Referenced by CoCoA::DistrMPolyInlFpPP::NewSummandPtr::myAssignZero().

void CoCoA::SmallFpImpl::myAssign value_t lhs,
value_t  x
const [inline]
 

lhs = x

Definition at line 119 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

void CoCoA::SmallFpImpl::myAssign value_t lhs,
long  n
const [inline]
 

lhs = n

Definition at line 126 of file SmallFpImpl.H.

References myModulus.

void CoCoA::SmallFpImpl::myAssign value_t lhs,
const ZZ N
const [inline]
 

lhs = N

Definition at line 134 of file SmallFpImpl.H.

References CoCoA::mpzref(), and myModulus.

void CoCoA::SmallFpImpl::myNegate value_t lhs,
value_t  x
const [inline]
 

lhs = -x

Definition at line 140 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

void CoCoA::SmallFpImpl::myAdd value_t lhs,
value_t  x,
value_t  y
const [inline]
 

lhs = x+y

Definition at line 148 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

void CoCoA::SmallFpImpl::mySub value_t lhs,
value_t  x,
value_t  y
const [inline]
 

lhs = x-y

Definition at line 157 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

void CoCoA::SmallFpImpl::myMul value_t lhs,
value_t  x,
value_t  y
const [inline]
 

lhs = x*y

Definition at line 166 of file SmallFpImpl.H.

References CoCoA_ASSERT, myModulus, myMulShift1, myMulShift2, and myRecip.

void CoCoA::SmallFpImpl::myDiv value_t lhs,
value_t  x,
value_t  y
const
 

lhs = x/y

Referenced by myIsDivisible().

bool CoCoA::SmallFpImpl::myIsDivisible value_t lhs,
value_t  x,
value_t  y
const [inline]
 

lhs = x/y, if y is non-zero

Definition at line 178 of file SmallFpImpl.H.

References CoCoA_ASSERT, myDiv(), and myModulus.

void CoCoA::SmallFpImpl::myPower value_t lhs,
value_t  x,
unsigned long  n
const
 

lhs = x^n

void CoCoA::SmallFpImpl::myOutput std::ostream &  out,
value_t  x
const
 

out << x

void CoCoA::SmallFpImpl::myOutput OpenMathOutput OMOut,
value_t  x
const
 

OMOut << x.

bool CoCoA::SmallFpImpl::myIsPrintAtom value_t  x  )  const [inline]
 

Definition at line 188 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

bool CoCoA::SmallFpImpl::myIsPrintedWithMinus value_t  x  )  const [inline]
 

Definition at line 195 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

bool CoCoA::SmallFpImpl::myIsZero value_t  x  )  const [inline]
 

x == 0

Definition at line 202 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

Referenced by myIsZeroAddMul().

bool CoCoA::SmallFpImpl::myIsOne value_t  x  )  const [inline]
 

x == 1

Definition at line 209 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

bool CoCoA::SmallFpImpl::myIsMinusOne value_t  x  )  const [inline]
 

x == -1

Definition at line 216 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

bool CoCoA::SmallFpImpl::myIsInteger ZZ N,
value_t  x
const [inline]
 

copy value of x into n, result is always true

Definition at line 223 of file SmallFpImpl.H.

bool CoCoA::SmallFpImpl::myIsZeroAddMul value_t lhs,
value_t  y,
value_t  z
const [inline]
 

Definition at line 230 of file SmallFpImpl.H.

References CoCoA_ASSERT, myIsZero(), myModulus, myMulShift1, myMulShift2, and myRecip.

bool CoCoA::SmallFpImpl::myIsEqual value_t  x,
value_t  y
const [inline]
 

Definition at line 243 of file SmallFpImpl.H.

References CoCoA_ASSERT, and myModulus.

SmallFpImpl::value_t CoCoA::SmallFpImpl::myReduceMod value_t  n  )  const [inline, private]
 

Definition at line 107 of file SmallFpImpl.H.

References myModulus.

static value_t CoCoA::SmallFpImpl::CheckCtorArg unsigned long  p  )  [static, private]
 

static value_t CoCoA::SmallFpImpl::CheckCtorArg const ZZ P  )  [static, private]
 

static value_t CoCoA::SmallFpImpl::CalcRecip value_t  p  )  [static, private]
 

static value_t CoCoA::SmallFpImpl::CalcDrop value_t  p  )  [static, private]
 

static value_t CoCoA::SmallFpImpl::CalcIterLimit value_t  p  )  [static, private]
 


Member Data Documentation

const std::size_t CoCoA::SmallFpImpl::DatumSize = sizeof(value_t) [static]
 

Definition at line 54 of file SmallFpImpl.H.

const value_t CoCoA::SmallFpImpl::myModulus [private]
 

Definition at line 80 of file SmallFpImpl.H.

Referenced by myAdd(), myAssign(), myIsDivisible(), myIsEqual(), myIsMinusOne(), myIsOne(), myIsPrintAtom(), myIsPrintedWithMinus(), myIsZero(), myIsZeroAddMul(), myMul(), myNegate(), myReduceMod(), and mySub().

const value_t CoCoA::SmallFpImpl::myRecip [private]
 

Definition at line 81 of file SmallFpImpl.H.

Referenced by myIsZeroAddMul(), and myMul().

const unsigned short CoCoA::SmallFpImpl::myMulShift1 [private]
 

Definition at line 82 of file SmallFpImpl.H.

Referenced by myIsZeroAddMul(), and myMul().

const unsigned short CoCoA::SmallFpImpl::myMulShift2 [private]
 

Definition at line 83 of file SmallFpImpl.H.

Referenced by myIsZeroAddMul(), and myMul().

const value_t CoCoA::SmallFpImpl::myDrop [private]
 

Definition at line 84 of file SmallFpImpl.H.

const value_t CoCoA::SmallFpImpl::myIterLimit [private]
 

Definition at line 85 of file SmallFpImpl.H.


The documentation for this class was generated from the following file:
Generated on Wed May 23 13:44:51 2007 for CoCoALib by  doxygen 1.4.6