|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 &)|
|SmallFpImpl & ||operator= (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)|
|const value_t ||myModulus|
|const value_t ||myRecip|
|const unsigned short ||myMulShift1|
|const unsigned short ||myMulShift2|
|const value_t ||myDrop|
|const value_t ||myIterLimit|
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
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::value_t a, b, c;
ModP.myAdd(a, b, c);
ModP.mySub(a, b, c);
ModP.myMul(a, b, c);
ModP.myDiv(a, b, c);
where inv(c) is inverse of c
ModP.myPower(a, b, c);
where ^ means "to the power of"
Example using myDrop and myIterLimit
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;
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/.