modulop.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers modulo p (<=32749)
6 */
7 
8 #include <misc/auxiliary.h>
9 #include <omalloc/omalloc.h>
10 
11 #include <factory/factory.h>
12 
13 #include <misc/mylimits.h>
14 #include <misc/sirandom.h>
15 
16 #include <reporter/reporter.h>
17 
18 #include <coeffs/coeffs.h>
19 #include <coeffs/numbers.h>
20 #include <coeffs/mpr_complex.h>
21 
22 #include "longrat.h"
23 #include "modulop.h"
24 
25 #include <string.h>
26 
27 BOOLEAN npGreaterZero (number k, const coeffs r);
28 number npMult (number a, number b, const coeffs r);
29 number npInit (long i, const coeffs r);
30 long npInt (number &n, const coeffs r);
31 number npAdd (number a, number b,const coeffs r);
32 number npSub (number a, number b,const coeffs r);
33 void npPower (number a, int i, number * result,const coeffs r);
34 BOOLEAN npIsZero (number a,const coeffs r);
35 BOOLEAN npIsOne (number a,const coeffs r);
36 BOOLEAN npIsMOne (number a,const coeffs r);
37 number npDiv (number a, number b,const coeffs r);
38 number npNeg (number c,const coeffs r);
39 number npInvers (number c,const coeffs r);
40 BOOLEAN npGreater (number a, number b,const coeffs r);
41 BOOLEAN npEqual (number a, number b,const coeffs r);
42 void npWrite (number a, const coeffs r);
43 void npCoeffWrite (const coeffs r, BOOLEAN details);
44 const char * npRead (const char *s, number *a,const coeffs r);
45 
46 #ifdef LDEBUG
47 BOOLEAN npDBTest (number a, const char *f, const int l, const coeffs r);
48 #endif
49 
50 nMapFunc npSetMap(const coeffs src, const coeffs dst);
51 
52 #ifdef NV_OPS
53 #pragma GCC diagnostic ignored "-Wlong-long"
54 static inline number nvMultM(number a, number b, const coeffs r)
55 {
56  assume( getCoeffType(r) == n_Zp );
57 
58 #if SIZEOF_LONG == 4
59 #define ULONG64 (unsigned long long)(unsigned long)
60 #else
61 #define ULONG64 (unsigned long)
62 #endif
63  return (number)
64  (unsigned long)((ULONG64 a)*(ULONG64 b) % (ULONG64 r->ch));
65 }
66 number nvMult (number a, number b, const coeffs r);
67 number nvDiv (number a, number b, const coeffs r);
68 number nvInvers (number c, const coeffs r);
69 //void nvPower (number a, int i, number * result, const coeffs r);
70 #endif
71 
72 BOOLEAN npGreaterZero (number k, const coeffs r)
73 {
74  n_Test(k, r);
75 
76  int h = (int)((long) k);
77  return ((int)h !=0) && (h <= (r->ch>>1));
78 }
79 
80 //unsigned long npMultMod(unsigned long a, unsigned long b, int npPrimeM)
81 //{
82 // unsigned long c = a*b;
83 // c = c % npPrimeM;
84 // assume(c == (unsigned long) npMultM((number) a, (number) b, npPrimeM));
85 // return c;
86 //}
87 
88 number npMult (number a,number b, const coeffs r)
89 {
90  n_Test(a, r);
91  n_Test(b, r);
92 
93  if (((long)a == 0) || ((long)b == 0))
94  return (number)0;
95  number c = npMultM(a,b, r);
96  n_Test(c, r);
97  return c;
98 }
99 
100 /*2
101 * create a number from int
102 */
103 number npInit (long i, const coeffs r)
104 {
105  long ii=i % (long)r->ch;
106  if (ii < 0L) ii += (long)r->ch;
107 
108  number c = (number)ii;
109  n_Test(c, r);
110  return c;
111 }
112 
113 
114 /*2
115  * convert a number to an int in (-p/2 .. p/2]
116  */
117 long npInt(number &n, const coeffs r)
118 {
119  n_Test(n, r);
120 
121  if ((long)n > (((long)r->ch) >>1)) return ((long)n -((long)r->ch));
122  else return ((long)n);
123 }
124 
125 number npAdd (number a, number b, const coeffs r)
126 {
127  n_Test(a, r);
128  n_Test(b, r);
129 
130  number c = npAddM(a,b, r);
131 
132  n_Test(c, r);
133 
134  return c;
135 }
136 
137 number npSub (number a, number b, const coeffs r)
138 {
139  n_Test(a, r);
140  n_Test(b, r);
141 
142  number c = npSubM(a,b,r);
143 
144  n_Test(c, r);
145 
146  return c;
147 }
148 
149 BOOLEAN npIsZero (number a, const coeffs r)
150 {
151  n_Test(a, r);
152 
153  return 0 == (long)a;
154 }
155 
156 BOOLEAN npIsOne (number a, const coeffs r)
157 {
158  n_Test(a, r);
159 
160  return 1 == (long)a;
161 }
162 
163 BOOLEAN npIsMOne (number a, const coeffs r)
164 {
165  n_Test(a, r);
166 
167  return ((r->npPminus1M == (long)a) &&(1L!=(long)a))/*for char 2*/;
168 }
169 
170 #ifdef HAVE_DIV_MOD
171 
172 #ifdef USE_NTL_XGCD
173 
174 //ifdef HAVE_NTL // in ntl.a
175 //extern void XGCD(long& d, long& s, long& t, long a, long b);
176 #include <NTL/ZZ.h>
177 #ifdef NTL_CLIENT
178 NTL_CLIENT
179 #endif
180 
181 #endif
182 
183 long InvMod(long a, const coeffs R)
184 {
185  long d, s, t;
186 
187 #ifdef USE_NTL_XGCD
188  XGCD(d, s, t, a, R->ch);
189  assume (d == 1);
190 #else
191  long u, v, u0, v0, u1, v1, u2, v2, q, r;
192 
193  assume(a>0);
194  u1=1; u2=0;
195  u = a; v = R->ch;
196 
197  while (v != 0)
198  {
199  q = u / v;
200  r = u % v;
201  u = v;
202  v = r;
203  u0 = u2;
204  u2 = u1 - q*u2;
205  u1 = u0;
206  }
207 
208  assume(u==1);
209  s = u1;
210 #endif
211  if (s < 0)
212  return s + R->ch;
213  else
214  return s;
215 }
216 #endif
217 
218 inline number npInversM (number c, const coeffs r)
219 {
220  n_Test(c, r);
221 #ifndef HAVE_DIV_MOD
222  number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
223 #else
224  long inv=(long)r->npInvTable[(long)c];
225  if (inv==0)
226  {
227  inv=InvMod((long)c,r);
228  r->npInvTable[(long)c]=inv;
229  }
230  number d = (number)inv;
231 #endif
232  n_Test(d, r);
233  return d;
234 
235 }
236 
237 number npDiv (number a,number b, const coeffs r)
238 {
239  n_Test(a, r);
240  n_Test(b, r);
241 
242 //#ifdef NV_OPS
243 // if (r->ch>NV_MAX_PRIME)
244 // return nvDiv(a,b);
245 //#endif
246  if ((long)a==0L)
247  return (number)0L;
248  number d;
249 
250 #ifndef HAVE_DIV_MOD
251  if ((long)b==0L)
252  {
253  WerrorS(nDivBy0);
254  return (number)0L;
255  }
256 
257  int s = r->npLogTable[(long)a] - r->npLogTable[(long)b];
258  if (s < 0)
259  s += r->npPminus1M;
260  d = (number)(long)r->npExpTable[s];
261 #else
262  number inv=npInversM(b,r);
263  d = npMultM(a,inv,r);
264 #endif
265 
266  n_Test(d, r);
267  return d;
268 
269 }
270 number npInvers (number c, const coeffs r)
271 {
272  n_Test(c, r);
273 
274  if ((long)c==0L)
275  {
276  WerrorS("1/0");
277  return (number)0L;
278  }
279  number d = npInversM(c,r);
280 
281  n_Test(d, r);
282  return d;
283 }
284 
285 number npNeg (number c, const coeffs r)
286 {
287  n_Test(c, r);
288 
289  if ((long)c==0L) return c;
290 
291 #if 0
292  number d = npNegM(c,r);
293  n_Test(d, r);
294  return d;
295 #else
296  c = npNegM(c,r);
297  n_Test(c, r);
298  return c;
299 #endif
300 }
301 
302 BOOLEAN npGreater (number a,number b, const coeffs r)
303 {
304  n_Test(a, r);
305  n_Test(b, r);
306 
307  //return (long)a != (long)b;
308  return ((long)a) > ((long)b);
309 }
310 
311 BOOLEAN npEqual (number a,number b, const coeffs r)
312 {
313  n_Test(a, r);
314  n_Test(b, r);
315 
316 // return (long)a == (long)b;
317 
318  return npEqualM(a,b,r);
319 }
320 
321 void npWrite (number a, const coeffs r)
322 {
323  n_Test(a, r);
324 
325  if ((long)a>(((long)r->ch) >>1)) StringAppend("-%d",(int)(((long)r->ch)-((long)a)));
326  else StringAppend("%d",(int)((long)a));
327 }
328 
329 #if 0
330 void npPower (number a, int i, number * result, const coeffs r)
331 {
332  n_Test(a, r);
333 
334  if (i==0)
335  {
336  //npInit(1,result);
337  *(long *)result = 1;
338  }
339  else if (i==1)
340  {
341  *result = a;
342  }
343  else
344  {
345  npPower(a,i-1,result,r);
346  *result = npMultM(a,*result,r);
347  }
348 }
349 #endif
350 
351 static const char* npEati(const char *s, int *i, const coeffs r)
352 {
353  if (((*s) >= '0') && ((*s) <= '9'))
354  {
355  unsigned long ii=0L;
356  do
357  {
358  ii *= 10;
359  ii += *s++ - '0';
360  if (ii >= (MAX_INT_VAL / 10)) ii = ii % r->ch;
361  }
362  while (((*s) >= '0') && ((*s) <= '9'));
363  if (ii >= (unsigned long)r->ch) ii = ii % r->ch;
364  *i=(int)ii;
365  }
366  else (*i) = 1;
367  return s;
368 }
369 
370 const char * npRead (const char *s, number *a, const coeffs r)
371 {
372  int z;
373  int n=1;
374 
375  s = npEati(s, &z, r);
376  if ((*s) == '/')
377  {
378  s++;
379  s = npEati(s, &n, r);
380  }
381  if (n == 1)
382  *a = (number)(long)z;
383  else
384  {
385  if ((z==0)&&(n==0)) WerrorS(nDivBy0);
386  else
387  {
388 #ifdef NV_OPS
389  if (r->ch>NV_MAX_PRIME)
390  *a = nvDiv((number)(long)z,(number)(long)n,r);
391  else
392 #endif
393  *a = npDiv((number)(long)z,(number)(long)n,r);
394  }
395  }
396  n_Test(*a, r);
397  return s;
398 }
399 
400 /*2
401 * set the charcteristic (allocate and init tables)
402 */
403 
405 {
406  #ifdef HAVE_DIV_MOD
407  if (r->npInvTable!=NULL)
408  omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) );
409  r->npInvTable=NULL;
410  #else
411  if (r->npExpTable!=NULL)
412  {
413  omFreeSize( (void *)r->npExpTable, r->ch*sizeof(unsigned short) );
414  omFreeSize( (void *)r->npLogTable, r->ch*sizeof(unsigned short) );
415  r->npExpTable=NULL; r->npLogTable=NULL;
416  }
417  #endif
418 }
419 
420 static BOOLEAN npCoeffsEqual(const coeffs r, n_coeffType n, void * parameter)
421 {
422  /* test, if r is an instance of nInitCoeffs(n,parameter) */
423  return (n==n_Zp) && (r->ch==(int)(long)parameter);
424 }
425 CanonicalForm npConvSingNFactoryN( number n, BOOLEAN setChar, const coeffs r )
426 {
427  if (setChar) setCharacteristic( r->ch );
428  CanonicalForm term(npInt( n,r ));
429  return term;
430 }
431 
432 number npConvFactoryNSingN( const CanonicalForm n, const coeffs r)
433 {
434  if (n.isImm())
435  {
436  return npInit(n.intval(),r);
437  }
438  else
439  {
440  assume(0);
441  return NULL;
442  }
443 }
444 
445 static char* npCoeffName(const coeffs cf)
446 {
447  static char npCoeffName_buf[15];
448  snprintf(npCoeffName_buf,14,"ZZ/%d",cf->ch);
449  return npCoeffName_buf;
450 }
451 
452 static char* npCoeffString(const coeffs cf)
453 {
454  return omStrDup(npCoeffName(cf));
455 }
456 
457 static void npWriteFd(number n, FILE* f, const coeffs)
458 {
459  fprintf(f,"%d ",(int)(long)n);
460 }
461 
462 static number npReadFd(s_buff f, const coeffs)
463 {
464  // read int
465  int dd;
466  dd=s_readint(f);
467  return (number)(long)dd;
468 }
469 
470 static number npRandom(siRandProc p, number, number, const coeffs cf)
471 {
472  return npInit(p(),cf);
473 }
474 
476 {
477  assume( getCoeffType(r) == n_Zp );
478  const int c = (int) (long) p;
479 
480  assume( c > 0 );
481 
482  int i, w;
483 
484  r->is_field=TRUE;
485  r->is_domain=TRUE;
486  r->rep=n_rep_int;
487 
488  r->ch = c;
489  r->npPminus1M = c /*r->ch*/ - 1;
490 
491  //r->cfInitChar=npInitChar;
492  r->cfKillChar=npKillChar;
493  r->nCoeffIsEqual=npCoeffsEqual;
494  r->cfCoeffString=npCoeffString;
495  r->cfCoeffName=npCoeffName;
496  r->cfCoeffWrite=npCoeffWrite;
497 
498  r->cfMult = npMult;
499  r->cfSub = npSub;
500  r->cfAdd = npAdd;
501  r->cfDiv = npDiv;
502  r->cfInit = npInit;
503  //r->cfSize = ndSize;
504  r->cfInt = npInt;
505  #ifdef HAVE_RINGS
506  //r->cfDivComp = NULL; // only for ring stuff
507  //r->cfIsUnit = NULL; // only for ring stuff
508  //r->cfGetUnit = NULL; // only for ring stuff
509  //r->cfExtGcd = NULL; // only for ring stuff
510  // r->cfDivBy = NULL; // only for ring stuff
511  #endif
512  r->cfInpNeg = npNeg;
513  r->cfInvers= npInvers;
514  //r->cfCopy = ndCopy;
515  //r->cfRePart = ndCopy;
516  //r->cfImPart = ndReturn0;
517  r->cfWriteLong = npWrite;
518  r->cfRead = npRead;
519  //r->cfNormalize=ndNormalize;
520  r->cfGreater = npGreater;
521  r->cfEqual = npEqual;
522  r->cfIsZero = npIsZero;
523  r->cfIsOne = npIsOne;
524  r->cfIsMOne = npIsMOne;
525  r->cfGreaterZero = npGreaterZero;
526  //r->cfPower = npPower;
527  //r->cfGetDenom = ndGetDenom;
528  //r->cfGetNumerator = ndGetNumerator;
529  //r->cfGcd = ndGcd;
530  //r->cfLcm = ndGcd;
531  //r->cfDelete= ndDelete;
532  r->cfSetMap = npSetMap;
533  //r->cfName = ndName;
534  //r->cfInpMult=ndInpMult;
535 #ifdef NV_OPS
536  if (c>NV_MAX_PRIME)
537  {
538  r->cfMult = nvMult;
539  r->cfDiv = nvDiv;
540  r->cfExactDiv= nvDiv;
541  r->cfInvers= nvInvers;
542  //r->cfPower= nvPower;
543  }
544 #endif
545 #ifdef LDEBUG
546  // debug stuff
547  r->cfDBTest=npDBTest;
548 #endif
549 
550  r->convSingNFactoryN=npConvSingNFactoryN;
551  r->convFactoryNSingN=npConvFactoryNSingN;
552 
553  r->cfRandom=npRandom;
554 
555  // io via ssi
556  r->cfWriteFd=npWriteFd;
557  r->cfReadFd=npReadFd;
558 
559  // the variables:
560  r->nNULL = (number)0;
561  r->type = n_Zp;
562  r->has_simple_Alloc=TRUE;
563  r->has_simple_Inverse=TRUE;
564 
565  // the tables
566 #ifdef NV_OPS
567  if (r->ch <=NV_MAX_PRIME)
568 #endif
569  {
570 #if !defined(HAVE_DIV_MOD) || !defined(HAVE_MULT_MOD)
571  r->npExpTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
572  r->npLogTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
573  r->npExpTable[0] = 1;
574  r->npLogTable[0] = 0;
575  if (r->ch > 2)
576  {
577  w = 1;
578  loop
579  {
580  r->npLogTable[1] = 0;
581  w++;
582  i = 0;
583  loop
584  {
585  i++;
586  r->npExpTable[i] =(int)(((long)w * (long)r->npExpTable[i-1]) % r->ch);
587  r->npLogTable[r->npExpTable[i]] = i;
588  if /*(i == r->ch - 1 ) ||*/ (/*(*/ r->npExpTable[i] == 1 /*)*/)
589  break;
590  }
591  if (i == r->ch - 1)
592  break;
593  }
594  }
595  else
596  {
597  r->npExpTable[1] = 1;
598  r->npLogTable[1] = 0;
599  }
600 #endif
601 #ifdef HAVE_DIV_MOD
602  r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
603 #endif
604  }
605  return FALSE;
606 }
607 
608 #ifdef LDEBUG
609 BOOLEAN npDBTest (number a, const char *f, const int l, const coeffs r)
610 {
611  if (((long)a<0L) || ((long)a>(long)r->ch))
612  {
613  Print("wrong mod p number %ld at %s,%d\n",(long)a,f,l);
614  return FALSE;
615  }
616  return TRUE;
617 }
618 #endif
619 
620 static number npMapP(number from, const coeffs src, const coeffs dst_r)
621 {
622  long i = (long)from;
623  if (i>src->ch/2)
624  {
625  i-=src->ch;
626  while (i < 0) i+=dst_r->ch;
627  }
628  i%=dst_r->ch;
629  return (number)i;
630 }
631 
632 static number npMapLongR(number from, const coeffs /*src*/, const coeffs dst_r)
633 {
634  gmp_float *ff=(gmp_float*)from;
635  mpf_t *f=ff->_mpfp();
636  number res;
637  mpz_ptr dest,ndest;
638  int size,i;
639  int e,al,bl;
640  long iz;
641  mp_ptr qp,dd,nn;
642 
643  size = (*f)[0]._mp_size;
644  if (size == 0)
645  return npInit(0,dst_r);
646  if(size<0)
647  size = -size;
648 
649  qp = (*f)[0]._mp_d;
650  while(qp[0]==0)
651  {
652  qp++;
653  size--;
654  }
655 
656  if(dst_r->ch>2)
657  e=(*f)[0]._mp_exp-size;
658  else
659  e=0;
660  res = ALLOC_RNUMBER();
661 #if defined(LDEBUG)
662  res->debug=123456;
663 #endif
664  dest = res->z;
665 
666  long in=0;
667  if (e<0)
668  {
669  al = dest->_mp_size = size;
670  if (al<2) al = 2;
671  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
672  for (i=0;i<size;i++) dd[i] = qp[i];
673  bl = 1-e;
674  nn = (mp_ptr)omAlloc(sizeof(mp_limb_t)*bl);
675  nn[bl-1] = 1;
676  for (i=bl-2;i>=0;i--) nn[i] = 0;
677  ndest = res->n;
678  ndest->_mp_d = nn;
679  ndest->_mp_alloc = ndest->_mp_size = bl;
680  res->s = 0;
681  in=mpz_fdiv_ui(ndest,dst_r->ch);
682  mpz_clear(ndest);
683  }
684  else
685  {
686  al = dest->_mp_size = size+e;
687  if (al<2) al = 2;
688  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
689  for (i=0;i<size;i++) dd[i+e] = qp[i];
690  for (i=0;i<e;i++) dd[i] = 0;
691  res->s = 3;
692  }
693 
694  dest->_mp_d = dd;
695  dest->_mp_alloc = al;
696  iz=mpz_fdiv_ui(dest,dst_r->ch);
697  mpz_clear(dest);
698  if(res->s==0)
699  iz=(long)npDiv((number)iz,(number)in,dst_r);
700  FREE_RNUMBER(res); // Q!?
701  return (number)iz;
702 }
703 
704 #ifdef HAVE_RINGS
705 /*2
706 * convert from a GMP integer
707 */
708 static number npMapGMP(number from, const coeffs /*src*/, const coeffs dst)
709 {
710  mpz_ptr erg = (mpz_ptr) omAlloc(sizeof(mpz_t)); // evtl. spaeter mit bin
711  mpz_init(erg);
712 
713  mpz_mod_ui(erg, (mpz_ptr) from, dst->ch);
714  number r = (number) mpz_get_si(erg);
715 
716  mpz_clear(erg);
717  omFree((void *) erg);
718  return (number) r;
719 }
720 
721 static number npMapZ(number from, const coeffs src, const coeffs dst)
722 {
723  if (SR_HDL(from) & SR_INT)
724  {
725  long f_i=SR_TO_INT(from);
726  return npInit(f_i,dst);
727  }
728  return npMapGMP(from,src,dst);
729 }
730 
731 /*2
732 * convert from an machine long
733 */
734 static number npMapMachineInt(number from, const coeffs /*src*/,const coeffs dst)
735 {
736  long i = (long) (((unsigned long) from) % dst->ch);
737  return (number) i;
738 }
739 #endif
740 
741 static number npMapCanonicalForm (number a, const coeffs /*src*/, const coeffs dst)
742 {
743  setCharacteristic (dst ->ch);
745  return (number) (f.intval());
746 }
747 
748 nMapFunc npSetMap(const coeffs src, const coeffs dst)
749 {
750 #ifdef HAVE_RINGS
751  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src))
752  {
753  return npMapMachineInt;
754  }
755  if (src->rep==n_rep_gmp) //nCoeff_is_Ring_Z(src) || nCoeff_is_Ring_PtoM(src) || nCoeff_is_Ring_ModN(src))
756  {
757  return npMapGMP;
758  }
759  if (src->rep==n_rep_gap_gmp) //nCoeff_is_Ring_Z(src)
760  {
761  return npMapZ;
762  }
763 #endif
764  if (src->rep==n_rep_gap_rat) /* Q, Z */
765  {
766  return nlModP; // npMap0; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
767  }
768  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) )
769  {
770  if (n_GetChar(src) == n_GetChar(dst))
771  {
772  return ndCopyMap;
773  }
774  else
775  {
776  return npMapP;
777  }
778  }
779  if ((src->rep==n_rep_gmp_float) && nCoeff_is_long_R(src))
780  {
781  return npMapLongR;
782  }
783  if (nCoeff_is_CF (src))
784  {
785  return npMapCanonicalForm;
786  }
787  return NULL; /* default */
788 }
789 
790 // -----------------------------------------------------------
791 // operation for very large primes (32749< p < 2^31-1)
792 // ----------------------------------------------------------
793 #ifdef NV_OPS
794 
795 number nvMult (number a,number b, const coeffs r)
796 {
797  //if (((long)a == 0) || ((long)b == 0))
798  // return (number)0;
799  //else
800  return nvMultM(a,b,r);
801 }
802 
803 void nvInpMult(number &a, number b, const coeffs r)
804 {
805  number n=nvMultM(a,b,r);
806  a=n;
807 }
808 
809 
810 inline long nvInvMod(long a, const coeffs R)
811 {
812 #ifdef HAVE_DIV_MOD
813  return InvMod(a, R);
814 #else
815 /// TODO: use "long InvMod(long a, const coeffs R)"?!
816 
817  long s;
818 
819  long u, u0, u1, u2, q, r; // v0, v1, v2,
820 
821  u1=1; // v1=0;
822  u2=0; // v2=1;
823  u = a;
824 
825  long v = R->ch;
826 
827  while (v != 0)
828  {
829  q = u / v;
830  r = u % v;
831  u = v;
832  v = r;
833  u0 = u2;
834 // v0 = v2;
835  u2 = u1 - q*u2;
836 // v2 = v1 - q*v2;
837  u1 = u0;
838 // v1 = v0;
839  }
840 
841  s = u1;
842  //t = v1;
843  if (s < 0)
844  return s + R->ch;
845  else
846  return s;
847 #endif
848 }
849 
850 inline number nvInversM (number c, const coeffs r)
851 {
852  long inv=nvInvMod((long)c,r);
853  return (number)inv;
854 }
855 
856 number nvDiv (number a,number b, const coeffs r)
857 {
858  if ((long)a==0L)
859  return (number)0L;
860  else if ((long)b==0L)
861  {
862  WerrorS(nDivBy0);
863  return (number)0L;
864  }
865  else
866  {
867  number inv=nvInversM(b,r);
868  return nvMultM(a,inv,r);
869  }
870 }
871 number nvInvers (number c, const coeffs r)
872 {
873  if ((long)c==0L)
874  {
875  WerrorS(nDivBy0);
876  return (number)0L;
877  }
878  return nvInversM(c,r);
879 }
880 #if 0
881 void nvPower (number a, int i, number * result, const coeffs r)
882 {
883  if (i==0)
884  {
885  //npInit(1,result);
886  *(long *)result = 1;
887  }
888  else if (i==1)
889  {
890  *result = a;
891  }
892  else
893  {
894  nvPower(a,i-1,result,r);
895  *result = nvMultM(a,*result,r);
896  }
897 }
898 #endif
899 #endif
900 
901 void npCoeffWrite (const coeffs r, BOOLEAN /*details*/)
902 {
903  Print("ZZ/%d",r->ch);
904 }
905 
long intval() const
conversion functions
const CanonicalForm int s
Definition: facAbsFact.cc:55
static number npMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: modulop.cc:734
const poly a
Definition: syzextra.cc:212
#define Print
Definition: emacs.cc:83
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:834
static number npMultM(number a, number b, const coeffs r)
Definition: modulop.h:49
number npInit(long i, const coeffs r)
Definition: modulop.cc:103
long npInt(number &n, const coeffs r)
Definition: modulop.cc:117
Definition: int_poly.h:33
loop
Definition: myNF.cc:98
number nlModP(number q, const coeffs, const coeffs Zp)
Definition: longrat.cc:1440
if(0 > strat->sl)
Definition: myNF.cc:73
#define FALSE
Definition: auxiliary.h:94
mpf_t * _mpfp()
Definition: mpr_complex.h:134
return P p
Definition: myNF.cc:203
number nvInvers(number c, const coeffs r)
Definition: modulop.cc:871
static void npWriteFd(number n, FILE *f, const coeffs)
Definition: modulop.cc:457
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:244
bool isImm() const
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:248
static FORCE_INLINE BOOLEAN nCoeff_is_long_R(const coeffs r)
Definition: coeffs.h:908
void npPower(number a, int i, number *result, const coeffs r)
number npInvers(number c, const coeffs r)
Definition: modulop.cc:270
#define npEqualM(A, B, r)
Definition: modulop.h:132
static number npMapP(number from, const coeffs src, const coeffs dst_r)
Definition: modulop.cc:620
static char * npCoeffName(const coeffs cf)
Definition: modulop.cc:445
number nvMult(number a, number b, const coeffs r)
Definition: modulop.cc:795
long nvInvMod(long a, const coeffs R)
Definition: modulop.cc:810
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
{p < 2^31}
Definition: coeffs.h:30
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:750
(), see rinteger.h, new impl.
Definition: coeffs.h:112
number npAdd(number a, number b, const coeffs r)
Definition: modulop.cc:125
void nvInpMult(number &a, number b, const coeffs r)
Definition: modulop.cc:803
void npWrite(number a, const coeffs r)
Definition: modulop.cc:321
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:448
factory&#39;s main class
Definition: canonicalform.h:75
#define TRUE
Definition: auxiliary.h:98
number npDiv(number a, number b, const coeffs r)
Definition: modulop.cc:237
#define FREE_RNUMBER(x)
Definition: coeffs.h:86
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
BOOLEAN npEqual(number a, number b, const coeffs r)
Definition: modulop.cc:311
BOOLEAN npInitChar(coeffs r, void *p)
Definition: modulop.cc:475
#define omAlloc(size)
Definition: omAllocDecl.h:210
BOOLEAN npDBTest(number a, const char *f, const int l, const coeffs r)
Definition: modulop.cc:609
void setCharacteristic(int c)
Definition: cf_char.cc:23
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
static number npNegM(number a, const coeffs r)
Definition: modulop.h:111
number npInversM(number c, const coeffs r)
Definition: modulop.cc:218
static number npSubM(number a, number b, const coeffs r)
Definition: modulop.h:82
static number npRandom(siRandProc p, number, number, const coeffs cf)
Definition: modulop.cc:470
poly res
Definition: myNF.cc:322
BOOLEAN npGreater(number a, number b, const coeffs r)
Definition: modulop.cc:302
number nvDiv(number a, number b, const coeffs r)
Definition: modulop.cc:856
const ring r
Definition: syzextra.cc:208
BOOLEAN npIsMOne(number a, const coeffs r)
Definition: modulop.cc:163
Coefficient rings, fields and other domains suitable for Singular polynomials.
void npCoeffWrite(const coeffs r, BOOLEAN details)
Definition: modulop.cc:901
static FORCE_INLINE BOOLEAN nCoeff_is_CF(const coeffs r)
Definition: coeffs.h:914
int s_readint(s_buff F)
Definition: s_buff.cc:110
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:394
The main handler for Singular numbers which are suitable for Singular polynomials.
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
const ring R
Definition: DebugPrint.cc:36
BOOLEAN npGreaterZero(number k, const coeffs r)
Definition: modulop.cc:72
const int MAX_INT_VAL
Definition: mylimits.h:12
static const char * npEati(const char *s, int *i, const coeffs r)
Definition: modulop.cc:351
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:742
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:77
All the auxiliary stuff.
const char *const nDivBy0
Definition: numbers.h:83
#define StringAppend
Definition: emacs.cc:82
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
nMapFunc npSetMap(const coeffs src, const coeffs dst)
Definition: modulop.cc:748
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
static number npMapLongR(number from, const coeffs, const coeffs dst_r)
Definition: modulop.cc:632
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
int(* siRandProc)()
Definition: sirandom.h:9
number npSub(number a, number b, const coeffs r)
Definition: modulop.cc:137
number npConvFactoryNSingN(const CanonicalForm n, const coeffs r)
Definition: modulop.cc:432
#define NV_MAX_PRIME
Definition: modulop.h:21
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
#define SR_TO_INT(SR)
Definition: longrat.h:70
(number), see longrat.h
Definition: coeffs.h:111
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static char * npCoeffString(const coeffs cf)
Definition: modulop.cc:452
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
#define NULL
Definition: omList.c:10
#define ULONG64
(gmp_float), see
Definition: coeffs.h:117
number npNeg(number c, const coeffs r)
Definition: modulop.cc:285
static number npMapCanonicalForm(number a, const coeffs, const coeffs dst)
Definition: modulop.cc:741
#define SR_INT
Definition: longrat.h:68
static number npMapZ(number from, const coeffs src, const coeffs dst)
Definition: modulop.cc:721
const CanonicalForm & w
Definition: facAbsFact.cc:55
#define ALLOC_RNUMBER()
Definition: coeffs.h:87
number npMult(number a, number b, const coeffs r)
Definition: modulop.cc:88
CanonicalForm npConvSingNFactoryN(number n, BOOLEAN setChar, const coeffs r)
Definition: modulop.cc:425
static number npMapGMP(number from, const coeffs, const coeffs dst)
Definition: modulop.cc:708
static number npReadFd(s_buff f, const coeffs)
Definition: modulop.cc:462
static BOOLEAN npCoeffsEqual(const coeffs r, n_coeffType n, void *parameter)
Definition: modulop.cc:420
number nvInversM(number c, const coeffs r)
Definition: modulop.cc:850
(int), see modulop.h
Definition: coeffs.h:110
#define SR_HDL(A)
Definition: tgb.cc:35
void npKillChar(coeffs r)
Definition: modulop.cc:404
const char * npRead(const char *s, number *a, const coeffs r)
Definition: modulop.cc:370
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:85
const poly b
Definition: syzextra.cc:213
BOOLEAN npIsOne(number a, const coeffs r)
Definition: modulop.cc:156
BOOLEAN npIsZero(number a, const coeffs r)
Definition: modulop.cc:149
#define omAlloc0(size)
Definition: omAllocDecl.h:211
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
static number nvMultM(number a, number b, const coeffs r)
Definition: modulop.cc:54
#define omStrDup(s)
Definition: omAllocDecl.h:263