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