source: git/libpolys/coeffs/longrat.cc @ 0a3fa3

spielwiese
Last change on this file since 0a3fa3 was 0a3fa3, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
bug in nlModP (longrat.cc:1294) ADD: test mapping of -7/5 from Q into F_1000000007 (wrong on 32bit due to an integer overflow in nlModP)
  • Property mode set to 100644
File size: 55.0 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5/*
6* ABSTRACT: computation with long rational numbers (Hubert Grassmann)
7*/
8
9#include "config.h"
10#include <misc/auxiliary.h>
11
12#ifdef HAVE_FACTORY
13#include <factory/factory.h>
14#endif
15
16#include <coeffs/longrat.h>
17
18
19// 64 bit version:
20#if 0
21#define MAX_NUM_SIZE 60
22#define POW_2_28 0x10000000000000L
23#define LONG long
24#else
25#define MAX_NUM_SIZE 28
26#define POW_2_28 (1L<<28)
27#define LONG int
28#endif
29
30static inline number nlShort3(number x) // assume x->s==3
31{
32  assume(x->s==3);
33  if ((mpz_cmp_ui(x->z,(long)0)==0)
34  || (mpz_size1(x->z)<=MP_SMALL))
35  {
36    LONG ui=mpz_get_si(x->z);
37    if ((((ui<<3)>>3)==ui)
38    && (mpz_cmp_si(x->z,(long)ui)==0))
39    {
40      mpz_clear(x->z);
41      FREE_RNUMBER(x);
42      return INT_TO_SR(ui);
43    }
44  }
45  return x;
46}
47
48#ifndef LONGRAT_CC
49#define LONGRAT_CC
50
51#include <string.h>
52#include <float.h>
53
54#include <coeffs/coeffs.h>
55#include <reporter/reporter.h>
56#include <omalloc/omalloc.h>
57
58#include <coeffs/numbers.h>
59#include <coeffs/modulop.h>
60#include <coeffs/shortfl.h>
61#include <coeffs/mpr_complex.h>
62
63#ifndef BYTES_PER_MP_LIMB
64#define BYTES_PER_MP_LIMB sizeof(mp_limb_t)
65#endif
66
67/*-----------------------------------------------------------------*/
68/*3
69* parameter s in number:
70* 0 (or FALSE): not normalised rational
71* 1 (or TRUE):  normalised rational
72* 3          :  integer with n==NULL
73*/
74/*3
75**  'SR_INT' is the type of those integers small enough to fit into  29  bits.
76**  Therefor the value range of this small integers is: $-2^{28}...2^{28}-1$.
77**
78**  Small integers are represented by an immediate integer handle, containing
79**  the value instead of pointing  to  it,  which  has  the  following  form:
80**
81**      +-------+-------+-------+-------+- - - -+-------+-------+-------+
82**      | guard | sign  | bit   | bit   |       | bit   | tag   | tag   |
83**      | bit   | bit   | 27    | 26    |       | 0     | 0     | 1     |
84**      +-------+-------+-------+-------+- - - -+-------+-------+-------+
85**
86**  Immediate integers handles carry the tag 'SR_INT', i.e. the last bit is 1.
87**  This distuingishes immediate integers from other handles which  point  to
88**  structures aligned on 4 byte boundaries and therefor have last bit  zero.
89**  (The second bit is reserved as tag to allow extensions of  this  scheme.)
90**  Using immediates as pointers and dereferencing them gives address errors.
91**
92**  To aid overflow check the most significant two bits must always be equal,
93**  that is to say that the sign bit of immediate integers has a  guard  bit.
94**
95**  The macros 'INT_TO_SR' and 'SR_TO_INT' should be used to convert  between
96**  a small integer value and its representation as immediate integer handle.
97**
98**  Large integers and rationals are represented by z and n
99**  where n may be undefined (if s==3)
100**  NULL represents only deleted values
101*/
102#define SR_HDL(A) ((long)(A))
103/*#define SR_INT    1L*/
104/*#define INT_TO_SR(INT)  ((number) (((long)INT << 2) + SR_INT))*/
105// #define SR_TO_INT(SR)   (((long)SR) >> 2)
106
107#define MP_SMALL 1
108//#define mpz_isNeg(A) (mpz_cmp_si(A,(long)0)<0)
109#define mpz_isNeg(A) ((A)->_mp_size<0)
110#define mpz_limb_size(A) ((A)->_mp_size)
111#define mpz_limb_d(A) ((A)->_mp_d)
112#define MPZ_DIV(A,B,C) mpz_tdiv_q((A),(B),(C))
113#define MPZ_EXACTDIV(A,B,C) mpz_divexact((A),(B),(C))
114
115/// Our Type!
116static const n_coeffType ID = n_Q;
117
118void    _nlDelete_NoImm(number *a);
119
120/***************************************************************
121 *
122 * Routines which are never inlined by p_Numbers.h
123 *
124 *******************************************************************/
125#ifndef P_NUMBERS_H
126
127number nlShort3_noinline(number x) // assume x->s==3
128{
129  return nlShort3(x);
130}
131
132
133number nlOne=INT_TO_SR(1);
134
135#if (__GNU_MP_VERSION*10+__GNU_MP_VERSION_MINOR < 31)
136void mpz_mul_si (mpz_ptr r, mpz_srcptr s, long int si)
137{
138  if (si>=0)
139    mpz_mul_ui(r,s,si);
140  else
141  {
142    mpz_mul_ui(r,s,-si);
143    mpz_neg(r,r);
144  }
145}
146#endif
147
148static number nlMapP(number from, const coeffs src, const coeffs dst)
149{
150  assume( getCoeffType(dst) == ID );
151  assume( getCoeffType(src) == n_Zp );
152
153  number to;
154  to = nlInit(npInt(from,src), dst);
155  return to;
156}
157
158static number nlMapLongR(number from, const coeffs src, const coeffs dst);
159static number nlMapR(number from, const coeffs src, const coeffs dst);
160
161
162#ifdef HAVE_RINGS
163/*2
164* convert from a GMP integer
165*/
166number nlMapGMP(number from, const coeffs /*src*/, const coeffs /*dst*/)
167{
168  number z=ALLOC_RNUMBER();
169#if defined(LDEBUG)
170  z->debug=123456;
171#endif
172  mpz_init_set(z->z,(mpz_ptr) from);
173  //mpz_init_set_ui(&z->n,1);
174  z->s = 3;
175  z=nlShort3(z);
176  return z;
177}
178
179/*2
180* convert from an machine long
181*/
182number nlMapMachineInt(number from, const coeffs /*src*/, const coeffs /*dst*/)
183{
184  number z=ALLOC_RNUMBER();
185#if defined(LDEBUG)
186  z->debug=123456;
187#endif
188  mpz_init_set_ui(z->z,(unsigned long) from);
189  z->s = 3;
190  z=nlShort3(z);
191  return z;
192}
193#endif
194
195
196#ifdef LDEBUG
197BOOLEAN nlDBTest(number a, const char *f,const int l, const coeffs /*r*/)
198{
199  if (a==NULL)
200  {
201    Print("!!longrat: NULL in %s:%d\n",f,l);
202    return FALSE;
203  }
204  //if ((int)a==1) Print("!! 0x1 as number ? %s %d\n",f,l);
205  if ((((long)a)&3L)==3L)
206  {
207    Print(" !!longrat:ptr(3) in %s:%d\n",f,l);
208    return FALSE;
209  }
210  if ((((long)a)&3L)==1L)
211  {
212    if (((((LONG)(long)a)<<1)>>1)!=((LONG)(long)a))
213    {
214      Print(" !!longrat:arith:%lx in %s:%d\n",(long)a, f,l);
215      return FALSE;
216    }
217    return TRUE;
218  }
219  /* TODO: If next line is active, then computations in algebraic field
220           extensions over Q will throw a lot of assume violations although
221           everything is computed correctly and no seg fault appears.
222           Maybe the test is not appropriate in this case. */
223  omCheckIf(omCheckAddrSize(a,sizeof(*a)), return FALSE);
224  if (a->debug!=123456)
225  {
226    Print("!!longrat:debug:%d in %s:%d\n",a->debug,f,l);
227    a->debug=123456;
228    return FALSE;
229  }
230  if ((a->s<0)||(a->s>4))
231  {
232    Print("!!longrat:s=%d in %s:%d\n",a->s,f,l);
233    return FALSE;
234  }
235  /* TODO: If next line is active, then computations in algebraic field
236           extensions over Q will throw a lot of assume violations although
237           everything is computed correctly and no seg fault appears.
238           Maybe the test is not appropriate in this case. */
239  //omCheckAddrSize(a->z[0]._mp_d,a->z[0]._mp_alloc*BYTES_PER_MP_LIMB);
240  if (a->z[0]._mp_alloc==0)
241    Print("!!longrat:z->alloc=0 in %s:%d\n",f,l);
242
243  if (a->s<2)
244  {
245    /* TODO: If next line is active, then computations in algebraic field
246             extensions over Q will throw a lot of assume violations although
247             everything is computed correctly and no seg fault appears.
248             Maybe the test is not appropriate in this case. */
249    //omCheckIf(omCheckAddrSize(a->n[0]._mp_d,a->n[0]._mp_alloc*BYTES_PER_MP_LIMB), return FALSE);
250    if (a->z[0]._mp_alloc==0)
251      Print("!!longrat:n->alloc=0 in %s:%d\n",f,l);
252    if ((mpz_size1(a->n) ==1) && (mpz_cmp_si(a->n,(long)1)==0))
253    {
254      Print("!!longrat:integer as rational in %s:%d\n",f,l);
255      mpz_clear(a->n); a->s=3;
256      return FALSE;
257    }
258    else if (mpz_isNeg(a->n))
259    {
260      Print("!!longrat:div. by negative in %s:%d\n",f,l);
261      mpz_neg(a->z,a->z);
262      mpz_neg(a->n,a->n);
263      return FALSE;
264    }
265    return TRUE;
266  }
267  //if (a->s==2)
268  //{
269  //  Print("!!longrat:s=2 in %s:%d\n",f,l);
270  //  return FALSE;
271  //}
272  if (mpz_size1(a->z)>MP_SMALL) return TRUE;
273  LONG ui=(int)mpz_get_si(a->z);
274  if ((((ui<<3)>>3)==ui)
275  && (mpz_cmp_si(a->z,(long)ui)==0))
276  {
277    Print("!!longrat:im int %d in %s:%d\n",ui,f,l);
278    f=NULL;
279    return FALSE;
280  }
281  return TRUE;
282}
283#endif
284
285#ifdef HAVE_FACTORY
286CanonicalForm nlConvSingNFactoryN( number n, BOOLEAN setChar, const coeffs /*r*/ )
287{
288  if (setChar) setCharacteristic( 0 );
289
290  CanonicalForm term;
291  if ( SR_HDL(n) & SR_INT )
292  {
293    term = SR_TO_INT(n);
294  }
295  else
296  {
297    if ( n->s == 3 )
298    {
299      mpz_t dummy;
300      mpz_init_set( dummy,n->z );
301      term = make_cf( dummy );
302    }
303    else
304    {
305      // assume s==0 or s==1
306      mpz_t num, den;
307      On(SW_RATIONAL);
308      mpz_init_set( num, n->z );
309      mpz_init_set( den, n->n );
310      term = make_cf( num, den, ( n->s != 1 ));
311    }
312  }
313  return term;
314}
315
316number nlConvFactoryNSingN( const CanonicalForm n, const coeffs r)
317{
318  if (n.isImm())
319  {
320    return nlInit(n.intval(),r);
321  }
322  else
323  {
324    number z = ALLOC_RNUMBER(); //Q!? // (number)omAllocBin(rnumber_bin);
325#if defined(LDEBUG)
326    z->debug=123456;
327#endif
328    gmp_numerator( n, z->z );
329    if ( n.den().isOne() )
330      z->s = 3;
331    else
332    {
333      gmp_denominator( n, z->n );
334      z->s = 0;
335    }
336    nlNormalize(z,r);
337    return z;
338  }
339}
340#endif
341number nlRInit (long i);
342
343static number nlMapR(number from, const coeffs src, const coeffs dst)
344{
345  assume( getCoeffType(dst) == ID );
346  assume( getCoeffType(src) == n_R );
347
348  double f=nrFloat(from);
349  if (f==0.0) return INT_TO_SR(0);
350  int f_sign=1;
351  if (f<0.0)
352  {
353    f_sign=-1;
354    f=-f;
355  }
356  int i=0;
357  mpz_t h1;
358  mpz_init_set_ui(h1,1);
359  while((FLT_RADIX*f) < DBL_MAX && i<DBL_MANT_DIG)
360  {
361    f*=FLT_RADIX;
362    mpz_mul_ui(h1,h1,FLT_RADIX);
363    i++;
364  }
365  number re=nlRInit(1);
366  mpz_set_d(re->z,f);
367  memcpy(&(re->n),&h1,sizeof(h1));
368  re->s=0; /* not normalized */
369  if(f_sign==-1) re=nlNeg(re,dst);
370  nlNormalize(re,dst);
371  return re;
372}
373
374static number nlMapLongR(number from, const coeffs src, const coeffs dst)
375{
376  assume( getCoeffType(dst) == ID );
377  assume( getCoeffType(src) == n_long_R );
378
379  gmp_float *ff=(gmp_float*)from;
380  mpf_t *f=ff->_mpfp();
381  number res;
382  mpz_ptr dest,ndest;
383  int size, i,negative;
384  int e,al,bl;
385  mp_ptr qp,dd,nn;
386
387  size = (*f)[0]._mp_size;
388  if (size == 0)
389    return INT_TO_SR(0);
390  if(size<0)
391  {
392    negative = 1;
393    size = -size;
394  }
395  else
396    negative = 0;
397
398  qp = (*f)[0]._mp_d;
399  while(qp[0]==0)
400  {
401    qp++;
402    size--;
403  }
404
405  e=(*f)[0]._mp_exp-size;
406  res = ALLOC_RNUMBER();
407#if defined(LDEBUG)
408  res->debug=123456;
409#endif
410  dest = res->z;
411
412  if (e<0)
413  {
414    al = dest->_mp_size = size;
415    if (al<2) al = 2;
416    dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
417    for (i=0;i<size;i++) dd[i] = qp[i];
418    bl = 1-e;
419    nn = (mp_ptr)omAlloc(sizeof(mp_limb_t)*bl);
420    nn[bl-1] = 1;
421    for (i=bl-2;i>=0;i--) nn[i] = 0;
422    ndest = res->n;
423    ndest->_mp_d = nn;
424    ndest->_mp_alloc = ndest->_mp_size = bl;
425    res->s = 0;
426  }
427  else
428  {
429    al = dest->_mp_size = size+e;
430    if (al<2) al = 2;
431    dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
432    for (i=0;i<size;i++) dd[i+e] = qp[i];
433    for (i=0;i<e;i++) dd[i] = 0;
434    res->s = 3;
435  }
436
437  dest->_mp_d = dd;
438  dest->_mp_alloc = al;
439  if (negative) dest->_mp_size = -dest->_mp_size;
440
441  if (res->s==0)
442    nlNormalize(res,dst);
443  else if (mpz_size1(res->z)<=MP_SMALL)
444  {
445    // res is new, res->ref is 1
446    res=nlShort3(res);
447  }
448  nlTest(res, dst);
449  return res;
450}
451
452//static number nlMapLongR(number from)
453//{
454//  gmp_float *ff=(gmp_float*)from;
455//  const mpf_t *f=ff->mpfp();
456//  int f_size=ABS((*f)[0]._mp_size);
457//  if (f_size==0)
458//    return nlInit(0);
459//  int f_sign=1;
460//  number work=ngcCopy(from);
461//  if (!ngcGreaterZero(work))
462//  {
463//    f_sign=-1;
464//    work=ngcNeg(work);
465//  }
466//  int i=0;
467//  mpz_t h1;
468//  mpz_init_set_ui(h1,1);
469//  while((FLT_RADIX*f) < DBL_MAX && i<DBL_MANT_DIG)
470//  {
471//    f*=FLT_RADIX;
472//    mpz_mul_ui(h1,h1,FLT_RADIX);
473//    i++;
474//  }
475//  number r=nlRInit(1);
476//  mpz_set_d(&(r->z),f);
477//  memcpy(&(r->n),&h1,sizeof(h1));
478//  r->s=0; /* not normalized */
479//  nlNormalize(r);
480//  return r;
481//
482//
483//  number r=nlRInit(1);
484//  int f_shift=f_size+(*f)[0]._mp_exp;
485//  if ( f_shift > 0)
486//  {
487//    r->s=0;
488//    mpz_init(&r->n);
489//    mpz_setbit(&r->n,f_shift*BYTES_PER_MP_LIMB*8);
490//    mpz_setbit(&r->z,f_size*BYTES_PER_MP_LIMB*8-1);
491//    // now r->z has enough space
492//    memcpy(mpz_limb_d(&r->z),((*f)[0]._mp_d),f_size*BYTES_PER_MP_LIMB);
493//    nlNormalize(r);
494//  }
495//  else
496//  {
497//    r->s=3;
498//    if (f_shift==0)
499//    {
500//      mpz_setbit(&r->z,f_size*BYTES_PER_MP_LIMB*8-1);
501//      // now r->z has enough space
502//      memcpy(mpz_limb_d(&r->z),((*f)[0]._mp_d),f_size*BYTES_PER_MP_LIMB);
503//    }
504//    else /* f_shift < 0 */
505//    {
506//      mpz_setbit(&r->z,(f_size-f_shift)*BYTES_PER_MP_LIMB*8-1);
507//      // now r->z has enough space
508//      memcpy(mpz_limb_d(&r->z)-f_shift,((*f)[0]._mp_d),
509//        f_size*BYTES_PER_MP_LIMB);
510//    }
511//  }
512//  if ((*f)[0]._mp_size<0);
513//    r=nlNeg(r);
514//  return r;
515//}
516
517int nlSize(number a, const coeffs)
518{
519  if (a==INT_TO_SR(0))
520     return 0; /* rational 0*/
521  if (SR_HDL(a) & SR_INT)
522     return 1; /* immidiate int */
523  int s=a->z[0]._mp_alloc;
524//  while ((s>0) &&(a->z._mp_d[s]==0L)) s--;
525//#if SIZEOF_LONG == 8
526//  if (a->z._mp_d[s] < (unsigned long)0x100000000L) s=s*2-1;
527//  else s *=2;
528//#endif
529//  s++;
530  if (a->s<2)
531  {
532    int d=a->n[0]._mp_alloc;
533//    while ((d>0) && (a->n._mp_d[d]==0L)) d--;
534//#if SIZEOF_LONG == 8
535//    if (a->n._mp_d[d] < (unsigned long)0x100000000L) d=d*2-1;
536//    else d *=2;
537//#endif
538    s+=d;
539  }
540  return s;
541}
542
543/*2
544* convert number to int
545*/
546int nlInt(number &i, const coeffs r)
547{
548  nlTest(i, r);
549  nlNormalize(i,r);
550  if (SR_HDL(i) &SR_INT) return SR_TO_INT(i);
551  if (i->s==3)
552  {
553    if(mpz_size1(i->z)>MP_SMALL) return 0;
554    int ul=(int)mpz_get_si(i->z);
555    if (mpz_cmp_si(i->z,(long)ul)!=0) return 0;
556    return ul;
557  }
558  mpz_t tmp;
559  int ul;
560  mpz_init(tmp);
561  MPZ_DIV(tmp,i->z,i->n);
562  if(mpz_size1(tmp)>MP_SMALL) ul=0;
563  else
564  {
565    ul=(int)mpz_get_si(tmp);
566    if (mpz_cmp_si(tmp,(long)ul)!=0) ul=0;
567  }
568  mpz_clear(tmp);
569  return ul;
570}
571
572/*2
573* convert number to bigint
574*/
575number nlBigInt(number &i, const coeffs r)
576{
577  nlTest(i, r);
578  nlNormalize(i,r);
579  if (SR_HDL(i) &SR_INT) return (i);
580  if (i->s==3)
581  {
582    return nlCopy(i,r);
583  }
584  number tmp=nlRInit(1);
585  MPZ_DIV(tmp->z,i->z,i->n);
586  tmp=nlShort3(tmp);
587  return tmp;
588}
589
590/*
591* 1/a
592*/
593number nlInvers(number a, const coeffs r)
594{
595  nlTest(a, r);
596  number n;
597  if (SR_HDL(a) & SR_INT)
598  {
599    if ((a==INT_TO_SR(1L)) || (a==INT_TO_SR(-1L)))
600    {
601      return a;
602    }
603    if (nlIsZero(a,r))
604    {
605      WerrorS(nDivBy0);
606      return INT_TO_SR(0);
607    }
608    n=ALLOC_RNUMBER();
609#if defined(LDEBUG)
610    n->debug=123456;
611#endif
612    n->s=1;
613    if ((long)a>0L)
614    {
615      mpz_init_set_si(n->z,(long)1);
616      mpz_init_set_si(n->n,(long)SR_TO_INT(a));
617    }
618    else
619    {
620      mpz_init_set_si(n->z,(long)-1);
621      mpz_init_set_si(n->n,(long)-SR_TO_INT(a));
622    }
623    nlTest(n, r);
624    return n;
625  }
626  n=ALLOC_RNUMBER();
627#if defined(LDEBUG)
628  n->debug=123456;
629#endif
630  {
631    n->s=a->s;
632    mpz_init_set(n->n,a->z);
633    switch (a->s)
634    {
635      case 0:
636      case 1:
637              mpz_init_set(n->z,a->n);
638              if (mpz_isNeg(n->n)) /* && n->s<2*/
639              {
640                mpz_neg(n->z,n->z);
641                mpz_neg(n->n,n->n);
642              }
643              if (mpz_cmp_si(n->n,(long)1)==0)
644              {
645                mpz_clear(n->n);
646                n->s=3;
647                n=nlShort3(n);
648              }
649              break;
650      case 3:
651              n->s=1;
652              if (mpz_isNeg(n->n)) /* && n->s<2*/
653              {
654                mpz_neg(n->n,n->n);
655                mpz_init_set_si(n->z,(long)-1);
656              }
657              else
658              {
659                mpz_init_set_si(n->z,(long)1);
660              }
661              break;
662    }
663  }
664  nlTest(n, r);
665  return n;
666}
667
668
669/*2
670* u := a / b in Z, if b | a (else undefined)
671*/
672number   nlExactDiv(number a, number b, const coeffs r)
673{
674  if (b==INT_TO_SR(0))
675  {
676    WerrorS(nDivBy0);
677    return INT_TO_SR(0);
678  }
679  if (a==INT_TO_SR(0))
680    return INT_TO_SR(0);
681  number u;
682  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
683  {
684    /* the small int -(1<<28) divided by -1 is the large int (1<<28)   */
685    if ((a==INT_TO_SR(-(POW_2_28)))&&(b==INT_TO_SR(-1L)))
686    {
687      return nlRInit(POW_2_28);
688    }
689    long aa=SR_TO_INT(a);
690    long bb=SR_TO_INT(b);
691    return INT_TO_SR(aa/bb);
692  }
693  number bb=NULL;
694  if (SR_HDL(b) & SR_INT)
695  {
696    bb=nlRInit(SR_TO_INT(b));
697    b=bb;
698  }
699  u=ALLOC_RNUMBER();
700#if defined(LDEBUG)
701  u->debug=123456;
702#endif
703  mpz_init(u->z);
704  /* u=a/b */
705  u->s = 3;
706  MPZ_EXACTDIV(u->z,a->z,b->z);
707  if (bb!=NULL)
708  {
709    mpz_clear(bb->z);
710#if defined(LDEBUG)
711    bb->debug=654324;
712#endif
713    FREE_RNUMBER(bb); // omFreeBin((void *)bb, rnumber_bin);
714  }
715  u=nlShort3(u);
716  nlTest(u, r);
717  return u;
718}
719
720/*2
721* u := a / b in Z
722*/
723number nlIntDiv (number a, number b, const coeffs r)
724{
725  if (b==INT_TO_SR(0))
726  {
727    WerrorS(nDivBy0);
728    return INT_TO_SR(0);
729  }
730  if (a==INT_TO_SR(0))
731    return INT_TO_SR(0);
732  number u;
733  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
734  {
735    /* the small int -(1<<28) divided by -1 is the large int (1<<28)   */
736    if ((a==INT_TO_SR(-(POW_2_28)))&&(b==INT_TO_SR(-1L)))
737    {
738      return nlRInit(POW_2_28);
739    }
740    long aa=SR_TO_INT(a);
741    long bb=SR_TO_INT(b);
742    return INT_TO_SR(aa/bb);
743  }
744  if (SR_HDL(a) & SR_INT)
745  {
746    /* the small int -(1<<28) divided by 2^28 is 1   */
747    if (a==INT_TO_SR(-(POW_2_28)))
748    {
749      if(mpz_cmp_si(b->z,(POW_2_28))==0)
750      {
751        return INT_TO_SR(-1);
752      }
753    }
754    /* a is a small and b is a large int: -> 0 */
755    return INT_TO_SR(0);
756  }
757  number bb=NULL;
758  if (SR_HDL(b) & SR_INT)
759  {
760    bb=nlRInit(SR_TO_INT(b));
761    b=bb;
762  }
763  u=ALLOC_RNUMBER();
764#if defined(LDEBUG)
765  u->debug=123456;
766#endif
767  assume(a->s==3);
768  assume(b->s==3);
769  mpz_init_set(u->z,a->z);
770  /* u=u/b */
771  u->s = 3;
772  MPZ_DIV(u->z,u->z,b->z);
773  if (bb!=NULL)
774  {
775    mpz_clear(bb->z);
776#if defined(LDEBUG)
777    bb->debug=654324;
778#endif
779    FREE_RNUMBER(bb); // omFreeBin((void *)bb, rnumber_bin);
780  }
781  u=nlShort3(u);
782  nlTest(u, r);
783  return u;
784}
785
786/*2
787* u := a mod b in Z, u>=0
788*/
789number nlIntMod (number a, number b, const coeffs r)
790{
791  if (b==INT_TO_SR(0))
792  {
793    WerrorS(nDivBy0);
794    return INT_TO_SR(0);
795  }
796  if (a==INT_TO_SR(0))
797    return INT_TO_SR(0);
798  number u;
799  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
800  {
801    if ((long)a>0L)
802    {
803      if ((long)b>0L)
804        return INT_TO_SR(SR_TO_INT(a)%SR_TO_INT(b));
805      else
806        return INT_TO_SR(SR_TO_INT(a)%(-SR_TO_INT(b)));
807    }
808    else
809    {
810      if ((long)b>0L)
811      {
812        long i=(-SR_TO_INT(a))%SR_TO_INT(b);
813        if ( i != 0L ) i = (SR_TO_INT(b))-i;
814        return INT_TO_SR(i);
815      }
816      else
817      {
818        long i=(-SR_TO_INT(a))%(-SR_TO_INT(b));
819        if ( i != 0L ) i = (-SR_TO_INT(b))-i;
820        return INT_TO_SR(i);
821      }
822    }
823  }
824  if (SR_HDL(a) & SR_INT)
825  {
826    /* a is a small and b is a large int: -> a or (a+b) or (a-b) */
827    if ((long)a<0L)
828    {
829      if (mpz_isNeg(b->z))
830        return nlSub(a,b,r);
831      /*else*/
832        return nlAdd(a,b,r);
833    }
834    /*else*/
835      return a;
836  }
837  number bb=NULL;
838  if (SR_HDL(b) & SR_INT)
839  {
840    bb=nlRInit(SR_TO_INT(b));
841    b=bb;
842  }
843  u=ALLOC_RNUMBER();
844#if defined(LDEBUG)
845  u->debug=123456;
846#endif
847  mpz_init(u->z);
848  u->s = 3;
849  mpz_mod(u->z,a->z,b->z);
850  if (bb!=NULL)
851  {
852    mpz_clear(bb->z);
853#if defined(LDEBUG)
854    bb->debug=654324;
855#endif
856    FREE_RNUMBER(bb); // omFreeBin((void *)bb, rnumber_bin);
857  }
858  if (mpz_isNeg(u->z))
859  {
860    if (mpz_isNeg(b->z))
861      mpz_sub(u->z,u->z,b->z);
862    else
863      mpz_add(u->z,u->z,b->z);
864  }
865  u=nlShort3(u);
866  nlTest(u, r);
867  return u;
868}
869
870/*2
871* u := a / b
872*/
873number nlDiv (number a, number b, const coeffs r)
874{
875  number u;
876  if (nlIsZero(b,r))
877  {
878    WerrorS(nDivBy0);
879    return INT_TO_SR(0);
880  }
881  u=ALLOC_RNUMBER();
882  u->s=0;
883#if defined(LDEBUG)
884  u->debug=123456;
885#endif
886// ---------- short / short ------------------------------------
887  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
888  {
889    long i=SR_TO_INT(a);
890    long j=SR_TO_INT(b);
891    if ((i==-POW_2_28) && (j== -1L))
892    { 
893      FREE_RNUMBER(u);
894      return nlRInit(POW_2_28);
895    }
896    long r=i%j;
897    if (r==0)
898    {
899      FREE_RNUMBER(u); // omFreeBin((void *)u, rnumber_bin);
900      return INT_TO_SR(i/j);
901    }
902    mpz_init_set_si(u->z,(long)i);
903    mpz_init_set_si(u->n,(long)j);
904  }
905  else
906  {
907    mpz_init(u->z);
908// ---------- short / long ------------------------------------
909    if (SR_HDL(a) & SR_INT)
910    {
911      // short a / (z/n) -> (a*n)/z
912      if (b->s<2)
913      {
914        mpz_mul_si(u->z,b->n,SR_TO_INT(a));
915      }
916      else
917      // short a / long z -> a/z
918      {
919        mpz_set_si(u->z,SR_TO_INT(a));
920      }
921      if (mpz_cmp(u->z,b->z)==0)
922      {
923        mpz_clear(u->z);
924        FREE_RNUMBER(u);
925        return INT_TO_SR(1);
926      }
927      mpz_init_set(u->n,b->z);
928    }
929// ---------- long / short ------------------------------------
930    else if (SR_HDL(b) & SR_INT)
931    {
932      mpz_set(u->z,a->z);
933      // (z/n) / b -> z/(n*b)
934      if (a->s<2)
935      {
936        mpz_init_set(u->n,a->n);
937        if ((long)b>0L)
938          mpz_mul_ui(u->n,u->n,SR_TO_INT(b));
939        else
940        {
941          mpz_mul_ui(u->n,u->n,-SR_TO_INT(b));
942          mpz_neg(u->z,u->z);
943        }
944      }
945      else
946      // long z / short b -> z/b
947      {
948        //mpz_set(u->z,a->z);
949        mpz_init_set_si(u->n,SR_TO_INT(b));
950      }
951    }
952// ---------- long / long ------------------------------------
953    else
954    {
955      mpz_set(u->z,a->z);
956      mpz_init_set(u->n,b->z);
957      if (a->s<2) mpz_mul(u->n,u->n,a->n);
958      if (b->s<2) mpz_mul(u->z,u->z,b->n);
959    }
960  }
961  if (mpz_isNeg(u->n))
962  {
963    mpz_neg(u->z,u->z);
964    mpz_neg(u->n,u->n);
965  }
966  if (mpz_cmp_si(u->n,(long)1)==0)
967  {
968    mpz_clear(u->n);
969    u->s=3;
970    u=nlShort3(u);
971  }
972  nlTest(u, r);
973  return u;
974}
975
976/*2
977* u:= x ^ exp
978*/
979void nlPower (number x,int exp,number * u, const coeffs r)
980{
981  *u = INT_TO_SR(0); // 0^e, e!=0
982  if (!nlIsZero(x,r))
983  {
984    nlTest(x, r);
985    number aa=NULL;
986    if (SR_HDL(x) & SR_INT)
987    {
988      aa=nlRInit(SR_TO_INT(x));
989      x=aa;
990    }
991    else if (x->s==0)
992      nlNormalize(x,r);
993    *u=ALLOC_RNUMBER();
994#if defined(LDEBUG)
995    (*u)->debug=123456;
996#endif
997    mpz_init((*u)->z);
998    mpz_pow_ui((*u)->z,x->z,(unsigned long)exp);
999    if (x->s<2)
1000    {
1001      if (mpz_cmp_si(x->n,(long)1)==0)
1002      {
1003        x->s=3;
1004        mpz_clear(x->n);
1005      }
1006      else
1007      {
1008        mpz_init((*u)->n);
1009        mpz_pow_ui((*u)->n,x->n,(unsigned long)exp);
1010      }
1011    }
1012    (*u)->s = x->s;
1013    if ((*u)->s==3) *u=nlShort3(*u);
1014    if (aa!=NULL)
1015    {
1016      mpz_clear(aa->z);
1017      FREE_RNUMBER(aa);
1018    }
1019  }
1020  else if (exp==0)
1021    *u = INT_TO_SR(1); // 0^0
1022#ifdef LDEBUG
1023  if (exp<0) Print("nlPower: neg. exp. %d\n",exp);
1024  nlTest(*u, r);
1025#endif
1026}
1027
1028
1029/*2
1030* za >= 0 ?
1031*/
1032BOOLEAN nlGreaterZero (number a, const coeffs r)
1033{
1034  nlTest(a, r);
1035  if (SR_HDL(a) & SR_INT) return SR_HDL(a)>1L /* represents number(0) */;
1036  return (!mpz_isNeg(a->z));
1037}
1038
1039/*2
1040* a > b ?
1041*/
1042BOOLEAN nlGreater (number a, number b, const coeffs r)
1043{
1044  nlTest(a, r);
1045  nlTest(b, r);
1046  number re;
1047  BOOLEAN rr;
1048  re=nlSub(a,b,r);
1049  rr=(!nlIsZero(re,r)) && (nlGreaterZero(re,r));
1050  nlDelete(&re,r);
1051  return rr;
1052}
1053
1054/*2
1055* a == -1 ?
1056*/
1057BOOLEAN nlIsMOne (number a, const coeffs r)
1058{
1059#ifdef LDEBUG
1060  if (a==NULL) return FALSE;
1061  nlTest(a, r);
1062#endif
1063  //if (SR_HDL(a) & SR_INT) return (a==INT_TO_SR(-1L));
1064  //return FALSE;
1065  return  (a==INT_TO_SR(-1L));
1066}
1067
1068/*2
1069* result =gcd(a,b)
1070*/
1071number nlGcd(number a, number b, const coeffs r)
1072{
1073  number result;
1074  nlTest(a, r);
1075  nlTest(b, r);
1076  //nlNormalize(a);
1077  //nlNormalize(b);
1078  if ((a==INT_TO_SR(1L))||(a==INT_TO_SR(-1L))
1079  ||  (b==INT_TO_SR(1L))||(b==INT_TO_SR(-1L)))
1080    return INT_TO_SR(1L);
1081  if (a==INT_TO_SR(0)) /* gcd(0,b) ->b */
1082    return nlCopy(b,r);
1083  if (b==INT_TO_SR(0)) /* gcd(a,0) -> a */
1084    return nlCopy(a,r);
1085  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
1086  {
1087    long i=SR_TO_INT(a);
1088    long j=SR_TO_INT(b);
1089    if((i==0L)||(j==0L))
1090      return INT_TO_SR(1);
1091    long l;
1092    i=ABS(i);
1093    j=ABS(j);
1094    do
1095    {
1096      l=i%j;
1097      i=j;
1098      j=l;
1099    } while (l!=0L);
1100    if (i==POW_2_28)
1101      result=nlRInit(POW_2_28);
1102    else
1103     result=INT_TO_SR(i);
1104    nlTest(result,r);
1105    return result;
1106  }
1107  if (((!(SR_HDL(a) & SR_INT))&&(a->s<2))
1108  ||  ((!(SR_HDL(b) & SR_INT))&&(b->s<2))) return INT_TO_SR(1);
1109  if (SR_HDL(a) & SR_INT)
1110  {
1111    LONG aa=ABS(SR_TO_INT(a));
1112    unsigned long t=mpz_gcd_ui(NULL,b->z,(long)aa);
1113    if (t==POW_2_28)
1114      result=nlRInit(POW_2_28);
1115    else
1116     result=INT_TO_SR(t);
1117  }
1118  else
1119  if (SR_HDL(b) & SR_INT)
1120  {
1121    LONG bb=ABS(SR_TO_INT(b));
1122    unsigned long t=mpz_gcd_ui(NULL,a->z,(long)bb);
1123    if (t==POW_2_28)
1124      result=nlRInit(POW_2_28);
1125    else
1126     result=INT_TO_SR(t);
1127  }
1128  else
1129  {
1130    result=ALLOC_RNUMBER();
1131    mpz_init(result->z);
1132    mpz_gcd(result->z,a->z,b->z);
1133    result->s = 3;
1134  #ifdef LDEBUG
1135    result->debug=123456;
1136  #endif
1137    result=nlShort3(result);
1138  }
1139  nlTest(result, r);
1140  return result;
1141}
1142
1143number nlShort1(number x) // assume x->s==0/1
1144{
1145  assume(x->s<2);
1146  if (mpz_cmp_ui(x->z,(long)0)==0)
1147  {
1148    _nlDelete_NoImm(&x);
1149    return INT_TO_SR(0);
1150  }
1151  if (x->s<2)
1152  {
1153    if (mpz_cmp(x->z,x->n)==0)
1154    {
1155      _nlDelete_NoImm(&x);
1156      return INT_TO_SR(1);
1157    }
1158  }
1159  return x;
1160}
1161/*2
1162* simplify x
1163*/
1164void nlNormalize (number &x, const coeffs r)
1165{
1166  if ((SR_HDL(x) & SR_INT) ||(x==NULL))
1167    return;
1168  if (x->s==3)
1169  {
1170    x=nlShort3_noinline(x);
1171    nlTest(x,r);
1172    return;
1173  }
1174  else if (x->s==0)
1175  {
1176    if (mpz_cmp_si(x->n,(long)1)==0)
1177    {
1178      mpz_clear(x->n);
1179      x->s=3;
1180      x=nlShort3(x);
1181    }
1182    else
1183    {
1184      mpz_t gcd;
1185      mpz_init(gcd);
1186      mpz_gcd(gcd,x->z,x->n);
1187      x->s=1;
1188      if (mpz_cmp_si(gcd,(long)1)!=0)
1189      {
1190        mpz_t r;
1191        mpz_init(r);
1192        MPZ_EXACTDIV(r,x->z,gcd);
1193        mpz_set(x->z,r);
1194        MPZ_EXACTDIV(r,x->n,gcd);
1195        mpz_set(x->n,r);
1196        mpz_clear(r);
1197        if (mpz_cmp_si(x->n,(long)1)==0)
1198        {
1199          mpz_clear(x->n);
1200          x->s=3;
1201          x=nlShort3_noinline(x);
1202        }
1203      }
1204      mpz_clear(gcd);
1205    }
1206  }
1207  nlTest(x, r);
1208}
1209
1210/*2
1211* returns in result->z the lcm(a->z,b->n)
1212*/
1213number nlLcm(number a, number b, const coeffs r)
1214{
1215  number result;
1216  nlTest(a, r);
1217  nlTest(b, r);
1218  if ((SR_HDL(b) & SR_INT)
1219  || (b->s==3))
1220  {
1221    // b is 1/(b->n) => b->n is 1 => result is a
1222    return nlCopy(a,r);
1223  }
1224  result=ALLOC_RNUMBER();
1225#if defined(LDEBUG)
1226  result->debug=123456;
1227#endif
1228  result->s=3;
1229  mpz_t gcd;
1230  mpz_init(gcd);
1231  mpz_init(result->z);
1232  if (SR_HDL(a) & SR_INT)
1233    mpz_gcd_ui(gcd,b->n,ABS(SR_TO_INT(a)));
1234  else
1235    mpz_gcd(gcd,a->z,b->n);
1236  if (mpz_cmp_si(gcd,(long)1)!=0)
1237  {
1238    mpz_t bt;
1239    mpz_init_set(bt,b->n);
1240    MPZ_EXACTDIV(bt,bt,gcd);
1241    if (SR_HDL(a) & SR_INT)
1242      mpz_mul_si(result->z,bt,SR_TO_INT(a));
1243    else
1244      mpz_mul(result->z,bt,a->z);
1245    mpz_clear(bt);
1246  }
1247  else
1248    if (SR_HDL(a) & SR_INT)
1249      mpz_mul_si(result->z,b->n,SR_TO_INT(a));
1250    else
1251      mpz_mul(result->z,b->n,a->z);
1252  mpz_clear(gcd);
1253  result=nlShort3(result);
1254  nlTest(result, r);
1255  return result;
1256}
1257
1258int nlModP(number n, int p, const coeffs r)
1259{
1260  if (SR_HDL(n) & SR_INT)
1261  {
1262    long i=SR_TO_INT(n);
1263    if (i<0L) return (((long)p)-((-i)%((long)p)));
1264    return i%((long)p);
1265  }
1266  int iz=(int)mpz_fdiv_ui(n->z,(unsigned long)p);
1267  if (n->s!=3)
1268  {
1269    int in=mpz_fdiv_ui(n->n,(unsigned long)p);
1270    long  s;
1271
1272    long  u, v, u0, v0, u1, v1, u2, v2, q, r;
1273
1274     u1=1; v1=0;
1275     u2=0; v2=1;
1276     u = in; v = p;
1277
1278     while (v != 0)
1279     {
1280        q = u / v;
1281        r = u % v;
1282        u = v;
1283        v = r;
1284        u0 = u2;
1285        v0 = v2;
1286        u2 =  u1 - q*u2;
1287        v2 = v1- q*v2;
1288        u1 = u0;
1289        v1 = v0;
1290     }
1291
1292     s = u1;
1293     if (s < 0) s+=p;
1294     u=(s*((long)iz)) % ((long)p); // BUG: integer overflow!!!
1295     return (int)u;
1296  }
1297  return iz;
1298}
1299
1300#ifdef HAVE_RINGS
1301/*2
1302* convert number i (from Q) to GMP and warn if denom != 1
1303*/
1304void nlGMP(number &i, number n, const coeffs r)
1305{
1306  // Hier brauche ich einfach die GMP Zahl
1307  nlTest(i, r);
1308  nlNormalize(i, r);
1309  if (SR_HDL(i) & SR_INT)
1310  {
1311    mpz_set_si((mpz_ptr) n, SR_TO_INT(i));
1312    return;
1313  }
1314  if (i->s!=3)
1315  {
1316     WarnS("Omitted denominator during coefficient mapping !");
1317  }
1318  mpz_set((mpz_ptr) n, i->z);
1319}
1320#endif
1321
1322/*2
1323* acces to denominator, other 1 for integers
1324*/
1325number   nlGetDenom(number &n, const coeffs r)
1326{
1327  if (!(SR_HDL(n) & SR_INT))
1328  {
1329    if (n->s==0)
1330    {
1331      nlNormalize(n,r);
1332    }
1333    if (!(SR_HDL(n) & SR_INT))
1334    {
1335      if (n->s!=3)
1336      {
1337        number u=ALLOC_RNUMBER();
1338        u->s=3;
1339#if defined(LDEBUG)
1340        u->debug=123456;
1341#endif
1342        mpz_init_set(u->z,n->n);
1343        u=nlShort3_noinline(u);
1344        return u;
1345      }
1346    }
1347  }
1348  return INT_TO_SR(1);
1349}
1350
1351/*2
1352* acces to Nominator, nlCopy(n) for integers
1353*/
1354number   nlGetNumerator(number &n, const coeffs r)
1355{
1356  if (!(SR_HDL(n) & SR_INT))
1357  {
1358    if (n->s==0)
1359    {
1360      nlNormalize(n,r);
1361    }
1362    if (!(SR_HDL(n) & SR_INT))
1363    {
1364      number u=ALLOC_RNUMBER();
1365#if defined(LDEBUG)
1366      u->debug=123456;
1367#endif
1368      u->s=3;
1369      mpz_init_set(u->z,n->z);
1370      if (n->s!=3)
1371      {
1372        u=nlShort3_noinline(u);
1373      }
1374      return u;
1375    }
1376  }
1377  return n; // imm. int
1378}
1379
1380/***************************************************************
1381 *
1382 * routines which are needed by Inline(d) routines
1383 *
1384 *******************************************************************/
1385BOOLEAN _nlEqual_aNoImm_OR_bNoImm(number a, number b)
1386{
1387  assume(! (SR_HDL(a) & SR_HDL(b) & SR_INT));
1388//  long - short
1389  BOOLEAN bo;
1390  if (SR_HDL(b) & SR_INT)
1391  {
1392    if (a->s!=0) return FALSE;
1393    number n=b; b=a; a=n;
1394  }
1395//  short - long
1396  if (SR_HDL(a) & SR_INT)
1397  {
1398    if (b->s!=0)
1399      return FALSE;
1400    if (((long)a > 0L) && (mpz_isNeg(b->z)))
1401      return FALSE;
1402    if (((long)a < 0L) && (!mpz_isNeg(b->z)))
1403      return FALSE;
1404    mpz_t  bb;
1405    mpz_init_set(bb,b->n);
1406    mpz_mul_si(bb,bb,(long)SR_TO_INT(a));
1407    bo=(mpz_cmp(bb,b->z)==0);
1408    mpz_clear(bb);
1409    return bo;
1410  }
1411// long - long
1412  if (((a->s==1) && (b->s==3))
1413  ||  ((b->s==1) && (a->s==3)))
1414    return FALSE;
1415  if (mpz_isNeg(a->z)&&(!mpz_isNeg(b->z)))
1416    return FALSE;
1417  if (mpz_isNeg(b->z)&&(!mpz_isNeg(a->z)))
1418    return FALSE;
1419  mpz_t  aa;
1420  mpz_t  bb;
1421  mpz_init_set(aa,a->z);
1422  mpz_init_set(bb,b->z);
1423  if (a->s<2) mpz_mul(bb,bb,a->n);
1424  if (b->s<2) mpz_mul(aa,aa,b->n);
1425  bo=(mpz_cmp(aa,bb)==0);
1426  mpz_clear(aa);
1427  mpz_clear(bb);
1428  return bo;
1429}
1430
1431// copy not immediate number a
1432number _nlCopy_NoImm(number a)
1433{
1434  assume(!((SR_HDL(a) & SR_INT)||(a==NULL)));
1435  //nlTest(a, r);
1436  number b=ALLOC_RNUMBER();
1437#if defined(LDEBUG)
1438  b->debug=123456;
1439#endif
1440  switch (a->s)
1441  {
1442    case 0:
1443    case 1:
1444            mpz_init_set(b->n,a->n);
1445    case 3:
1446            mpz_init_set(b->z,a->z);
1447            break;
1448  }
1449  b->s = a->s;
1450  return b;
1451}
1452
1453void _nlDelete_NoImm(number *a)
1454{
1455  {
1456    switch ((*a)->s)
1457    {
1458      case 0:
1459      case 1:
1460        mpz_clear((*a)->n);
1461      case 3:
1462        mpz_clear((*a)->z);
1463#ifdef LDEBUG
1464        (*a)->s=2;
1465#endif
1466    }
1467    FREE_RNUMBER(*a); // omFreeBin((void *) *a, rnumber_bin);
1468  }
1469}
1470
1471number _nlNeg_NoImm(number a)
1472{
1473  {
1474    mpz_neg(a->z,a->z);
1475    if (a->s==3)
1476    {
1477      a=nlShort3(a);
1478    }
1479  }
1480  return a;
1481}
1482
1483number _nlAdd_aNoImm_OR_bNoImm(number a, number b)
1484{
1485  number u=ALLOC_RNUMBER();
1486#if defined(LDEBUG)
1487  u->debug=123456;
1488#endif
1489  mpz_init(u->z);
1490  if (SR_HDL(b) & SR_INT)
1491  {
1492    number x=a;
1493    a=b;
1494    b=x;
1495  }
1496  if (SR_HDL(a) & SR_INT)
1497  {
1498    switch (b->s)
1499    {
1500      case 0:
1501      case 1:/* a:short, b:1 */
1502      {
1503        mpz_t x;
1504        mpz_init(x);
1505        mpz_mul_si(x,b->n,SR_TO_INT(a));
1506        mpz_add(u->z,b->z,x);
1507        mpz_clear(x);
1508        if (mpz_cmp_ui(u->z,(long)0)==0)
1509        {
1510          mpz_clear(u->z);
1511          FREE_RNUMBER(u);
1512          return INT_TO_SR(0);
1513        }
1514        if (mpz_cmp(u->z,b->n)==0)
1515        {
1516          mpz_clear(u->z);
1517          FREE_RNUMBER(u);
1518          return INT_TO_SR(1);
1519        }
1520        mpz_init_set(u->n,b->n);
1521        u->s = 0;
1522        break;
1523      }
1524      case 3:
1525      {
1526        if ((long)a>0L)
1527          mpz_add_ui(u->z,b->z,SR_TO_INT(a));
1528        else
1529          mpz_sub_ui(u->z,b->z,-SR_TO_INT(a));
1530        if (mpz_cmp_ui(u->z,(long)0)==0)
1531        {
1532          mpz_clear(u->z);
1533          FREE_RNUMBER(u);
1534          return INT_TO_SR(0);
1535        }
1536        u->s = 3;
1537        u=nlShort3(u);
1538        break;
1539      }
1540    }
1541  }
1542  else
1543  {
1544    switch (a->s)
1545    {
1546      case 0:
1547      case 1:
1548      {
1549        switch(b->s)
1550        {
1551          case 0:
1552          case 1:
1553          {
1554            mpz_t x;
1555            mpz_init(x);
1556
1557            mpz_mul(x,b->z,a->n);
1558            mpz_mul(u->z,a->z,b->n);
1559            mpz_add(u->z,u->z,x);
1560            mpz_clear(x);
1561
1562            if (mpz_cmp_ui(u->z,(long)0)==0)
1563            {
1564              mpz_clear(u->z);
1565              FREE_RNUMBER(u);
1566              return INT_TO_SR(0);
1567            }
1568            mpz_init(u->n);
1569            mpz_mul(u->n,a->n,b->n);
1570            if (mpz_cmp(u->z,u->n)==0)
1571            {
1572               mpz_clear(u->z);
1573               mpz_clear(u->n);
1574               FREE_RNUMBER(u);
1575               return INT_TO_SR(1);
1576            }
1577            u->s = 0;
1578            break;
1579          }
1580          case 3: /* a:1 b:3 */
1581          {
1582            mpz_mul(u->z,b->z,a->n);
1583            mpz_add(u->z,u->z,a->z);
1584            if (mpz_cmp_ui(u->z,(long)0)==0)
1585            {
1586              mpz_clear(u->z);
1587              FREE_RNUMBER(u);
1588              return INT_TO_SR(0);
1589            }
1590            if (mpz_cmp(u->z,a->n)==0)
1591            {
1592              mpz_clear(u->z);
1593              FREE_RNUMBER(u);
1594              return INT_TO_SR(1);
1595            }
1596            mpz_init_set(u->n,a->n);
1597            u->s = 0;
1598            break;
1599          }
1600        } /*switch (b->s) */
1601        break;
1602      }
1603      case 3:
1604      {
1605        switch(b->s)
1606        {
1607          case 0:
1608          case 1:/* a:3, b:1 */
1609          {
1610            mpz_mul(u->z,a->z,b->n);
1611            mpz_add(u->z,u->z,b->z);
1612            if (mpz_cmp_ui(u->z,(long)0)==0)
1613            {
1614              mpz_clear(u->z);
1615              FREE_RNUMBER(u);
1616              return INT_TO_SR(0);
1617            }
1618            if (mpz_cmp(u->z,b->n)==0)
1619            {
1620              mpz_clear(u->z);
1621              FREE_RNUMBER(u);
1622              return INT_TO_SR(1);
1623            }
1624            mpz_init_set(u->n,b->n);
1625            u->s = 0;
1626            break;
1627          }
1628          case 3:
1629          {
1630            mpz_add(u->z,a->z,b->z);
1631            if (mpz_cmp_ui(u->z,(long)0)==0)
1632            {
1633              mpz_clear(u->z);
1634              FREE_RNUMBER(u);
1635              return INT_TO_SR(0);
1636            }
1637            u->s = 3;
1638            u=nlShort3(u);
1639            break;
1640          }
1641        }
1642        break;
1643      }
1644    }
1645  }
1646  return u;
1647}
1648
1649number _nlSub_aNoImm_OR_bNoImm(number a, number b)
1650{
1651  number u=ALLOC_RNUMBER();
1652#if defined(LDEBUG)
1653  u->debug=123456;
1654#endif
1655  mpz_init(u->z);
1656  if (SR_HDL(a) & SR_INT)
1657  {
1658    switch (b->s)
1659    {
1660      case 0:
1661      case 1:/* a:short, b:1 */
1662      {
1663        mpz_t x;
1664        mpz_init(x);
1665        mpz_mul_si(x,b->n,SR_TO_INT(a));
1666        mpz_sub(u->z,x,b->z);
1667        mpz_clear(x);
1668        if (mpz_cmp_ui(u->z,(long)0)==0)
1669        {
1670          mpz_clear(u->z);
1671          FREE_RNUMBER(u);
1672          return INT_TO_SR(0);
1673        }
1674        if (mpz_cmp(u->z,b->n)==0)
1675        {
1676          mpz_clear(u->z);
1677          FREE_RNUMBER(u);
1678          return INT_TO_SR(1);
1679        }
1680        mpz_init_set(u->n,b->n);
1681        u->s = 0;
1682        break;
1683      }
1684      case 3:
1685      {
1686        if ((long)a>0L)
1687        {
1688          mpz_sub_ui(u->z,b->z,SR_TO_INT(a));
1689          mpz_neg(u->z,u->z);
1690        }
1691        else
1692        {
1693          mpz_add_ui(u->z,b->z,-SR_TO_INT(a));
1694          mpz_neg(u->z,u->z);
1695        }
1696        if (mpz_cmp_ui(u->z,(long)0)==0)
1697        {
1698          mpz_clear(u->z);
1699          FREE_RNUMBER(u);
1700          return INT_TO_SR(0);
1701        }
1702        u->s = 3;
1703        u=nlShort3(u);
1704        break;
1705      }
1706    }
1707  }
1708  else if (SR_HDL(b) & SR_INT)
1709  {
1710    switch (a->s)
1711    {
1712      case 0:
1713      case 1:/* b:short, a:1 */
1714      {
1715        mpz_t x;
1716        mpz_init(x);
1717        mpz_mul_si(x,a->n,SR_TO_INT(b));
1718        mpz_sub(u->z,a->z,x);
1719        mpz_clear(x);
1720        if (mpz_cmp_ui(u->z,(long)0)==0)
1721        {
1722          mpz_clear(u->z);
1723          FREE_RNUMBER(u);
1724          return INT_TO_SR(0);
1725        }
1726        if (mpz_cmp(u->z,a->n)==0)
1727        {
1728          mpz_clear(u->z);
1729          FREE_RNUMBER(u);
1730          return INT_TO_SR(1);
1731        }
1732        mpz_init_set(u->n,a->n);
1733        u->s = 0;
1734        break;
1735      }
1736      case 3:
1737      {
1738        if ((long)b>0L)
1739        {
1740          mpz_sub_ui(u->z,a->z,SR_TO_INT(b));
1741        }
1742        else
1743        {
1744          mpz_add_ui(u->z,a->z,-SR_TO_INT(b));
1745        }
1746        if (mpz_cmp_ui(u->z,(long)0)==0)
1747        {
1748          mpz_clear(u->z);
1749          FREE_RNUMBER(u);
1750          return INT_TO_SR(0);
1751        }
1752        u->s = 3;
1753        u=nlShort3(u);
1754        break;
1755      }
1756    }
1757  }
1758  else
1759  {
1760    switch (a->s)
1761    {
1762      case 0:
1763      case 1:
1764      {
1765        switch(b->s)
1766        {
1767          case 0:
1768          case 1:
1769          {
1770            mpz_t x;
1771            mpz_t y;
1772            mpz_init(x);
1773            mpz_init(y);
1774            mpz_mul(x,b->z,a->n);
1775            mpz_mul(y,a->z,b->n);
1776            mpz_sub(u->z,y,x);
1777            mpz_clear(x);
1778            mpz_clear(y);
1779            if (mpz_cmp_ui(u->z,(long)0)==0)
1780            {
1781              mpz_clear(u->z);
1782              FREE_RNUMBER(u);
1783              return INT_TO_SR(0);
1784            }
1785            mpz_init(u->n);
1786            mpz_mul(u->n,a->n,b->n);
1787            if (mpz_cmp(u->z,u->n)==0)
1788            {
1789              mpz_clear(u->z);
1790              mpz_clear(u->n);
1791              FREE_RNUMBER(u);
1792              return INT_TO_SR(1);
1793            }
1794            u->s = 0;
1795            break;
1796          }
1797          case 3: /* a:1, b:3 */
1798          {
1799            mpz_t x;
1800            mpz_init(x);
1801            mpz_mul(x,b->z,a->n);
1802            mpz_sub(u->z,a->z,x);
1803            mpz_clear(x);
1804            if (mpz_cmp_ui(u->z,(long)0)==0)
1805            {
1806              mpz_clear(u->z);
1807              FREE_RNUMBER(u);
1808              return INT_TO_SR(0);
1809            }
1810            if (mpz_cmp(u->z,a->n)==0)
1811            {
1812              mpz_clear(u->z);
1813              FREE_RNUMBER(u);
1814              return INT_TO_SR(1);
1815            }
1816            mpz_init_set(u->n,a->n);
1817            u->s = 0;
1818            break;
1819          }
1820        }
1821        break;
1822      }
1823      case 3:
1824      {
1825        switch(b->s)
1826        {
1827          case 0:
1828          case 1: /* a:3, b:1 */
1829          {
1830            mpz_t x;
1831            mpz_init(x);
1832            mpz_mul(x,a->z,b->n);
1833            mpz_sub(u->z,x,b->z);
1834            mpz_clear(x);
1835            if (mpz_cmp_ui(u->z,(long)0)==0)
1836            {
1837              mpz_clear(u->z);
1838              FREE_RNUMBER(u);
1839              return INT_TO_SR(0);
1840            }
1841            if (mpz_cmp(u->z,b->n)==0)
1842            {
1843              mpz_clear(u->z);
1844              FREE_RNUMBER(u);
1845              return INT_TO_SR(1);
1846            }
1847            mpz_init_set(u->n,b->n);
1848            u->s = 0;
1849            break;
1850          }
1851          case 3: /* a:3 , b:3 */
1852          {
1853            mpz_sub(u->z,a->z,b->z);
1854            if (mpz_cmp_ui(u->z,(long)0)==0)
1855            {
1856              mpz_clear(u->z);
1857              FREE_RNUMBER(u);
1858              return INT_TO_SR(0);
1859            }
1860            u->s = 3;
1861            u=nlShort3(u);
1862            break;
1863          }
1864        }
1865        break;
1866      }
1867    }
1868  }
1869  return u;
1870}
1871
1872// a and b are intermediate, but a*b not
1873number _nlMult_aImm_bImm_rNoImm(number a, number b)
1874{
1875  number u=ALLOC_RNUMBER();
1876#if defined(LDEBUG)
1877  u->debug=123456;
1878#endif
1879  u->s=3;
1880  mpz_init_set_si(u->z,SR_TO_INT(a));
1881  mpz_mul_si(u->z,u->z,SR_TO_INT(b));
1882  return u;
1883}
1884
1885// a or b are not immediate
1886number _nlMult_aNoImm_OR_bNoImm(number a, number b)
1887{
1888  assume(! (SR_HDL(a) & SR_HDL(b) & SR_INT));
1889  number u=ALLOC_RNUMBER();
1890#if defined(LDEBUG)
1891  u->debug=123456;
1892#endif
1893  mpz_init(u->z);
1894  if (SR_HDL(b) & SR_INT)
1895  {
1896    number x=a;
1897    a=b;
1898    b=x;
1899  }
1900  if (SR_HDL(a) & SR_INT)
1901  {
1902    u->s=b->s;
1903    if (u->s==1) u->s=0;
1904    if ((long)a>0L)
1905    {
1906      mpz_mul_ui(u->z,b->z,(unsigned long)SR_TO_INT(a));
1907    }
1908    else
1909    {
1910      if (a==INT_TO_SR(-1))
1911      {
1912        mpz_set(u->z,b->z);
1913        mpz_neg(u->z,u->z);
1914        u->s=b->s;
1915      }
1916      else
1917      {
1918        mpz_mul_ui(u->z,b->z,(unsigned long)-SR_TO_INT(a));
1919        mpz_neg(u->z,u->z);
1920      }
1921    }
1922    if (u->s<2)
1923    {
1924      if (mpz_cmp(u->z,b->n)==0)
1925      {
1926        mpz_clear(u->z);
1927        FREE_RNUMBER(u);
1928        return INT_TO_SR(1);
1929      }
1930      mpz_init_set(u->n,b->n);
1931    }
1932    else //u->s==3
1933    {
1934      u=nlShort3(u);
1935    }
1936  }
1937  else
1938  {
1939    mpz_mul(u->z,a->z,b->z);
1940    u->s = 0;
1941    if(a->s==3)
1942    {
1943      if(b->s==3)
1944      {
1945        u->s = 3;
1946      }
1947      else
1948      {
1949        if (mpz_cmp(u->z,b->n)==0)
1950        {
1951          mpz_clear(u->z);
1952          FREE_RNUMBER(u);
1953          return INT_TO_SR(1);
1954        }
1955        mpz_init_set(u->n,b->n);
1956      }
1957    }
1958    else
1959    {
1960      if(b->s==3)
1961      {
1962        if (mpz_cmp(u->z,a->n)==0)
1963        {
1964          mpz_clear(u->z);
1965          FREE_RNUMBER(u);
1966          return INT_TO_SR(1);
1967        }
1968        mpz_init_set(u->n,a->n);
1969      }
1970      else
1971      {
1972        mpz_init(u->n);
1973        mpz_mul(u->n,a->n,b->n);
1974        if (mpz_cmp(u->z,u->n)==0)
1975        {
1976          mpz_clear(u->z);
1977          mpz_clear(u->n);
1978          FREE_RNUMBER(u);
1979          return INT_TO_SR(1);
1980        }
1981      }
1982    }
1983  }
1984  return u;
1985}
1986
1987/*2
1988* copy a to b for mapping
1989*/
1990number nlCopyMap(number a, const coeffs src, const coeffs dst)
1991{
1992  assume( getCoeffType(dst) == ID );
1993  assume( getCoeffType(src) == ID );
1994
1995  if ((SR_HDL(a) & SR_INT)||(a==NULL))
1996  {
1997    return a;
1998  }
1999  return _nlCopy_NoImm(a);
2000}
2001
2002nMapFunc nlSetMap(const coeffs src, const coeffs dst)
2003{
2004  assume( getCoeffType(dst) == ID );
2005//  assume( getCoeffType(src) == ID );
2006
2007  if (nCoeff_is_Q(src))
2008  {
2009    return ndCopyMap;
2010  }
2011  if (nCoeff_is_Zp(src))
2012  {
2013    return nlMapP;
2014  }
2015  if (nCoeff_is_R(src))
2016  {
2017    return nlMapR;
2018  }
2019  if (nCoeff_is_long_R(src))
2020  {
2021    return nlMapLongR; /* long R -> Q */
2022  }
2023#ifdef HAVE_RINGS
2024  if (nCoeff_is_Ring_Z(src) || nCoeff_is_Ring_PtoM(src) || nCoeff_is_Ring_ModN(src))
2025  {
2026    return nlMapGMP;
2027  }
2028  if (nCoeff_is_Ring_2toM(src))
2029  {
2030    return nlMapMachineInt;
2031  }
2032#endif
2033  return NULL;
2034}
2035/*2
2036* z := i
2037*/
2038number nlRInit (long i)
2039{
2040  number z=ALLOC_RNUMBER();
2041#if defined(LDEBUG)
2042  z->debug=123456;
2043#endif
2044  mpz_init_set_si(z->z,i);
2045  z->s = 3;
2046  return z;
2047}
2048
2049/*2
2050* z := i/j
2051*/
2052number nlInit2 (int i, int j, const coeffs r)
2053{
2054  number z=ALLOC_RNUMBER();
2055#if defined(LDEBUG)
2056  z->debug=123456;
2057#endif
2058  mpz_init_set_si(z->z,(long)i);
2059  mpz_init_set_si(z->n,(long)j);
2060  z->s = 0;
2061  nlNormalize(z,r);
2062  return z;
2063}
2064
2065number nlInit2gmp (mpz_t i, mpz_t j, const coeffs r)
2066{
2067  number z=ALLOC_RNUMBER();
2068#if defined(LDEBUG)
2069  z->debug=123456;
2070#endif
2071  mpz_init_set(z->z,i);
2072  mpz_init_set(z->n,j);
2073  z->s = 0;
2074  nlNormalize(z,r);
2075  return z;
2076}
2077
2078#else // DO_LINLINE
2079
2080// declare immedate routines
2081number nlRInit (int i);
2082BOOLEAN _nlEqual_aNoImm_OR_bNoImm(number a, number b);
2083number  _nlCopy_NoImm(number a);
2084number  _nlNeg_NoImm(number a);
2085number  _nlAdd_aNoImm_OR_bNoImm(number a, number b);
2086number  _nlSub_aNoImm_OR_bNoImm(number a, number b);
2087number  _nlMult_aNoImm_OR_bNoImm(number a, number b);
2088number  _nlMult_aImm_bImm_rNoImm(number a, number b);
2089
2090#endif
2091
2092/***************************************************************
2093 *
2094 * Routines which might be inlined by p_Numbers.h
2095 *
2096 *******************************************************************/
2097#if defined(DO_LINLINE) || !defined(P_NUMBERS_H)
2098
2099// routines which are always inlined/static
2100
2101/*2
2102* a = b ?
2103*/
2104LINLINE BOOLEAN nlEqual (number a, number b, const coeffs r)
2105{
2106  nlTest(a, r);
2107  nlTest(b, r);
2108// short - short
2109  if (SR_HDL(a) & SR_HDL(b) & SR_INT) return a==b;
2110  return _nlEqual_aNoImm_OR_bNoImm(a, b);
2111}
2112
2113LINLINE number nlInit (int i, const coeffs r)
2114{
2115  number n;
2116  LONG ii=(LONG)i;
2117  if ( ((ii << 3) >> 3) == ii ) n=INT_TO_SR(ii);
2118  else                          n=nlRInit(ii);
2119  nlTest(n, r);
2120  return n;
2121}
2122
2123/*2
2124* a == 1 ?
2125*/
2126LINLINE BOOLEAN nlIsOne (number a, const coeffs r)
2127{
2128#ifdef LDEBUG
2129  if (a==NULL) return FALSE;
2130  nlTest(a, r);
2131#endif
2132  return (a==INT_TO_SR(1));
2133}
2134
2135LINLINE BOOLEAN nlIsZero (number a, const coeffs)
2136{
2137  return (a==INT_TO_SR(0));
2138  //return (mpz_cmp_si(a->z,(long)0)==0);
2139}
2140
2141/*2
2142* copy a to b
2143*/
2144LINLINE number nlCopy(number a, const coeffs)
2145{
2146  if ((SR_HDL(a) & SR_INT)||(a==NULL))
2147  {
2148    return a;
2149  }
2150  return _nlCopy_NoImm(a);
2151}
2152
2153
2154/*2
2155* delete a
2156*/
2157LINLINE void nlDelete (number * a, const coeffs r)
2158{
2159  if (*a!=NULL)
2160  {
2161    nlTest(*a, r);
2162    if ((SR_HDL(*a) & SR_INT)==0)
2163    {
2164      _nlDelete_NoImm(a);
2165    }
2166    *a=NULL;
2167  }
2168}
2169
2170/*2
2171* za:= - za
2172*/
2173LINLINE number nlNeg (number a, const coeffs R)
2174{
2175  nlTest(a, R);
2176  if(SR_HDL(a) &SR_INT)
2177  {
2178    int r=SR_TO_INT(a);
2179    if (r==(-(POW_2_28))) a=nlRInit(POW_2_28);
2180    else               a=INT_TO_SR(-r);
2181    return a;
2182  }
2183  a = _nlNeg_NoImm(a);
2184  nlTest(a, R);
2185  return a;
2186
2187}
2188
2189/*2
2190* u:= a + b
2191*/
2192LINLINE number nlAdd (number a, number b, const coeffs R)
2193{
2194  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
2195  {
2196    LONG r=SR_HDL(a)+SR_HDL(b)-1L;
2197    if ( ((r << 1) >> 1) == r )
2198      return (number)(long)r;
2199    else
2200      return nlRInit(SR_TO_INT(r));
2201  }
2202  number u =  _nlAdd_aNoImm_OR_bNoImm(a, b);
2203  nlTest(u, R);
2204  return u;
2205}
2206
2207number nlShort1(number a);
2208number nlShort3_noinline(number x);
2209
2210static inline number nlInpAdd_(number a, number b, const coeffs r)
2211{
2212  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
2213  {
2214    LONG r=SR_HDL(a)+SR_HDL(b)-1L;
2215    if ( ((r << 1) >> 1) == r )
2216      return (number)(long)r;
2217    else
2218      return nlRInit(SR_TO_INT(r));
2219  }
2220  // a=a+b
2221  if (SR_HDL(b) & SR_INT)
2222  {
2223    switch (a->s)
2224    {
2225      case 0:
2226      case 1:/* b:short, a:1 */
2227      {
2228        mpz_t x;
2229        mpz_init(x);
2230        mpz_mul_si(x,a->n,SR_TO_INT(b));
2231        mpz_add(a->z,a->z,x);
2232        mpz_clear(x);
2233        a->s = 0;
2234        a=nlShort1(a);
2235        break;
2236      }
2237      case 3:
2238      {
2239        if ((long)b>0L)
2240          mpz_add_ui(a->z,a->z,SR_TO_INT(b));
2241        else
2242          mpz_sub_ui(a->z,a->z,-SR_TO_INT(b));
2243        a->s = 3;
2244        a=nlShort3_noinline(a);
2245        break;
2246      }
2247    }
2248    return a;
2249  }
2250  if (SR_HDL(a) & SR_INT)
2251  {
2252    number u=ALLOC_RNUMBER();
2253    #if defined(LDEBUG)
2254    u->debug=123456;
2255    #endif
2256    mpz_init(u->z);
2257    switch (b->s)
2258    {
2259      case 0:
2260      case 1:/* a:short, b:1 */
2261      {
2262        mpz_t x;
2263        mpz_init(x);
2264
2265        mpz_mul_si(x,b->n,SR_TO_INT(a));
2266        mpz_add(u->z,b->z,x);
2267        mpz_clear(x);
2268        // result cannot be 0, if coeffs are normalized
2269        mpz_init_set(u->n,b->n);
2270        u->s = 0;
2271        u=nlShort1(u);
2272        break;
2273      }
2274      case 3:
2275      {
2276        if ((long)a>0L)
2277          mpz_add_ui(u->z,b->z,SR_TO_INT(a));
2278        else
2279          mpz_sub_ui(u->z,b->z,-SR_TO_INT(a));
2280        // result cannot be 0, if coeffs are normalized
2281        u->s = 3;
2282        u=nlShort3_noinline(u);
2283        break;
2284      }
2285    }
2286    nlTest(u, r);
2287    return u;
2288  }
2289  else
2290  {
2291    switch (a->s)
2292    {
2293      case 0:
2294      case 1:
2295      {
2296        switch(b->s)
2297        {
2298          case 0:
2299          case 1: /* a:1 b:1 */
2300          {
2301            mpz_t x;
2302            mpz_t y;
2303            mpz_init(x);
2304            mpz_init(y);
2305            mpz_mul(x,b->z,a->n);
2306            mpz_mul(y,a->z,b->n);
2307            mpz_add(a->z,x,y);
2308            mpz_clear(x);
2309            mpz_clear(y);
2310            mpz_mul(a->n,a->n,b->n);
2311            a->s = 0;
2312            break;
2313          }
2314          case 3: /* a:1 b:3 */
2315          {
2316            mpz_t x;
2317            mpz_init(x);
2318            mpz_mul(x,b->z,a->n);
2319            mpz_add(a->z,a->z,x);
2320            mpz_clear(x);
2321            a->s = 0;
2322            break;
2323          }
2324        } /*switch (b->s) */
2325        a=nlShort1(a);
2326        break;
2327      }
2328      case 3:
2329      {
2330        switch(b->s)
2331        {
2332          case 0:
2333          case 1:/* a:3, b:1 */
2334          {
2335            mpz_t x;
2336            mpz_init(x);
2337            mpz_mul(x,a->z,b->n);
2338            mpz_add(a->z,b->z,x);
2339            mpz_clear(x);
2340            mpz_init_set(a->n,b->n);
2341            a->s = 0;
2342            a=nlShort1(a);
2343            break;
2344          }
2345          case 3:
2346          {
2347            mpz_add(a->z,a->z,b->z);
2348            a->s = 3;
2349            a=nlShort3_noinline(a);
2350            break;
2351          }
2352        }
2353        break;
2354      }
2355    }
2356    nlTest(a, r);
2357    return a;
2358  }
2359}
2360
2361LINLINE void nlInpAdd(number &a, number b, const coeffs r)
2362{
2363  a = nlInpAdd_(a, b, r);
2364}
2365
2366
2367LINLINE number nlMult (number a, number b, const coeffs R)
2368{
2369  nlTest(a, R);
2370  nlTest(b, R);
2371  if (a==INT_TO_SR(0)) return INT_TO_SR(0);
2372  if (b==INT_TO_SR(0)) return INT_TO_SR(0);
2373  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
2374  {
2375    LONG r=(SR_HDL(a)-1L)*(SR_HDL(b)>>1);
2376    if ((r/(SR_HDL(b)>>1))==(SR_HDL(a)-1L))
2377    {
2378      number u=((number) ((r>>1)+SR_INT));
2379      if (((((LONG)SR_HDL(u))<<1)>>1)==SR_HDL(u)) return (u);
2380      return nlRInit(SR_HDL(u)>>2);
2381    }
2382    number u = _nlMult_aImm_bImm_rNoImm(a, b);
2383    nlTest(u, R);
2384    return u;
2385
2386  }
2387  number u = _nlMult_aNoImm_OR_bNoImm(a, b);
2388  nlTest(u, R);
2389  return u;
2390
2391}
2392
2393
2394/*2
2395* u:= a - b
2396*/
2397LINLINE number nlSub (number a, number b, const coeffs r)
2398{
2399  if (SR_HDL(a) & SR_HDL(b) & SR_INT)
2400  {
2401    LONG r=SR_HDL(a)-SR_HDL(b)+1;
2402    if ( ((r << 1) >> 1) == r )
2403    {
2404      return (number)(long)r;
2405    }
2406    else
2407      return nlRInit(SR_TO_INT(r));
2408  }
2409  number u = _nlSub_aNoImm_OR_bNoImm(a, b);
2410  nlTest(u, r);
2411  return u;
2412
2413}
2414
2415LINLINE void nlInpMult(number &a, number b, const coeffs r)
2416{
2417  number aa=a;
2418  if (((SR_HDL(b)|SR_HDL(aa))&SR_INT))
2419  {
2420    number n=nlMult(aa,b,r);
2421    nlDelete(&a,r);
2422    a=n;
2423  }
2424  else
2425  {
2426    mpz_mul(aa->z,a->z,b->z);
2427    if (aa->s==3)
2428    {
2429      if(b->s!=3)
2430      {
2431        mpz_init_set(a->n,b->n);
2432        a->s=0;
2433      }
2434    }
2435    else
2436    {
2437      if(b->s!=3)
2438      {
2439        mpz_mul(a->n,a->n,b->n);
2440      }
2441      a->s=0;
2442    }
2443  }
2444}
2445#endif // DO_LINLINE
2446
2447#ifndef P_NUMBERS_H
2448
2449static void nlMPZ(mpz_t m, number &n, const coeffs r)
2450{
2451  assume( getCoeffType(r) == ID );
2452   
2453  nlTest(n, r);
2454  nlNormalize(n, r);
2455  if (SR_HDL(n) & SR_INT) mpz_init_set_si(m, SR_TO_INT(n));     /* n fits in an int */
2456  else             mpz_init_set(m, (mpz_ptr)n->z);
2457}
2458
2459
2460static number nlInitMPZ(mpz_t m, const coeffs)
2461{
2462  number z = ALLOC_RNUMBER();
2463  mpz_init_set(z->z, m);
2464  mpz_init_set_ui(z->n, 1);
2465  z->s = 3;
2466  return z;   
2467}
2468
2469
2470void nlInpGcd(number &a, number b, const coeffs r)
2471{
2472  if ((SR_HDL(b)|SR_HDL(a))&SR_INT)
2473  {
2474    number n=nlGcd(a,b,r);
2475    nlDelete(&a,r);
2476    a=n;
2477  }
2478  else
2479  {
2480    mpz_gcd(a->z,a->z,b->z);
2481    a=nlShort3_noinline(a);
2482  }
2483}
2484
2485void nlInpIntDiv(number &a, number b, const coeffs r)
2486{
2487  if ((SR_HDL(b)|SR_HDL(a))&SR_INT)
2488  {
2489    number n=nlIntDiv(a,b, r);
2490    nlDelete(&a,r);
2491    a=n;
2492  }
2493  else
2494  {
2495    if (mpz_isNeg(a->z))
2496    {
2497      if (mpz_isNeg(b->z))
2498      {
2499        mpz_add(a->z,a->z,b->z);
2500      }
2501      else
2502      {
2503        mpz_sub(a->z,a->z,b->z);
2504      }
2505      mpz_add_ui(a->z,a->z,1);
2506    }
2507    else
2508    {
2509      if (mpz_isNeg(b->z))
2510      {
2511        mpz_sub(a->z,a->z,b->z);
2512      }
2513      else
2514      {
2515        mpz_add(a->z,a->z,b->z);
2516      }
2517      mpz_sub_ui(a->z,a->z,1);
2518    }
2519    MPZ_DIV(a->z,a->z,b->z);
2520    a=nlShort3_noinline(a);
2521  }
2522}
2523
2524number nlFarey(number nN, number nP, const coeffs r)
2525{
2526  mpz_t tmp; mpz_init(tmp);
2527  mpz_t A,B,C,D,E,N,P;
2528  if (SR_HDL(nN) & SR_INT) mpz_init_set_si(N,SR_TO_INT(nN));
2529  else                     mpz_init_set(N,nN->z);
2530  if (SR_HDL(nP) & SR_INT) mpz_init_set_si(P,SR_TO_INT(nP));
2531  else                     mpz_init_set(P,nP->z);
2532  assume(!mpz_isNeg(P));
2533  if (mpz_isNeg(N))  mpz_add(N,N,P);
2534  mpz_init_set_si(A,(long)0);
2535  mpz_init_set_ui(B,(unsigned long)1);
2536  mpz_init_set_si(C,(long)0);
2537  mpz_init(D);
2538  mpz_init_set(E,P);
2539  number z=INT_TO_SR(0);
2540  while(mpz_cmp_si(N,(long)0)!=0)
2541  {
2542    mpz_mul(tmp,N,N);
2543    mpz_add(tmp,tmp,tmp);
2544    if (mpz_cmp(tmp,P)<0)
2545    {
2546       // return N/B
2547       z=ALLOC_RNUMBER();
2548       #ifdef LDEBUG
2549       z->debug=123456;
2550       #endif
2551       if (mpz_isNeg(B))
2552       {
2553         mpz_neg(B,B);
2554         mpz_neg(N,N);
2555       }
2556       mpz_init_set(z->z,N);
2557       mpz_init_set(z->n,B);
2558       z->s = 0;
2559       nlNormalize(z,r);
2560       break;
2561    }
2562    mpz_mod(D,E,N);
2563    mpz_div(tmp,E,N);
2564    mpz_mul(tmp,tmp,B);
2565    mpz_sub(C,A,tmp);
2566    mpz_set(E,N);
2567    mpz_set(N,D);
2568    mpz_set(A,B);
2569    mpz_set(B,C);
2570  }
2571  mpz_clear(tmp);
2572  mpz_clear(A);
2573  mpz_clear(B);
2574  mpz_clear(C);
2575  mpz_clear(D);
2576  mpz_clear(E);
2577  mpz_clear(N);
2578  mpz_clear(P);
2579  return z;
2580}
2581
2582void    nlCoeffWrite  (const coeffs, BOOLEAN /*details*/)
2583{
2584  PrintS("//   characteristic : 0\n");
2585}
2586
2587number   nlChineseRemainder(number *x, number *q,int rl, const coeffs C)
2588// elemenst in the array are x[0..(rl-1)], q[0..(rl-1)]
2589{
2590#ifdef HAVE_FACTORY
2591  setCharacteristic( 0 ); // only in char 0
2592  CFArray X(rl), Q(rl);
2593  int i;
2594  for(i=rl-1;i>=0;i--)
2595  {
2596    X[i]=C->convSingNFactoryN(x[i],FALSE,C); // may be larger MAX_INT
2597    Q[i]=C->convSingNFactoryN(q[i],FALSE,C); // may be larger MAX_INT
2598  }
2599  CanonicalForm xnew,qnew;
2600  chineseRemainder(X,Q,xnew,qnew);
2601  number n=C->convFactoryNSingN(xnew,C);
2602  number p=C->convFactoryNSingN(qnew,C);
2603  number p2=nlIntDiv(p,nlInit(2, C),C);
2604  if (nlGreater(n,p2,C))
2605  {
2606     number n2=nlSub(n,p,C);
2607     nlDelete(&n,C);
2608     n=n2;
2609  }
2610  nlDelete(&p,C);
2611  nlDelete(&p2,C);
2612  return n;
2613#else
2614  WerrorS("not implemented");
2615  return nlInit(0);
2616#endif
2617}
2618
2619BOOLEAN nlInitChar(coeffs r, void*)
2620{
2621  assume( getCoeffType(r) == ID );
2622  //const int ch = (int)(long)(p);
2623
2624  r->cfKillChar=NULL;
2625  r->nCoeffIsEqual=ndCoeffIsEqual;
2626  r->cfKillChar = ndKillChar; /* dummy */
2627
2628  r->cfInitMPZ = nlInitMPZ;
2629  r->cfMPZ  = nlMPZ;
2630   
2631  r->cfMult  = nlMult;
2632  r->cfSub   = nlSub;
2633  r->cfAdd   = nlAdd;
2634  r->cfDiv   = nlDiv;
2635  r->cfIntDiv= nlIntDiv;
2636  r->cfIntMod= nlIntMod;
2637  r->cfExactDiv= nlExactDiv;
2638  r->cfInit = nlInit;
2639  r->cfSize  = nlSize;
2640  r->cfInt  = nlInt;
2641   
2642  r->cfChineseRemainder=nlChineseRemainder;
2643  r->cfFarey=nlFarey;
2644  #ifdef HAVE_RINGS
2645  //r->cfDivComp = NULL; // only for ring stuff
2646  //r->cfIsUnit = NULL; // only for ring stuff
2647  //r->cfGetUnit = NULL; // only for ring stuff
2648  //r->cfExtGcd = NULL; // only for ring stuff
2649  //r->cfDivBy = NULL; // only for ring stuff
2650  #endif
2651  r->cfNeg   = nlNeg;
2652  r->cfInvers= nlInvers;
2653  r->cfCopy  = nlCopy;
2654  r->cfRePart = nlCopy;
2655  //r->cfImPart = ndReturn0;
2656  r->cfWrite = nlWrite;
2657  r->cfRead = nlRead;
2658  r->cfNormalize=nlNormalize;
2659  r->cfGreater = nlGreater;
2660  r->cfEqual = nlEqual;
2661  r->cfIsZero = nlIsZero;
2662  r->cfIsOne = nlIsOne;
2663  r->cfIsMOne = nlIsMOne;
2664  r->cfGreaterZero = nlGreaterZero;
2665  r->cfPower = nlPower;
2666  r->cfGetDenom = nlGetDenom;
2667  r->cfGetNumerator = nlGetNumerator;
2668  r->cfGcd  = nlGcd;
2669  r->cfLcm  = nlLcm;
2670  r->cfDelete= nlDelete;
2671  r->cfSetMap = nlSetMap;
2672  //r->cfName = ndName;
2673  r->cfInpMult=nlInpMult;
2674  r->cfInit_bigint=nlCopyMap;
2675  r->cfCoeffWrite=nlCoeffWrite;
2676#ifdef LDEBUG
2677  // debug stuff
2678  r->cfDBTest=nlDBTest;
2679#endif
2680#ifdef HAVE_FACTORY
2681  r->convSingNFactoryN=nlConvSingNFactoryN;
2682  r->convFactoryNSingN=nlConvFactoryNSingN;
2683#endif
2684
2685  // the variables: general stuff (required)
2686  r->nNULL = INT_TO_SR(0);
2687  //r->type = n_Q;
2688  r->ch = 0;
2689  r->has_simple_Alloc=FALSE;
2690  r->has_simple_Inverse=FALSE;
2691
2692  // variables for this type of coeffs:
2693  // (none)
2694  return FALSE;
2695}
2696#if 0
2697number nlMod(number a, number b)
2698{
2699  if (((SR_HDL(b)&SR_HDL(a))&SR_INT)
2700  {
2701    int bi=SR_TO_INT(b);
2702    int ai=SR_TO_INT(a);
2703    int bb=ABS(bi);
2704    int c=ai%bb;
2705    if (c<0)  c+=bb;
2706    return (INT_TO_SR(c));
2707  }
2708  number al;
2709  number bl;
2710  if (SR_HDL(a))&SR_INT)
2711    al=nlRInit(SR_TO_INT(a));
2712  else
2713    al=nlCopy(a);
2714  if (SR_HDL(b))&SR_INT)
2715    bl=nlRInit(SR_TO_INT(b));
2716  else
2717    bl=nlCopy(b);
2718  number r=nlRInit(0);
2719  mpz_mod(r->z,al->z,bl->z);
2720  nlDelete(&al);
2721  nlDelete(&bl);
2722  if (mpz_size1(&r->z)<=MP_SMALL)
2723  {
2724    LONG ui=(int)mpz_get_si(&r->z);
2725    if ((((ui<<3)>>3)==ui)
2726    && (mpz_cmp_si(x->z,(long)ui)==0))
2727    {
2728      mpz_clear(&r->z);
2729      FREE_RNUMBER(r); //  omFreeBin((void *)r, rnumber_bin);
2730      r=INT_TO_SR(ui);
2731    }
2732  }
2733  return r;
2734}
2735#endif
2736#endif // not P_NUMBERS_H
2737#endif // LONGRAT_CC
Note: See TracBrowser for help on using the repository browser.