# SmallFpDoubleImpl

© 2005,2010-2011 John Abbott
GNU Free Documentation License, Version 1.2

CoCoALib Documentation Index

## User documentation for SmallFpDoubleImpl

The class `SmallFpDoubleImpl` 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`.

Compared to `SmallFpImpl` the main difference is an implementation detail: values are represented as `double`s -- on 32-bit computers this allows a potentially usefully greater range of characteristics at a probably minor run-time cost.

A `SmallFpDoubleImpl` 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 `SmallFpDoubleImpl` class. Here is a brief summary.

```    SmallFpDoubleImpl ModP(p,convention);   // create SmallFpDoubleImpl object
int n;
BigInt N;
SmallFpImpl::value_t a, b, c;

ModP.myModulus();            // value of p (as a long)

ModP.myReduceMod(n);         // reduce mod p
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.myIsZeroAddMul(a,b,c)   // a = (a+b*c)%p; result is (a==0)

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

For `myExport` the choice between least non-negative and symmetric residues is determined by the convention specified when constructing the `SmallFpImpl` object. This cnvention may be either `GlobalSettings::SymmResidues` or `GlobalSettings::NonNegResidues`.

## Maintainer documentation for SmallFpDoubleImpl

Most functions are implemented inline, and no sanity checks are performed (except when `CoCoA_DEBUG` is enabled). The constructor does do some checking. The basic idea is to use the extra precision available in `double`s to allow larger prime finite fields than are permitted when 32-bit integers are used for all arithmetic. If fast 64-bit arithmetic becomes widespread then this class will probably become obsolete (unless you have a very fast floating point coprocessor?).

`SmallFpDoubleImpl::value_t` is simply `double`. Note that the values are always non-negative integers with maximum value less than `myModulusValue`; i.e. each residue class is represented (internally) by its least non-negative member.

To avoid problems with overflow the constructor checks that all integers from 0 to p*p-p can be represented exactly. We need to allow numbers as big as p*p-p so that `myIsZeroAddMul` can be implemented easily.

It is not strictly necessary that `myModulusValue` be prime, though division becomes only a partial map if `myModulusValue` is composite. I believe it is safest to insist that `myModulusValue` be prime -- the function `myIsDivisible` does indeed assume that `myModulusValue` is prime.

## Bugs, Shortcomings, and other ideas

The implementation is simplistic -- I wanted to dash it off quickly before going on holiday :-)