Changeset bb15576 in git

Mar 26, 2014, 3:09:39 PM (10 years ago)
Hans Schoenemann <hannes@…>
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
comments by Claus Fieker (CF)
1 edited


  • libpolys/coeffs/coeffs.h

    r4ac5fe rbb15576  
    124124                                // or NULL
    125125   // general stuff
     126   //   if the ring has a meaningful Euclidean structure, hopefully
     127   //   supported by cfQuotRem, then
     128   //     IntMod, IntDiv should give the same result
     129   //     IntDiv(a,b) = QuotRem(a,b, &IntMod(a,b))
     130   //   if the ring is not Euclidean, then IntMod should return 0
     131   //   and IntDiv the exact quotient. It is assumed that the function is
     132   //   ONLY called on Euclidean rings or in the case of an exact division.
     133   //
     134   //   cfDiv does an exact division, but has to handle illegal input
     135   //   cfExactDiv does an exact division, but no error checking
     136   //   (I'm not sure I understant and even less that this makes sense)
    126137   numberfunc cfMult, cfSub ,cfAdd ,cfDiv, cfIntDiv, cfIntMod, cfExactDiv;
    159170   void    (*cfWriteShort)(number &a, const coeffs r);
     172   // it is legal, but not always useful to have cfRead(s, a, r)
     173   //   just return s again.
     174   // Useful application (read constants which are not an projection
     175   // from int/bigint:
     176   // Let ring r = R,x,dp;
     177   // where R is a coeffs having "special" "named" elements (ie.
     178   // the primitive element in some algebraic extension).
     179   // If there is no interpreter variable of the same name, it is
     180   // difficult to create non-trivial elements in R.
     181   // Hence one can use the string to allow creation of R-elts using the
     182   // unbound name of the special element.
    161183   const char *  (*cfRead)(const char * s, number * a, const coeffs r);
    162185   void    (*cfNormalize)(number &a, const coeffs r);
    166187   BOOLEAN (*cfGreater)(number a,number b, const coeffs r),
    170191           (*cfIsOne)(number a, const coeffs r),
    171192           (*cfIsMOne)(number a, const coeffs r),
     193       //GreaterZero is used for printing of polynomials:
     194       //  a "+" is only printed in front of a coefficient
     195       //  if the element is >0. It is assumed that any element
     196       //  failing this will start printing with a leading "-"
    172197           (*cfGreaterZero)(number a, const coeffs r);
    175200   number  (*cfGetDenom)(number &n, const coeffs r);
    176201   number  (*cfGetNumerator)(number &n, const coeffs r);
     202   //CF: a Euclidean ring is a commutative, unitary ring with an Euclidean
     203   //  function f for all a,b in R, b ne 0, we can find q, r
     204   //  a = qb+r and either r=0 or f(r) < f(b)
     205   //  Note that neither q nor r nor f(r) are unique.
    177206   number  (*cfGcd)(number a, number b, const coeffs r);
    178207   number  (*cfExtGcd)(number a, number b, number *s, number *t,const coeffs r);
     208   //given a and b in a Euclidean setting, return s,t,u,v sth.
     209   //  sa + tb = gcd
     210   //  ua + vb = 0
     211   //  sv + tu = 1
     212   //  ie. the 2x2 matrix (s t | u v) is unimodular and maps (a,b) to (g, 0)
     213   //CF: note, in general, this cannot be derived from ExtGcd due to
     214   //    zero divisors
     215   number  (*cfXExtGcd)(number a, number b, number *s, number *t, number *u, number *v, const coeffs r);
     216   //in a Euclidean ring, return the Euclidean norm as a bigint (of type number)
     217   number  (*cfEucNorm)(number a, const coeffs r);
     218   //in a principal ideal ring (with zero divisors): the annihilator
     219   number  (*cfAnn)(number a, const coeffs r);
     220   //find a "canonical representative of a modulo the units of r
     221   //return NULL if a is already normalized
     222   //otherwise, the factor.
     223   //(for Z: make positive, for z/nZ make the gcd with n
     224   //aparently it is GetUnit!
     225   //in a Euclidean ring, return the quotient and compute the remainder
     226   //rem can be NULL
     227   number  (*cfQuotRem)(number a, number b, number *rem, const coeffs r);
    179228   number  (*cfLcm)(number a, number b, const coeffs r);
    180229   void    (*cfDelete)(number * a, const coeffs r);
     231   //CF: tries to find a canonical map from src -> dst
    181232   nMapFunc (*cfSetMap)(const coeffs src, const coeffs dst);
    199250   number  (*cfInit_bigint)(number i, const coeffs dummy, const coeffs dst);
    201    /// rational reconstruction: best rational with mod p=n
     252   /// rational reconstruction: "best" rational a/b with a/b = p mod n
     253   //  or a = bp mod n
     254   //  CF: no idea what this would be in general
     255   //     it seems to be extended to operate coefficient wise in extensions.
     256   //     I presume then n in coeffs_BIGINT while p in coeffs
    202257   number  (*cfFarey)(number p, number n, const coeffs);
    204259   /// chinese remainder
    205260   /// returns X with X mod q[i]=x[i], i=0..rl-1
     261   //CF: by the looks of it: q[i] in Z (coeffs_BIGINT)
     262   //    strange things happen in naChineseRemainder for example.
    206263   number  (*cfChineseRemainder)(number *x, number *q,int rl, BOOLEAN sym,const coeffs);
    218275   nCoeffsEnumeratorFunc cfClearDenominators;
     277   /// conversion to CanonicalForm(factory) to number
    220278   number (*convFactoryNSingN)( const CanonicalForm n, const coeffs r);
    221279   CanonicalForm (*convSingNFactoryN)( number n, BOOLEAN setChar, const coeffs r );
    294352   BOOLEAN (*cfIsUnit)(number a,const coeffs r);
    295353   number  (*cfGetUnit)(number a,const coeffs r);
     354   //CF: test if b divides a
    296355   BOOLEAN (*cfDivBy)(number a, number b, const coeffs r);
    297356  /* The following members are for representing the ring Z/n,
    319378  unsigned long mod2mMask;
     380  /*CF: for blackbox rings */
     381  void * data;
    321382#ifdef LDEBUG
    322383   // must be last entry:
    441502/// in Z/2^kZ: largest odd divisor of n (taken in Z)
    442503/// other cases: not implemented
     504// CF: shold imply that n/GetUnit(n) is normalized in Z/kZ
     505//   it would make more sense to return the inverse...
    443506static inline number n_GetUnit(number n, const coeffs r)
    444507{ assume(r != NULL); assume(r->cfGetUnit!=NULL); return r->cfGetUnit(n,r); }
    491554/// write to the output buffer of the currently used reporter
     555//CF: the "&" should be removed, as one wants to write constants as well
    492556static inline void   n_WriteLong(number& n,  const coeffs r)
    493557{ assume(r != NULL); assume(r->cfWriteLong!=NULL); r->cfWriteLong(n,r); }
    558622/// in K(t_1, ..., t_n): return a/b
    559623/// other fields: not implemented
     624// CF: see above: should be part of euclidean structure.
     625//   Needs to be implemented as pnBin relies on it.
     626//   Probably should default to Div.
    560627static inline number n_IntDiv(number a, number b, const coeffs r)
    561628{ assume(r != NULL); assume(r->cfIntDiv!=NULL); return r->cfIntDiv(a,b,r); }
    584651static inline number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
    585652{ assume(r != NULL); assume(r->cfExtGcd!=NULL); return r->cfExtGcd (a,b,s,t,r); }
     653static inline number n_XExtGcd(number a, number b, number *s, number *t, number *u, number *v, const coeffs r)
     654{ assume(r != NULL); assume(r->cfXExtGcd!=NULL); return r->cfXExtGcd (a,b,s,t,u,v,r); }
     655static inline number  n_EucNorm(number a, const coeffs r)
     656{ assume(r != NULL); assume(r->cfEucNorm!=NULL); return r->cfEucNorm (a,r); }
     657static inline number  n_Ann(number a, const coeffs r)
     658{ assume(r != NULL); assume(r->cfAnn!=NULL); return r->cfAnn (a,r); }
     659static inline number  n_QuotRem(number a, number b, number *q, const coeffs r)
     660{ assume(r != NULL); assume(r->cfQuotRem!=NULL); return r->cfQuotRem (a,b,q,r); }
    587663/// in Z: return the lcm of 'a' and 'b'
Note: See TracChangeset for help on using the changeset viewer.