Changeset 66e0d2 in git


Ignore:
Timestamp:
Jul 19, 1997, 10:13:16 AM (27 years ago)
Author:
Jens Schmidt <schmidt@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
1b73cc07cc26f967458468610090985974afb204
Parents:
e4eea0e6a7c23a276208a1ffe76b6d127f2e95e6
Message:
	* cf_chinese.cc (chineseRemainder): doc fix

	* cf_chinese.cc: doc fix


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

Legend:

Unmodified
Added
Removed

  • factory/cf_chinese.cc

    re4eea0e r66e0d2  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_chinese.cc,v 1.3 1997-06-19 12:27:25 schmidt Exp $ */
     2/* $Id: cf_chinese.cc,v 1.4 1997-07-19 08:13:16 schmidt Exp $ */
     3
     4//{{{ docu
     5//
     6// cf_chinese.cc - algorithms for chinese remaindering.
     7//
     8// Used by: cf_gcd.cc, cf_linsys.cc, sm_util.cc
     9//
     10//}}}
    311
    412#include <config.h>
    … …  
    917#include "canonicalform.h"
    1018
    11 
     19//{{{ void chineseRemainder( const CanonicalForm x1, const CanonicalForm q1, const CanonicalForm x2, const CanonicalForm q2, CanonicalForm & xnew, CanonicalForm & qnew )
     20//{{{ docu
     21//
     22// chineseRemainder - (simple) integer chinese remaindering.
     23//
     24// Calculate xnew such that xnew=x1 (mod q1) and xnew=x2
     25// (mod q2) and qnew = q1*q2.  q1 and q2 should be integers,
     26// pairwise prime, x1 and x2 should be integers.
     27//
     28// Note: be sure you are calculating in Z, and not in Q!
     29//
     30//}}}
    1231void chineseRemainder( const CanonicalForm x1, const CanonicalForm q1, const CanonicalForm x2, const CanonicalForm q2, CanonicalForm & xnew, CanonicalForm & qnew )
    1332{
    … …  
    1534    (void)iextgcd( q1, q2, a1, a2 );
    1635    qnew = q1 * q2;
     36    // xnew = mod( q1*a1*x2 + q2*a2*x1, qnew);
    1737    xnew = ( q1*a1*x2 + q2*a2*x1 ) % qnew;
    1838}
     39//}}}
    1940
     41//{{{ void chineseRemainder( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
     42//{{{ docu
     43//
     44// chineseRemainder - integer chinese remaindering.
     45//
     46// Calculate xnew such that xnew=x[i] (mod q[i]).  q[i] should be
     47// integers, pairwise prime. x[i] should be integers.
     48//
     49// Note: be sure you are calculating in Z, and not in Q!
     50//
     51//}}}
    2052void chineseRemainder( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
    2153{
    … …  
    2355    CFArray X(x), Q(q);
    2456    int i, j, n = x.size();
     57    // we use a divide-and-conquer algorithm to reduce the number
     58    // of remainderings
    2559    while ( n != 1 ) {
    2660        i = j = x.min();
    … …  
    3973    qnew = Q[q.min()];
    4074}
     75//}}}
Note: See TracChangeset for help on using the changeset viewer.