source: git/factory/cf_chinese.cc @ 8797746

spielwiese
Last change on this file since 8797746 was 362fc67, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: remove $Id$
  • Property mode set to 100644
File size: 6.6 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3//{{{ docu
4//
5// cf_chinese.cc - algorithms for chinese remaindering.
6//
7// Used by: cf_gcd.cc, cf_linsys.cc
8//
9// Header file: cf_algorithm.h
10//
11//}}}
12
13#include "config.h"
14
15#ifdef HAVE_NTL
16#include "NTLconvert.h"
17#endif
18
19#include "cf_assert.h"
20#include "debug.h"
21
22#include "canonicalform.h"
23#include "cf_iter.h"
24
25
26//{{{ void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
27//{{{ docu
28//
29// chineseRemainder - integer chinese remaindering.
30//
31// Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2)
32// and qnew = q1*q2.  q1 and q2 should be positive integers,
33// pairwise prime, x1 and x2 should be polynomials with integer
34// coefficients.  If x1 and x2 are polynomials with positive
35// coefficients, the result is guaranteed to have positive
36// coefficients, too.
37//
38// Note: This algorithm is optimized for the case q1>>q2.
39//
40// This is a standard algorithm.  See, for example,
41// Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra',
42// par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by
43// Homomorphic Images' in B. Buchberger - 'Computer Algebra -
44// Symbolic and Algebraic Computation'.
45//
46// Note: Be sure you are calculating in Z, and not in Q!
47//
48//}}}
49void
50chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
51{
52    DEBINCLEVEL( cerr, "chineseRemainder" );
53
54    DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
55    DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
56
57    // We calculate xnew as follows:
58    //     xnew = v1 + v2 * q1
59    // where
60    //     v1 = x1 (mod q1)
61    //     v2 = (x2-v1)/q1 (mod q2)  (*)
62    //
63    // We do one extra test to check whether x2-v1 vanishes (mod
64    // q2) in (*) since it is not costly and may save us
65    // from calculating the inverse of q1 (mod q2).
66    //
67    // u: v1 (mod q2)
68    // d: x2-v1 (mod q2)
69    // s: 1/q1 (mod q2)
70    //
71    CanonicalForm v2, v1;
72    CanonicalForm u, d, s, dummy;
73
74    v1 = mod( x1, q1 );
75    u = mod( v1, q2 );
76    d = mod( x2-u, q2 );
77    if ( d.isZero() )
78    {
79        xnew = v1;
80        qnew = q1 * q2;
81        DEBDECLEVEL( cerr, "chineseRemainder" );
82        return;
83    }
84    (void)bextgcd( q1, q2, s, dummy );
85    v2 = mod( d*s, q2 );
86    xnew = v1 + v2*q1;
87
88    // After all, calculate new modulus.  It is important that
89    // this is done at the very end of the algorithm, since q1
90    // and qnew may refer to the same object (same is true for x1
91    // and xnew).
92    qnew = q1 * q2;
93
94    DEBDECLEVEL( cerr, "chineseRemainder" );
95}
96//}}}
97
98//{{{ void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
99//{{{ docu
100//
101// chineseRemainder - integer chinese remaindering.
102//
103// Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the
104// product of all q[i].  q[i] should be positive integers,
105// pairwise prime.  x[i] should be polynomials with integer
106// coefficients.  If all coefficients of all x[i] are positive
107// integers, the result is guaranteed to have positive
108// coefficients, too.
109//
110// This is a standard algorithm, too, except for the fact that we
111// use a divide-and-conquer method instead of a linear approach
112// to calculate the remainder.
113//
114// Note: Be sure you are calculating in Z, and not in Q!
115//
116//}}}
117void
118chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
119{
120    DEBINCLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
121
122    ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
123    CFArray X(x), Q(q);
124    int i, j, n = x.size(), start = x.min();
125
126    DEBOUTLN( cerr, "array size = " << n );
127
128    while ( n != 1 )
129    {
130        i = j = start;
131        while ( i < start + n - 1 )
132        {
133            // This is a little bit dangerous: X[i] and X[j] (and
134            // Q[i] and Q[j]) may refer to the same object.  But
135            // xnew and qnew in the above function are modified
136            // at the very end of the function, so we do not
137            // modify x1 and q1, resp., by accident.
138            chineseRemainder( X[i], Q[i], X[i+1], Q[i+1], X[j], Q[j] );
139            i += 2;
140            j++;
141        }
142
143        if ( n & 1 )
144        {
145            X[j] = X[i];
146            Q[j] = Q[i];
147        }
148        // Maybe we would get some memory back at this point if
149        // we would set X[j+1, ..., n] and Q[j+1, ..., n] to zero
150        // at this point?
151
152        n = ( n + 1) / 2;
153    }
154    xnew = X[start];
155    qnew = Q[q.min()];
156
157    DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
158}
159//}}}
160
161CanonicalForm Farey_n (CanonicalForm N, const CanonicalForm P)
162//"USAGE:  Farey_n (N,P); P, N number;
163//RETURN:  a rational number a/b such that a/b=N mod P
164//         and |a|,|b|<(P/2)^{1/2}
165{
166   //assume(P>0);
167   // assume !isOn(SW_RATIONAL): mod is a no-op otherwise
168   if (N<0) N +=P;
169   CanonicalForm A,B,C,D,E;
170   E=P;
171   B=1;
172   while (!N.isZero())
173   {
174        if (2*N*N<P)
175        {
176           On(SW_RATIONAL);
177           N /=B;
178           Off(SW_RATIONAL);
179           return(N);
180        }
181        D=mod(E , N);
182        C=A-(E-mod(E , N))/N*B;
183        E=N;
184        N=D;
185        A=B;
186        B=C;
187   }
188   return(0);
189}
190
191CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q )
192{
193    int is_rat=isOn(SW_RATIONAL);
194    Off(SW_RATIONAL);
195    Variable x = f.mvar();
196    CanonicalForm result = 0;
197    CanonicalForm c;
198    CFIterator i;
199#ifdef HAVE_NTL
200    ZZ NTLq= convertFacCF2NTLZZ (q);
201    ZZ bound;
202    SqrRoot (bound, NTLq/2);
203#endif
204    for ( i = f; i.hasTerms(); i++ )
205    {
206        c = i.coeff();
207        if ( c.inCoeffDomain())
208        {
209#ifdef HAVE_NTL
210          if (c.inZ() && isOn (SW_USE_NTL))
211          {
212            ZZ NTLc= convertFacCF2NTLZZ (c);
213            bool lessZero= (sign (NTLc) == -1);
214            if (lessZero)
215              NTL::negate (NTLc, NTLc);
216            ZZ NTLnum, NTLden;
217            if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
218            {
219              if (lessZero)
220                NTL::negate (NTLnum, NTLnum);
221              CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
222              CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
223              On (SW_RATIONAL);
224              result += power (x, i.exp())*(num/den);
225              Off (SW_RATIONAL);
226            }
227          }
228          else
229#endif
230            result += power( x, i.exp() ) * Farey_n(c,q);
231        }
232        else
233          result += power( x, i.exp() ) * Farey(c,q);
234    }
235    if (is_rat) On(SW_RATIONAL);
236    return result;
237}
238
Note: See TracBrowser for help on using the repository browser.