source: git/factory/fac_distrib.cc @ 753fb61

spielwiese
Last change on this file since 753fb61 was 362fc67, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: remove $Id$
  • Property mode set to 100644
File size: 5.6 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3#include "config.h"
4
5#include "cf_assert.h"
6#include "debug.h"
7
8#include "cf_defs.h"
9#include "canonicalform.h"
10#include "cf_algorithm.h"
11#include "cf_iter.h"
12#include "fac_util.h"
13
14bool
15nonDivisors ( CanonicalForm omega, CanonicalForm delta, const CFArray & F, CFArray & d )
16{
17    DEBINCLEVEL( cerr, "nonDivisors" );
18    CanonicalForm q, r;
19    int k = F.size();
20    d = CFArray( 0, k );
21    d[0] = delta * omega;
22    for ( int i = 1; i <= k; i++ )
23    {
24        q = abs(F[i]);
25        for ( int j = i-1; j >= 0; j-- )
26        {
27            r = d[j];
28            do
29            {
30                r = gcd( r, q );
31                q = q / r;
32            } while ( !r.isOne() );
33            if ( q == 1 )
34            {
35                DEBDECLEVEL( cerr, "nonDivisors" );
36                return false;
37            }
38        }
39        d[i] = q;
40    }
41    DEBDECLEVEL( cerr, "nonDivisors" );
42    return true;
43}
44
45bool
46checkEvaluation ( const CanonicalForm & U, const CanonicalForm & lcU, const CanonicalForm & omega, const CFFList & F, const Evaluation & A, CanonicalForm & delta )
47{
48    CanonicalForm Vn, U0 = A( U );
49    CFFListIterator I;
50    int j;
51    CFArray FF = CFArray( 1, F.length() );
52    CFArray D;
53    Vn = A( lcU );
54    if ( Vn.isZero() )
55        return false;
56    delta = content( U0 );
57    for ( I = F, j = 1; I.hasItem(); I++, j++ )
58        FF[j] = A( I.getItem().factor() );
59    return nonDivisors( omega, delta, FF, D );
60}
61
62bool
63distributeLeadingCoeffs ( CanonicalForm & U, CFArray & G, CFArray & lcG, const CFFList & F, const CFArray & D, CanonicalForm & delta, CanonicalForm & omega, const Evaluation & A, int r )
64{
65    DEBINCLEVEL( cerr, "distributeLeadingCoeffs" );
66    CanonicalForm ut, gt, d, ft;
67    CanonicalForm dd, quot;
68    CFFListIterator I;
69    int m, j, i;
70    lcG = CFArray( 1, r );
71    for ( j = 1; j <= r; j ++ )
72        lcG[j] = 1;
73
74    for ( I = F, i = 1; I.hasItem(); I++, i++ )
75    {
76        ft = I.getItem().factor();
77        m = I.getItem().exp();
78        DEBOUTLN( cerr, "trying to distribute " << ft );
79        DEBOUTLN( cerr, "which is tested with " << D[i] );
80        DEBOUTLN( cerr, "and contained to the power of " << m );
81        j = 1;
82        while ( m > 0 && j <= r )
83        {
84            ut = lc( G[j] );
85            DEBOUTLN( cerr, "checking with " << ut );
86            while ( m > 0 && fdivides( D[i], ut, quot ) )
87            {
88                DEBOUTLN( cerr, "match found" );
89                m--; ut= quot;
90                lcG[j] *= ft;
91            }
92            j++;
93        }
94        if (m != 0)
95        {
96            DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
97            return false;
98        }
99    }
100    DEBOUTLN( cerr, "the leading coeffs before omega and delta correction: " << lcG );
101    if ( !omega.isOne() )
102    {
103        for ( j = 1; j <= r; j++ )
104        {
105//            G[j] *= omega;
106            lcG[j] *= omega;
107            if(lc( G[j] ).isZero()) return false;
108            G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
109        }
110        U *= power( omega, r-1 );
111    }
112    if ( !delta.isOne() )
113    {
114        for ( j = 1; j <= r; j++ )
115        {
116            lcG[j] *= delta;
117            if(lc( G[j] ).isZero()) return false;
118            G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
119        }
120        U *= power( delta, r );
121    }
122    DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
123    return true;
124}
125
126
127static void
128gfbAdjoin ( const CanonicalForm & F, CFList & L )
129{
130    if ( F.isOne() )
131        return;
132    if ( L.isEmpty() )
133    {
134        L.append( F );
135        return;
136    }
137    CanonicalForm h, quot, f = F;
138    CFListIterator i, j;
139    for ( i = L; i.hasItem() && ! f.isOne(); )
140    {
141        h = gcd( f, i.getItem() );
142        if ( h.isOne() )
143        {
144            i++;
145            continue;
146        }
147        while ( fdivides( h, f, quot ) )
148            f= quot;
149        CFList D( h );
150        gfbAdjoin( i.getItem() / h, D );
151        for ( j = D; j.hasItem(); j++ )
152            i.append( j.getItem() );
153        i.remove( true );
154    }
155    if ( ! f.isOne() )
156        L.append( f );
157}
158
159
160CFList
161gcdFreeBasis ( const CFList L )
162{
163    CFListIterator i;
164    CFList R;
165    for ( i = L; i.hasItem(); i++ )
166        gfbAdjoin( i.getItem(), R );
167    return R;
168}
169
170bool
171Univar2Bivar(const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
172{
173    CanonicalForm l = LC( U, Variable(1) );
174    int n = G.size();
175    CFArray lcG(1,n);
176    for ( int i = 1; i <= n; i++ )
177    {
178        G[i] *= A(l)/lc(G[i]);
179        lcG[i] = l;
180    }
181    return Hensel( U * power( l, n-1 ), G, lcG, A, bound, x );
182}
183
184bool
185Hensel2 ( const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
186{
187    int i,n = G.size(); // n is number of factors of U
188    CFArray TrueLcs(1, n);
189    for (i=1; i <= n; i++)
190        TrueLcs[i] = 1;
191    Variable y;
192    CanonicalForm lcU = LC ( U, Variable(1) );
193    while (! lcU.inCoeffDomain())
194    {
195        y = lcU.mvar(); // should make a more intelligent choice
196        CanonicalForm BivariateU = A ( U, 2, y.level() - 1 );
197        CFArray BivariateFactors = G;
198        CFArray lcFactors(1,n);
199        Univar2Bivar(BivariateU, BivariateFactors, A, bound, y);
200        for (i = 1; i <= n; i++)
201        {
202            BivariateFactors[i] /= content(BivariateFactors[i]);
203            lcFactors[i] = LC(BivariateFactors[i],Variable(1));
204        }
205//        GFB = GcdFreeBasis(lcFactors); // this is not right... should probably make everything squarefree
206//        Hensel2(lcU, GFB, A, bound, y);
207    }
208    for (i = 1; i <= n; i++)
209        G[i] *= A(TrueLcs[i])/lc(G[i]);
210    return Hensel(U, G, TrueLcs, A, bound, x);
211}
Note: See TracBrowser for help on using the repository browser.