source: git/factory/fac_distrib.cc @ 564dd8

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