# Changeset 6ea941 in git

Ignore:
Timestamp:
Jul 3, 2009, 3:14:10 PM (14 years ago)
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
Parents:
a209ec5a023aa3cf7d9f9167a249678feca0047b
Message:
corrected a modulo b in Z/n and Z/2^m

Location:
kernel
Files:
5 edited

Unmodified
Removed
• ## kernel/numbers.cc

 ra209ec5 *  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 \$ */ /* n->nDiv   = nr2mDiv; n->nIntDiv       = nr2mIntDiv; n->nIntMod=nr2mMod; n->nExactDiv= nr2mDiv; n->nNeg   = nr2mNeg; n->nDiv   = nrnDiv; n->nIntDiv= nrnIntDiv; n->nIntMod= nrnMod; n->nExactDiv= nrnDiv; n->nNeg   = nrnNeg;
• ## kernel/rmodulo2m.cc

 ra209ec5 *  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 } 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

 ra209ec5 *  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 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

 ra209ec5 *  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 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

 ra209ec5 *  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 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);
Note: See TracChangeset for help on using the changeset viewer.