Changeset bb15576 in git

Timestamp:

Mar 26, 2014, 3:09:39 PM (10 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

47c384136f1b4ee402a334c1eab7f3125ac03231

Parents:

4ac5feb5ea4143bcc757962ac627d22b4d1fddff

Message:

comments by Claus Fieker (CF)

File:

• libpolys/coeffs/coeffs.h (modified) (12 diffs)

libpolys/coeffs/coeffs.h

@@ -124 +124 @@
                                 // or NULL
    // general stuff
+   //   if the ring has a meaningful Euclidean structure, hopefully
+   //   supported by cfQuotRem, then
+   //     IntMod, IntDiv should give the same result
+   //     IntDiv(a,b) = QuotRem(a,b, &IntMod(a,b))
+   //   if the ring is not Euclidean, then IntMod should return 0
+   //   and IntDiv the exact quotient. It is assumed that the function is
+   //   ONLY called on Euclidean rings or in the case of an exact division.
+   //
+   //   cfDiv does an exact division, but has to handle illegal input
+   //   cfExactDiv does an exact division, but no error checking
+   //   (I'm not sure I understant and even less that this makes sense)
    numberfunc cfMult, cfSub ,cfAdd ,cfDiv, cfIntDiv, cfIntMod, cfExactDiv;
 
@@ -159 +170 @@
    void    (*cfWriteShort)(number &a, const coeffs r);
 
+   // it is legal, but not always useful to have cfRead(s, a, r)
+   //   just return s again.
+   // Useful application (read constants which are not an projection
+   // from int/bigint:
+   // Let ring r = R,x,dp;
+   // where R is a coeffs having "special" "named" elements (ie.
+   // the primitive element in some algebraic extension).
+   // If there is no interpreter variable of the same name, it is
+   // difficult to create non-trivial elements in R.
+   // Hence one can use the string to allow creation of R-elts using the
+   // unbound name of the special element.
    const char *  (*cfRead)(const char * s, number * a, const coeffs r);
+
    void    (*cfNormalize)(number &a, const coeffs r);
-
-
 
    BOOLEAN (*cfGreater)(number a,number b, const coeffs r),
@@ -170 +191 @@
            (*cfIsOne)(number a, const coeffs r),
            (*cfIsMOne)(number a, const coeffs r),
+       //GreaterZero is used for printing of polynomials:
+       //  a "+" is only printed in front of a coefficient
+       //  if the element is >0. It is assumed that any element
+       //  failing this will start printing with a leading "-"
            (*cfGreaterZero)(number a, const coeffs r);
 
@@ -175 +200 @@
    number  (*cfGetDenom)(number &n, const coeffs r);
    number  (*cfGetNumerator)(number &n, const coeffs r);
+   //CF: a Euclidean ring is a commutative, unitary ring with an Euclidean
+   //  function f s.th. for all a,b in R, b ne 0, we can find q, r s.th.
+   //  a = qb+r and either r=0 or f(r) < f(b)
+   //  Note that neither q nor r nor f(r) are unique.
    number  (*cfGcd)(number a, number b, const coeffs r);
    number  (*cfExtGcd)(number a, number b, number *s, number *t,const coeffs r);
+   //given a and b in a Euclidean setting, return s,t,u,v sth.
+   //  sa + tb = gcd
+   //  ua + vb = 0
+   //  sv + tu = 1
+   //  ie. the 2x2 matrix (s t | u v) is unimodular and maps (a,b) to (g, 0)
+   //CF: note, in general, this cannot be derived from ExtGcd due to
+   //    zero divisors
+   number  (*cfXExtGcd)(number a, number b, number *s, number *t, number *u, number *v, const coeffs r);
+   //in a Euclidean ring, return the Euclidean norm as a bigint (of type number)
+   number  (*cfEucNorm)(number a, const coeffs r);
+   //in a principal ideal ring (with zero divisors): the annihilator
+   number  (*cfAnn)(number a, const coeffs r);
+   //find a "canonical representative of a modulo the units of r
+   //return NULL if a is already normalized
+   //otherwise, the factor.
+   //(for Z: make positive, for z/nZ make the gcd with n
+   //aparently it is GetUnit!
+   //in a Euclidean ring, return the quotient and compute the remainder
+   //rem can be NULL
+   number  (*cfQuotRem)(number a, number b, number *rem, const coeffs r);
    number  (*cfLcm)(number a, number b, const coeffs r);
    void    (*cfDelete)(number * a, const coeffs r);
+
+   //CF: tries to find a canonical map from src -> dst
    nMapFunc (*cfSetMap)(const coeffs src, const coeffs dst);
 
@@ -199 +250 @@
    number  (*cfInit_bigint)(number i, const coeffs dummy, const coeffs dst);
 
-   /// rational reconstruction: best rational with mod p=n
+   /// rational reconstruction: "best" rational a/b with a/b = p mod n
+   //  or a = bp mod n
+   //  CF: no idea what this would be in general
+   //     it seems to be extended to operate coefficient wise in extensions.
+   //     I presume then n in coeffs_BIGINT while p in coeffs
    number  (*cfFarey)(number p, number n, const coeffs);
 
    /// chinese remainder
    /// returns X with X mod q[i]=x[i], i=0..rl-1
+   //CF: by the looks of it: q[i] in Z (coeffs_BIGINT)
+   //    strange things happen in naChineseRemainder for example.
    number  (*cfChineseRemainder)(number *x, number *q,int rl, BOOLEAN sym,const coeffs);
 
@@ -218 +275 @@
    nCoeffsEnumeratorFunc cfClearDenominators;
 
+   /// conversion to CanonicalForm(factory) to number
    number (*convFactoryNSingN)( const CanonicalForm n, const coeffs r);
    CanonicalForm (*convSingNFactoryN)( number n, BOOLEAN setChar, const coeffs r );
@@ -294 +352 @@
    BOOLEAN (*cfIsUnit)(number a,const coeffs r);
    number  (*cfGetUnit)(number a,const coeffs r);
+   //CF: test if b divides a
    BOOLEAN (*cfDivBy)(number a, number b, const coeffs r);
   /* The following members are for representing the ring Z/n,
@@ -319 +378 @@
   unsigned long mod2mMask;
 #endif
+  /*CF: for blackbox rings */
+  void * data;
 #ifdef LDEBUG
    // must be last entry:
@@ -441 +502 @@
 /// in Z/2^kZ: largest odd divisor of n (taken in Z)
 /// other cases: not implemented
+// CF: shold imply that n/GetUnit(n) is normalized in Z/kZ
+//   it would make more sense to return the inverse...
 static inline number n_GetUnit(number n, const coeffs r)
 { assume(r != NULL); assume(r->cfGetUnit!=NULL); return r->cfGetUnit(n,r); }
@@ -490 +553 @@
 
 /// write to the output buffer of the currently used reporter
+//CF: the "&" should be removed, as one wants to write constants as well
 static inline void   n_WriteLong(number& n,  const coeffs r)
 { assume(r != NULL); assume(r->cfWriteLong!=NULL); r->cfWriteLong(n,r); }
@@ -558 +622 @@
 /// in K(t_1, ..., t_n): return a/b
 /// other fields: not implemented
+// CF: see above: should be part of euclidean structure.
+//   Needs to be implemented as pnBin relies on it.
+//   Probably should default to Div.
 static inline number n_IntDiv(number a, number b, const coeffs r)
 { assume(r != NULL); assume(r->cfIntDiv!=NULL); return r->cfIntDiv(a,b,r); }
@@ -584 +651 @@
 static inline number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
 { assume(r != NULL); assume(r->cfExtGcd!=NULL); return r->cfExtGcd (a,b,s,t,r); }
+static inline number n_XExtGcd(number a, number b, number *s, number *t, number *u, number *v, const coeffs r)
+{ assume(r != NULL); assume(r->cfXExtGcd!=NULL); return r->cfXExtGcd (a,b,s,t,u,v,r); }
+static inline number  n_EucNorm(number a, const coeffs r)
+{ assume(r != NULL); assume(r->cfEucNorm!=NULL); return r->cfEucNorm (a,r); }
+static inline number  n_Ann(number a, const coeffs r)
+{ assume(r != NULL); assume(r->cfAnn!=NULL); return r->cfAnn (a,r); }
+static inline number  n_QuotRem(number a, number b, number *q, const coeffs r)
+{ assume(r != NULL); assume(r->cfQuotRem!=NULL); return r->cfQuotRem (a,b,q,r); }
+
 
 /// in Z: return the lcm of 'a' and 'b'