Changeset c12372 in git for factory/cf_chinese.cc

Timestamp:

Jul 24, 1997, 12:39:35 PM (27 years ago)

Author:

Jens Schmidt <schmidt@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

063ebbbe875cacd2b1e4f25d7006348a5823fc8a

Parents:

960f2ac0a38ea1611c75e0b2fd1764a6c0554fe1

Message:

	* cf_chinese.cc (chineseRemainder( CF, ... )): operator % replaced
	  by function mod()


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

File:

• factory/cf_chinese.cc (modified) (4 diffs)

factory/cf_chinese.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_chinese.cc,v 1.4 1997-07-19 08:13:16 schmidt Exp $ */
+/* $Id: cf_chinese.cc,v 1.5 1997-07-24 10:39:35 schmidt Exp $ */
 
 //{{{ docu
@@ -14 +14 @@
 #include "assert.h"
 
-#include "cf_defs.h"
 #include "canonicalform.h"
 
@@ -20 +19 @@
 //{{{ docu
 //
-// chineseRemainder - (simple) integer chinese remaindering.
+// chineseRemainder - integer chinese remaindering.
 //
-// Calculate xnew such that xnew=x1 (mod q1) and xnew=x2
-// (mod q2) and qnew = q1*q2.  q1 and q2 should be integers,
-// pairwise prime, x1 and x2 should be integers.
+// Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2)
+// and qnew = q1*q2.  q1 and q2 should be positive integers,
+// pairwise prime, x1 and x2 should be polynomials with integer
+// coefficients.  If x1 and x2 are polynomials with positive
+// coefficients, the result is guaranteed to have positive
+// coefficients, too.
 //
 // Note: be sure you are calculating in Z, and not in Q!
 //
 //}}}
-void chineseRemainder( const CanonicalForm x1, const CanonicalForm q1, const CanonicalForm x2, const CanonicalForm q2, CanonicalForm & xnew, CanonicalForm & qnew )
+void
+chineseRemainder( const CanonicalForm x1, const CanonicalForm q1, const CanonicalForm x2, const CanonicalForm q2, CanonicalForm & xnew, CanonicalForm & qnew )
 {
     CanonicalForm a1, a2;
     (void)iextgcd( q1, q2, a1, a2 );
     qnew = q1 * q2;
-    // xnew = mod( q1*a1*x2 + q2*a2*x1, qnew);
-    xnew = ( q1*a1*x2 + q2*a2*x1 ) % qnew;
+    xnew = mod( q1*a1*x2 + q2*a2*x1, qnew );
 }
 //}}}
@@ -44 +46 @@
 // chineseRemainder - integer chinese remaindering.
 //
-// Calculate xnew such that xnew=x[i] (mod q[i]).  q[i] should be
-// integers, pairwise prime. x[i] should be integers.
+// Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the
+// product of all q[i].  q[i] should be positive integers,
+// pairwise prime.  x[i] should be polynomials with integer
+// coefficients.  If all coefficients of all x[i] are positive
+// integers, the result is guaranteed to have positive
+// coefficients, too.
 //
 // Note: be sure you are calculating in Z, and not in Q!
 //
 //}}}
-void chineseRemainder( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
+void
+chineseRemainder( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
 {
     ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
     CFArray X(x), Q(q);
     int i, j, n = x.size();
-    // we use a divide-and-conquer algorithm to reduce the number
-    // of remainderings
+
     while ( n != 1 ) {
         i = j = x.min();