SmallFpDoubleImpl

© 2005 John Abbott
GNU Free Documentation License, Version 1.2



index page

User documentation for SmallFpDoubleImpl

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

Compared to SmallFpImpl the main difference is an implementation detail: values are represnted as doubles -- 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);   // create SmallFpDoubleImpl 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.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
  
    ModP.myOutput(cout, a);      // cout << a;

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 doubles 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 myModulus; i.e. each residue class is represented by its least non-negative member. The printed form reflects this choice of representative.

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 myModulus be prime, though division becomes only a partial map if myModulus is composite. I believe it is safest to insist that myModulus be prime -- the function myIsDivisible does indeed assume that myModulus is prime.

Bugs, Shortcomings, and other ideas

BUG: The use of IsSmallPrime in the ctor prevents use of primes whose square is too large for an unsigned long. Need a specific function which allows larger primes (on 32-bit machines).

BUG: the function myIsInteger assumes that any valid residue is small enough to fit into a long. Strictly C++ does not guarantee this.

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

Precalculating a reciprocal would probably allow faster reduction modulo myModulus in myReduceMod, myMul and myIsZeroAddMul.

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?