Changeset 6ea941 in git

Timestamp:

Jul 3, 2009, 3:14:10 PM (14 years ago)

Author:

Frank Seelisch <seelisch@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

e1634d68136a437eacace709df6dc52c3227ad7f

Parents:

a209ec5a023aa3cf7d9f9167a249678feca0047b

Message:

corrected a modulo b in Z/n and Z/2^m


git-svn-id: file:///usr/local/Singular/svn/trunk@11940 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

kernel

Files:

• numbers.cc (modified) (3 diffs)
• rmodulo2m.cc (modified) (2 diffs)
• rmodulo2m.h (modified) (2 diffs)
• rmodulon.cc (modified) (2 diffs)
• rmodulon.h (modified) (2 diffs)

kernel/numbers.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR      *
 *****************************************/
-/* $Id: numbers.cc,v 1.22 2009-06-09 18:10:44 Singular Exp $ */
+/* $Id: numbers.cc,v 1.23 2009-07-03 13:14:10 seelisch Exp $ */
 
 /*
@@ -367 +367 @@
      n->nDiv   = nr2mDiv;
      n->nIntDiv       = nr2mIntDiv;
+     n->nIntMod=nr2mMod;
      n->nExactDiv= nr2mDiv;
      n->nNeg   = nr2mNeg;
@@ -409 +410 @@
      n->nDiv   = nrnDiv;
      n->nIntDiv= nrnIntDiv;
+     n->nIntMod= nrnMod;
      n->nExactDiv= nrnDiv;
      n->nNeg   = nrnNeg;

kernel/rmodulo2m.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: rmodulo2m.cc,v 1.24 2009-05-06 12:53:49 Singular Exp $ */
+/* $Id: rmodulo2m.cc,v 1.25 2009-07-03 13:14:10 seelisch Exp $ */
 /*
 * ABSTRACT: numbers modulo 2^m
@@ -346 +346 @@
 }
 
+number nr2mMod (number a, number b)
+{
+  /*
+    We need to return the number r which is uniquely determined by the
+    following two properties:
+      (1) 0 <= r < |b| (with respect to '<' and '<=' performed in Z x Z)
+      (2) There exists some k in the integers Z such that a = k * b + r.
+    Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
+    Now, there are three cases:
+      (a) g = 1
+          Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
+          Thus r = 0.
+      (b) g <> 1 and g divides a
+          Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again r = 0.
+      (c) g <> 1 and g does not divide a
+          Let's denote the division with remainder of a by g as follows:
+          a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
+          fulfills (1) and (2), i.e. r := t is the correct result. Hence
+          in this third case, r is the remainder of division of a by g in Z.
+    This algorithm is the same as for the case Z/n, except that we may
+    compute the gcd of |b| and 2^m "by hand": We just extract the highest
+    power of 2 (<= 2^m) that is contained in b.
+  */
+  NATNUMBER g = 1;
+  NATNUMBER b_div = b;
+  if (b_div < 0) b_div = - b_div; // b_div now represents |b|
+  NATNUMBER r = 0;
+  while ((g < nr2mModul) && (b_div > 0) && (b_div % 2 == 0))
+  {
+    b_div = b_div >> 1;
+    g = g << 1;
+  } // g is now the gcd of 2^m and |b|
+
+  if (g != 1) r = (NATNUMBER)a % g;
+  return (number)r;
+}
+
 number nr2mIntDiv (number a,number b)
 {

kernel/rmodulo2m.h

@@ -4 +4 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: rmodulo2m.h,v 1.11 2009-05-06 12:53:49 Singular Exp $ */
+/* $Id: rmodulo2m.h,v 1.12 2009-07-03 13:14:10 seelisch Exp $ */
 /*
 * ABSTRACT: numbers modulo 2^m
@@ -28 +28 @@
 number  nr2mDiv         (number a, number b);
 number  nr2mIntDiv      (number a,number b);
+number  nr2mMod         (number a,number b);
 number  nr2mNeg         (number c);
 number  nr2mInvers      (number c);

kernel/rmodulon.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: rmodulon.cc,v 1.34 2009-05-22 13:18:12 Singular Exp $ */
+/* $Id: rmodulon.cc,v 1.35 2009-07-03 13:14:10 seelisch Exp $ */
 /*
 * ABSTRACT: numbers modulo n
@@ -317 +317 @@
     return (number) erg;
   }
+}
+
+number nrnMod (number a, number b)
+{
+  /*
+    We need to return the number r which is uniquely determined by the
+    following two properties:
+      (1) 0 <= r < |b| (with respect to '<' and '<=' performed in Z x Z)
+      (2) There exists some k in the integers Z such that a = k * b + r.
+    Consider g := gcd(n, |b|). Note that then |b|/g is a unit in Z/n.
+    Now, there are three cases:
+      (a) g = 1
+          Then |b| is a unit in Z/n, i.e. |b| (and also b) divides a.
+          Thus r = 0.
+      (b) g <> 1 and g divides a
+          Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again r = 0.
+      (c) g <> 1 and g does not divide a
+          Then denote the division with remainder of a by g as this:
+          a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
+          fulfills (1) and (2), i.e. r := t is the correct result. Hence
+          in this third case, r is the remainder of division of a by g in Z.
+  */
+  int_number g = (int_number) omAllocBin(gmp_nrn_bin);
+  int_number b_abs = (int_number) omAllocBin(gmp_nrn_bin);
+  int_number r = (int_number) omAllocBin(gmp_nrn_bin);
+  mpz_init(g);
+  mpz_init_set(b_abs,(int_number)b);
+  mpz_init_set_si(r,(long)0);
+  if (mpz_isNeg(b_abs)) mpz_neg(b_abs, b_abs); // b_abs now represents |b|
+  mpz_gcd(g, (int_number) nrnModul, b_abs); // g is now as above
+  if (mpz_cmp_si(g, (long)1) != 0) mpz_mod(r, (int_number)a, g); // the case g <> 1
+  mpz_clear(g);
+  mpz_clear(b_abs);
+  omFreeBin(g, gmp_nrn_bin);
+  omFreeBin(b_abs, gmp_nrn_bin);
+  return (number)r;
 }
 

kernel/rmodulon.h

@@ -4 +4 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: rmodulon.h,v 1.11 2009-05-22 16:57:41 Singular Exp $ */
+/* $Id: rmodulon.h,v 1.12 2009-07-03 13:14:10 seelisch Exp $ */
 /*
 * ABSTRACT: numbers modulo n
@@ -32 +32 @@
 number  nrnGetUnit     (number a);
 number  nrnDiv         (number a, number b);
+number  nrnMod         (number a,number b);
 number  nrnIntDiv      (number a,number b);
 number  nrnNeg         (number c);