source: git/factory/fac_distrib.cc @ 050d1b

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