The class SmallFpImpl
is a very low level implementation class for fast
arithmetic in a small, prime finite field. It is not intended for use
by casual CoCoALib users, who should instead see the documentation in
QuotientRing
(in particular the function NewZmod
), or possibly the
documentation in RingFp
, RingFpLog
, and RingFpDouble
.
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. The values to be manipulated must be of type SmallFpImpl::value_t
.
This is an unsigned machine integer type, and the values 0
and 1
may be used normally (but other values must be reduced before being used).
All operations on values must be effected by calling member functions
of the SmallFpImpl
class. Here is a brief summary.
SmallFpImpl ModP(p, convention); // create SmallFpImpl object int n; BigInt N; BigRat q; SmallFpImpl::value_t a, b, c; ModP.myModulus(); // value of p (as a long) ModP.myReduce(n); // reduce mod p ModP.myReduce(N); // reduce mod p ModP.myReduce(q); // reduce mod p ModP.myNegate(a); // -a mod p ModP.myAdd(a, b); // (a+b)%p; ModP.mySub(a, b); // (a-b)%p; ModP.myMul(a, b); // (a*b)%p; ModP.myDiv(a, b); // (a*inv(b))%p; where inv(b) is inverse of b ModP.myPower(a, b); // (a^b)%p; where ^ means "to the power of" ModP.myIsZeroAddMul(a,b,c) // a = (a+b*c)%p; result is (a==0) ModP.myExport(a); // returns a preimage (of type long) according to symm/non-neg convention.
For myExport
the choice between least non-negative and symmetric
residues is determined by the convention specified when constructing
the SmallFpImpl
object. This convention may be either
GlobalSettings::SymmResidues
or
GlobalSettings::NonNegResidues
.
This is still preliminary
SmallFpImpl::value_t InnerProd; 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; k = 0; } } InnerProd = ModP.myReduceMod(InnerProd);
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). See example in user doc.
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.
Should there be a myIsMinusOne
function?
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).
No example programs in examples/ directory.