Changeset 7d73a53 in git

Timestamp:

Feb 23, 2016, 5:09:19 PM (8 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b4f17ed1d25f93d46dbe29e4b499baecc2fd51bb')

Children:

ca5f5ec50e7d7e43e956e80b9cff948d8a89ee55

Parents:

6828dc2a9db4f0616aef09df69cf620b2f3ace02

Message:

div and mod for Z

Files:

• Singular/LIB/atkins.lib (modified) (3 diffs)
• Tst/Manual/Schoof.res.gz.uu (modified) (1 diff)
• Tst/Manual/bigint_operations.res.gz.uu (modified) (1 diff)
• Tst/Manual/bigint_operations.stat (modified) (1 diff)
• Tst/Manual/bigint_operations.tst (modified) (1 diff)
• Tst/Manual/chineseRem.res.gz.uu (modified) (1 diff)
• Tst/Manual/coeffmod.res.gz.uu (modified) (1 diff)
• Tst/Manual/powerpolyX.res.gz.uu (modified) (1 diff)
• libpolys/coeffs/coeffs.h (modified) (2 diffs)
• libpolys/coeffs/longrat.cc (modified) (14 diffs)

Singular/LIB/atkins.lib

@@ -200 +200 @@
 "
 {
-  if((D>=0)||((D mod 4)==-2)||((D mod 4)==-1)||(absValue(D)>=4*p))
+  if((D>=0)||((D mod 4)==2)||((D mod 4)==3)||(absValue(D)>=4*p))
   {                                  // (0)[Test if assumptions well-defined]
     return(0);
@@ -231 +231 @@
       {
         x(0)=squareRoot(D,p);        // (3)[Compute square root]
-        if((x(0) mod 2)!=(-(D mod 2))) // D is <0
+        if((x(0) mod 2)!=(D mod 2)) // D is <0
         {
           x(0)=p-x(0);
@@ -248 +248 @@
         if((((4*p-b^2) mod absValue(D))!=0)||(c!=root_c^2))
         {
+        "3";
           return(-1);
           // ERROR("The Diophantine equation has no solution!");

Tst/Manual/Schoof.res.gz.uu

@@ -1 @@
-begin 644 Schoof.res.gz
-M'XL(")JNRU```U-C:&]O9BYR97,`"PYQ\?134%`PM%/P\7124"HI+M'+R4Q2
+begin 640 Schoof.res.gz
+M'XL(".B`S%8``U-C:&]O9BYR97,`"PYQ\?134%`PM%/P\7124"HI+M'+R4Q2
 MLE8`LN(S\S)+-#2MN4"T@IV=0G!R1GY^FEY>:KE><4EB"5<P5+<15'=R465!
-M23[$`+BDL9U"469>ND*0@JV"@4Z53DH!0LX$9J:&L9&!@;&.N:&.F8$1T$9C
->$V-C0[@R4SNP<T!VEA9K&&I:JW`!`+6AQ42Y````
+M23[$`+BDL9U"469>ND*0@JV"@4Z53DH!0LX$9J:&L9&!@;&.N:&.F8$1T$8@
+<U\@0KLS4#NP<D)VEQ1J&FM8J7`#Q;,(BN0``````
 `
 end

Tst/Manual/bigint_operations.res.gz.uu

@@ -1 @@
-begin 644 bigint_operations.res.gz
-M'XL("(.NRU```V)I9VEN=%]O<&5R871I;VYS+G)E<P!%CL$*PC`,AN]]BB`>
-M5K$CS=;.4>A!O`S$RSP[-C:DH)VXJJ^O$S=/27[^?'SE<5<<`$!:V!=;6(0A
-MQ!?7+`Q\MLIY%R)NV#C!6FC<V?E0];?N7@?7^R'VW2L>0AU8^0/1U(H47]%Z
-M.HB?)**0:)A$D*0SK5`C$FV(\A1EFNL,$T*5:#W#DADF%(?6/>%/')-KWP(9
-9)@B$G)]2^W4?K1Y#)+E9LC=-JX5/Y@``````
+begin 640 bigint_operations.res.gz
+M'XL(",Z!S%8``V)I9VEN=%]O<&5R871I;VYS+G)E<P"=E<MNG#`4AO<\Q1'*
+M`M*!^((A%`V+JIM(53?INB,SH5,K#$0#:56-^NZU"=@0CPH)"^S#\??[W"3N
+MOWV^^PH`.(<O=Y_`[=HNK$3A9B!W.U&+SO,S1ZV0YU"(@ZB[7?-4GG@GFKH-
+MZ_)WV':\<^X'(3*>\IA_33:C0?SO&*$`H\S!"#")DYBA&"%";@E)(X2C-$X0
+M)8C1.-9B5(L%S(<'\0N,HOIR;!Z`9$Y``6LFRD'O60A/IV8/^Y_E_G$G>0EX
+M+SSP40D*7P-Q"&=M)*%\B1_@>;R_N_"OBP]RKVXM_.V6&RY51S6)L3(!W/;Y
+M",TC_^-FVD65ZZ\VF3++JBWUEV0NE0Y2,H"/[F8(1,N1\2894^_N8S-N:@*1
+M[HMY;%S@"I5K(=<)S&:ADJ$<GB;S+?+A[+;B4`]9FL/IF!><P1V`28!&ELH,
+MC"&GY^8&VB.OJJ!_:X_,9-;%9$/E8(X%=G00&I!S\`H(%@CVB@B6D=A&%HC$
+M9`A!Q4\'W7EZ:Z>(]/-_U?1"LBO9"%U*>RV,+Q1@+?O2[+X&\V9'5K.-Y$)]
+M(ZOM$W2AFY$]`&^`[5%8'W0RJ<1L)B)K)J:B:PMM3<<LK94JS)Z3=\G8$_..
+9E)B<'?6#4K^>Y];#?G;E_`-SNM#'RP8`````
 `
 end

Tst/Manual/bigint_operations.stat

@@ -1 @@
-1 >> tst_memory_0 :: 1355525762:3150:3-1-5:x86_64-Linux:snork:184288
-1 >> tst_memory_1 :: 1355525762:3150:3-1-5:x86_64-Linux:snork:2240216
-1 >> tst_memory_2 :: 1355525762:3150:3-1-5:x86_64-Linux:snork:2273016
-1 >> tst_timer_1 :: 1355525762:3150:3-1-5:x86_64-Linux:snork:3
+1 >> tst_memory_0 :: 1456243150:4030, 64 bit:4.0.3:x86_64-Linux:nepomuck:104680
+1 >> tst_memory_1 :: 1456243150:4030, 64 bit:4.0.3:x86_64-Linux:nepomuck:2228224
+1 >> tst_memory_2 :: 1456243150:4030, 64 bit:4.0.3:x86_64-Linux:nepomuck:2228224
+1 >> tst_timer_1 :: 1456243150:4030, 64 bit:4.0.3:x86_64-Linux:nepomuck:0

Tst/Manual/bigint_operations.tst

@@ -2 +2 @@
 bigint(5)*2, bigint(2)^100-10;
 bigint(-5) div 2, bigint(-5) mod 2;
+
+proc check_divmod(bigint a, bigint b)
+{
+  if ((a div b)*b+(a mod b)==a)
+  {
+    "sum okay";
+  }
+  else
+  {
+    "div:",a div b;
+    "mod:",a mod b;
+    "sum:",(a div b)*b+(a mod b)," a:",a," b:",b;
+  }
+  if((a mod b)>=0) {"sign okay";}
+  else { "a mod b:",a mod b; }
+}
+// small-small
+check_divmod(7,3);
+check_divmod(7,-3);
+check_divmod(-7,-3);
+check_divmod(-7,3);
+// small -large
+check_divmod(7,30000000000);
+check_divmod(7,-30000000000);
+check_divmod(-7,-30000000000);
+check_divmod(-7,30000000000);
+// large-small
+check_divmod(70000000000,3);
+check_divmod(70000000000,-3);
+check_divmod(-70000000000,-3);
+check_divmod(-70000000000,3);
+// large-large
+check_divmod(70000000000,30000000000);
+check_divmod(70000000000,-30000000000);
+check_divmod(-70000000000,-30000000000);
+check_divmod(-70000000000,30000000000);
 tst_status(1);$

Tst/Manual/chineseRem.res.gz.uu

@@ -1 @@
-begin 644 chineseRem.res.gz
-M'XL("(6NRU```V-H:6YE<V5296TN<F5S``L.<?'T4U!0,+13\/%T4E`J*2[1
+begin 640 chineseRem.res.gz
+M'XL("#M_S%8``V-H:6YE<V5296TN<F5S``L.<?'T4U!0,+13\/%T4E`J*2[1
 MR\E,4K)6`++B,_,R2S0TK;E`M(*=G4)R1F9>:G%J4&JN7EYJN5YQ26()5S#4
 M!".H"<E%E04E^1!#X)+&=@I%F7GI"D$*M@H&.A4Z*04(.1-D<S5R,HM+-(Q,
-M=`Q-=<PU=2`\'6,=4TV@,W0-+>"Z3.W`+@0YH;18PU#36H4+`'1Z&C_,````
+L=`Q-=<PU=2`\'6,=4TV@,PR-X)I,[<`.!+F@M%C#4--:A0L`SAN<F\L`````
 `
 end

Tst/Manual/coeffmod.res.gz.uu

@@ -1 +1 @@
 begin 640 coeffmod.res.gz
-M'XL(".[^FE,``V-O969F;6]D+G)E<P!%C\T.@C`0A.\\Q89XX$\BI14-H0?C
-MA<1X$.^F""4-6(C46-]>4`*GW>S,MYG)KL?T#``!A5-Z`%/URF]$;L8P;#<A
-MA;+LV!@G4`KWMN3\T1:^+-]^KY@RLHE'$\_JGM7L_V(60PI/(2NX0`(;3WM%
-MMVB80M<V'^`)PB1R-'8)"C%Q=+C>[QR-7+)X"85<5$(JD$FXG+=+,(M[<L@[
-:P&A`T6R)Z*_/&/G56X$=KXPO<-+XE?H`````
+M'XL("/U^S%8``V-O969F;6]D+G)E<P!%C\T.@C`0A.\\Q89XX$\B+14-H0?C
+MA<1X$.\&A)(&+$1JK&\O**&GW>S,;+[)KL?T#``!A5-Z`%,.TF]Y8<8P;C<N
+MN+3LV)@F4`KWKF+LT96^J-[^('-I9',>S?F\&?(F_[]81$SAR44-%TA@XRFO
+M[+464NB[]@,L02&)'!6Z!.&0.`JO]SM'(9=H+Z%0\)H+"2+!^KS58!;SQ,BK
+:L#LFT>*(Z*_.1/P:K,".5\87X.574OD`````
 `
 end

Tst/Manual/powerpolyX.res.gz.uu

@@ -1 +1 @@
 begin 640 powerpolyX.res.gz
-M'XL("&<$FU,``W!O=V5R<&]L>5@N<F5S`$V//0^",!"&=W[%Q3B@%&*I^!'2
-M#L;%Q#B(@YNIT9A&4J"MH?Q[00EENLL]E^?NS2[[PPD`,(/C80<3HTV4B_LD
-MA;:["2F,/TN]K@)C4!;U4Y5%WEPC^:PC;;CQLMX0]P;^UOS-_Y(!$@9*R!><
-MZ0)9]"@=67;6O`%.R=R2T,9!XF#20T7M.L1NOF)P%R\A#504Q\2!]0`D'7DV
-JX]?]"DG$D6IS$9N$Q"X#2X+V,![VM^P7O\OWT3Z>I5/O"Y74O)TI`0``
+M'XL("(-_S%8``W!O=V5R<&]L>5@N<F5S`$V//0^",!"&=W[%Q3B@%&);$`UI
+M!^-B8AS4P<W4:$@#*5\UE'\O**%.=[GG\MR]E^O^<`(`S.%XV,%,-SK(Y6.6
+M0-_=I9+:723.4(%S*(OV59=%WMT"]6J#1@OM7$8#&0TB:T0F?I()4@ZU5"F<
+MV0H9]"PM"0=KWH%@=&FH;X@761B-L&8F]K&=KSD\9"J5AHIA0BV()Z#8GV?S
+J_[I;(84$JOM<U$0>,:%GJ-<?QM/^EG_C#_G>C8L7R=SY`"R^3(8I`0``
 `
 end

libpolys/coeffs/coeffs.h

@@ -613 +613 @@
 /// raises an error if 'b' is not invertible in r
 /// exception in Z: raises an error if 'a' is not divisible by 'b'
+/// always: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a
 static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
 { STATISTIC(n_Div); assume(r != NULL); assume(r->cfDiv!=NULL); return r->cfDiv(a,b,r); }
@@ -624 +625 @@
 
 /// for r a field, return n_Init(0,r)
-/// otherwise: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a
+/// always: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a
+/// n_IntMod(a,b,r) >=0
 static FORCE_INLINE number n_IntMod(number a, number b, const coeffs r)
 { STATISTIC(n_IntMod); assume(r != NULL); return r->cfIntMod(a,b,r); }

libpolys/coeffs/longrat.cc

@@ -160 +160 @@
 #define mpz_limb_size(A) ((A)->_mp_size)
 #define mpz_limb_d(A) ((A)->_mp_d)
-#define MPZ_DIV(A,B,C) mpz_tdiv_q((A),(B),(C))
-#define MPZ_EXACTDIV(A,B,C) mpz_divexact((A),(B),(C))
 
 void    _nlDelete_NoImm(number *a);
@@ -624 +622 @@
   long ul;
   mpz_init(tmp);
-  MPZ_DIV(tmp,i->z,i->n);
+  mpz_tdiv_q(tmp,i->z,i->n);
   if(mpz_size1(tmp)>MP_SMALL) ul=0;
   else
@@ -648 +646 @@
   }
   number tmp=nlRInit(1);
-  MPZ_DIV(tmp->z,i->z,i->n);
+  mpz_tdiv_q(tmp->z,i->z,i->n);
   tmp=nlShort3(tmp);
   return tmp;
@@ -769 +767 @@
   /* u=a/b */
   u->s = 3;
-  MPZ_EXACTDIV(u->z,a->z,b->z);
+  mpz_divexact(u->z,a->z,b->z);
   if (bb!=NULL)
   {
@@ -803 +801 @@
       return nlRInit(POW_2_28);
     }
-    long aa=SR_TO_INT(a);
-    long bb=SR_TO_INT(b);
-    return INT_TO_SR(aa/bb);
-  }
+    LONG aa=SR_TO_INT(a);
+    LONG bb=SR_TO_INT(b);
+    LONG rr=aa%bb;
+    if (rr<0) rr+=ABS(bb);
+    LONG cc=(aa-rr)/bb;
+    return INT_TO_SR(cc);
+  }
+  number aa=NULL;
   if (SR_HDL(a) & SR_INT)
   {
@@ -817 +819 @@
       }
     }
-    /* a is a small and b is a large int: -> 0 */
-    return INT_TO_SR(0);
+    aa=nlRInit(SR_TO_INT(a));
+    a=aa;
   }
   number bb=NULL;
@@ -835 +837 @@
   /* u=u/b */
   u->s = 3;
-  MPZ_DIV(u->z,u->z,b->z);
+  number rr=nlIntMod(a,b,r);
+  if (SR_HDL(rr) &  SR_INT) mpz_sub_ui(u->z,u->z,SR_TO_INT(rr));
+  else                      mpz_sub(u->z,u->z,rr->z);
+  mpz_divexact(u->z,u->z,b->z);
+  if (aa!=NULL)
+  {
+    mpz_clear(aa->z);
+#if defined(LDEBUG)
+    aa->debug=654324;
+#endif
+    FREE_RNUMBER(aa);
+  }
   if (bb!=NULL)
   {
@@ -864 +877 @@
   if (SR_HDL(a) & SR_HDL(b) & SR_INT)
   {
+    LONG aa=SR_TO_INT(a);
     LONG bb=SR_TO_INT(b);
-    LONG c=SR_TO_INT(a) % bb;
+    LONG c=aa % bb;
+    if (c<0) c+=ABS(bb);
     return INT_TO_SR(c);
   }
   if (SR_HDL(a) & SR_INT)
   {
+    LONG ai=SR_TO_INT(a);
     mpz_t aa;
-    mpz_init(aa);
-    mpz_set_si(aa, SR_TO_INT(a));
+    mpz_init_set_si(aa, ai);
     u=ALLOC_RNUMBER();
 #if defined(LDEBUG)
@@ -879 +894 @@
     u->s = 3;
     mpz_init(u->z);
-    mpz_t q;
-    mpz_init(q);
-    mpz_tdiv_qr(q,u->z, aa, b->z);
-    mpz_clear(q);
+    mpz_mod(u->z, aa, b->z);
     mpz_clear(aa);
     u=nlShort3(u);
@@ -900 +912 @@
   mpz_init(u->z);
   u->s = 3;
-  mpz_t q;
-  mpz_init(q);
-  mpz_tdiv_qr(q, u->z, a->z, b->z);
-  mpz_clear(q);
+  mpz_mod(u->z, a->z, b->z);
   if (bb!=NULL)
   {
@@ -1349 +1358 @@
       if (mpz_cmp_si(gcd,(long)1)!=0)
       {
-        MPZ_EXACTDIV(x->z,x->z,gcd);
-        MPZ_EXACTDIV(x->n,x->n,gcd);
+        mpz_divexact(x->z,x->z,gcd);
+        mpz_divexact(x->n,x->n,gcd);
         if (mpz_cmp_si(x->n,(long)1)==0)
         {
@@ -1394 +1403 @@
     mpz_t bt;
     mpz_init_set(bt,b->n);
-    MPZ_EXACTDIV(bt,bt,gcd);
+    mpz_divexact(bt,bt,gcd);
     if (SR_HDL(a) & SR_INT)
       mpz_mul_si(result->z,bt,SR_TO_INT(a));
@@ -1646 +1655 @@
   if (mpz_cmp_si(gcd,(long)1)!=0)
   {
-    MPZ_EXACTDIV(x->z,x->z,gcd);
-    MPZ_EXACTDIV(x->n,x->n,gcd);
+    mpz_divexact(x->z,x->z,gcd);
+    mpz_divexact(x->n,x->n,gcd);
     if (mpz_cmp_si(x->n,(long)1)==0)
     {
@@ -2803 +2812 @@
   else
   {
-    if (mpz_isNeg(a->z))
-    {
-      if (mpz_isNeg(b->z))
-      {
-        mpz_add(a->z,a->z,b->z);
-      }
-      else
-      {
-        mpz_sub(a->z,a->z,b->z);
-      }
-      mpz_add_ui(a->z,a->z,1);
-    }
-    else
-    {
-      if (mpz_isNeg(b->z))
-      {
-        mpz_sub(a->z,a->z,b->z);
-      }
-      else
-      {
-        mpz_add(a->z,a->z,b->z);
-      }
-      mpz_sub_ui(a->z,a->z,1);
-    }
-    MPZ_DIV(a->z,a->z,b->z);
+    number rr=nlIntMod(a,b,r);
+    if (SR_HDL(rr) &  SR_INT) mpz_sub_ui(a->z,a->z,SR_TO_INT(rr));
+    else                      mpz_sub(a->z,a->z,rr->z);
+    mpz_divexact(a->z,a->z,b->z);
     a=nlShort3_noinline(a);
   }