001/*
002 * $Id: GCDHenselTest.java 4377 2013-04-26 15:21:21Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008//import java.util.Map;
009
010import org.apache.log4j.BasicConfigurator;
011
012import junit.framework.Test;
013import junit.framework.TestCase;
014import junit.framework.TestSuite;
015
016import edu.jas.arith.BigInteger;
017import edu.jas.arith.ModInteger;
018import edu.jas.poly.ExpVector;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.poly.PolyUtil;
022import edu.jas.poly.TermOrder;
023
024
025/**
026 * GCD Hensel algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030public class GCDHenselTest extends TestCase {
031
032
033    /**
034     * main.
035     */
036    public static void main(String[] args) {
037        BasicConfigurator.configure();
038        junit.textui.TestRunner.run(suite());
039    }
040
041
042    /**
043     * Constructs a <CODE>GCDHenselTest</CODE> object.
044     * @param name String.
045     */
046    public GCDHenselTest(String name) {
047        super(name);
048    }
049
050
051    /**
052     */
053    public static Test suite() {
054        TestSuite suite = new TestSuite(GCDHenselTest.class);
055        return suite;
056    }
057
058
059    GreatestCommonDivisorAbstract<BigInteger> ufd;
060
061
062    GreatestCommonDivisorAbstract<BigInteger> ufd1;
063
064
065    TermOrder to = new TermOrder(TermOrder.INVLEX);
066
067
068    GenPolynomialRing<BigInteger> dfac;
069
070
071    BigInteger cofac;
072
073
074    BigInteger ai;
075
076
077    BigInteger bi;
078
079
080    BigInteger ci;
081
082
083    BigInteger di;
084
085
086    BigInteger ei;
087
088
089    GenPolynomial<BigInteger> a;
090
091
092    GenPolynomial<BigInteger> b;
093
094
095    GenPolynomial<BigInteger> c;
096
097
098    GenPolynomial<BigInteger> d;
099
100
101    GenPolynomial<BigInteger> e;
102
103
104    GenPolynomial<BigInteger> ac;
105
106
107    GenPolynomial<BigInteger> bc;
108
109
110    GenPolynomial<GenPolynomial<BigInteger>> ar;
111
112
113    GenPolynomial<GenPolynomial<BigInteger>> br;
114
115
116    GenPolynomial<GenPolynomial<BigInteger>> cr;
117
118
119    GenPolynomial<GenPolynomial<BigInteger>> dr;
120
121
122    GenPolynomial<GenPolynomial<BigInteger>> er;
123
124
125    GenPolynomial<GenPolynomial<BigInteger>> arc;
126
127
128    GenPolynomial<GenPolynomial<BigInteger>> brc;
129
130
131    int rl = 3;
132    String [] vars = { "x", "y", "z" }; 
133
134
135    int kl = 4;
136
137
138    int ll = 5;
139
140
141    int el = 4; //3;
142
143
144    float q = 0.3f;
145
146
147    @Override
148    protected void setUp() {
149        a = b = c = d = e = null;
150        ai = bi = ci = di = ei = null;
151        ar = br = cr = dr = er = null;
152        cofac = new BigInteger();
153        ufd = new GreatestCommonDivisorHensel<ModInteger>();
154        dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to, vars);
155    }
156
157
158    @Override
159    protected void tearDown() {
160        a = b = c = d = e = null;
161        ai = bi = ci = di = ei = null;
162        ar = br = cr = dr = er = null;
163        ufd = null;
164        dfac = null;
165    }
166
167
168    /**
169     * Test Hensel algorithm gcd.
170     */
171    public void testHenselGcd() {
172        //GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
173        for (int i = 0; i < 1; i++) {
174            a = dfac.random(kl, ll + i, el + i, q);
175            b = dfac.random(kl, ll + i, el + i, q);
176            c = dfac.random(kl, ll + i, el + i, q);
177            c = c.multiply(dfac.univariate(0));
178            //a = ufd.basePrimitivePart(a);
179            //b = ufd.basePrimitivePart(b);
180            ExpVector ev = c.leadingExpVector();
181            if ( ev != null ) {
182                c.doPutToMap(ev,dfac.coFac.getONE());
183            }
184
185            if (a.isZERO() || b.isZERO() || c.isZERO()) {
186                // skip for this turn
187                continue;
188            }
189            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
190            //System.out.println("a  = " + a);
191            //System.out.println("b  = " + b);
192            //System.out.println("c  = " + c);
193
194            a = a.multiply(c); //.multiply(c);
195            b = b.multiply(c);
196            //System.out.println("a c = " + a);
197            //System.out.println("b c = " + b);
198
199            d = ufd.gcd(a, b);
200            //d = ufd.baseGcd(a,b);
201
202            c = ufd.basePrimitivePart(c).abs();
203            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
204            //System.out.println("c  = " + c);
205            //System.out.println("d  = " + d);
206            //System.out.println("e  = " + e);
207            assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
208
209            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
210            //System.out.println("e  = " + e);
211            assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO());
212
213            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
214            //System.out.println("e  = " + e);
215            assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO());
216        }
217    }
218
219
220    /**
221     * Test linear Hensel algorithm gcd.
222     */
223    public void ytestHenselLinearSubresGcd() {
224        ufd1 = new GreatestCommonDivisorHensel<ModInteger>(false);
225        //GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
226
227        for (int i = 0; i < 1; i++) {
228            a = dfac.random(kl, ll + i, el + i, q);
229            b = dfac.random(kl, ll + i, el + i, q);
230            c = dfac.random(kl, ll + i, el + i, q);
231            c = c.multiply(dfac.univariate(0));
232            //a = ufd.basePrimitivePart(a);
233            //b = ufd.basePrimitivePart(b);
234            ExpVector ev = c.leadingExpVector();
235            if ( ev != null ) {
236                c.doPutToMap(ev,dfac.coFac.getONE());
237            }
238
239            if (a.isZERO() || b.isZERO() || c.isZERO()) {
240                // skip for this turn
241                continue;
242            }
243            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
244            //System.out.println("a  = " + a);
245            //System.out.println("b  = " + b);
246            //System.out.println("c  = " + c);
247
248            a = a.multiply(c); //.multiply(c);
249            b = b.multiply(c);
250            //System.out.println("a c = " + a);
251            //System.out.println("b c = " + b);
252
253            long t = System.currentTimeMillis();
254            d = ufd1.gcd(a, b);
255            t = System.currentTimeMillis() - t;
256            //d = ufd.baseGcd(a,b);
257
258            long tq = System.currentTimeMillis();
259            e = ufd.gcd(a,b);
260            tq = System.currentTimeMillis() - tq;
261            //System.out.println("Hensel quadratic, time = " + tq);
262            //System.out.println("Hensel linear, time    = " + t);
263
264            c = ufd.basePrimitivePart(c).abs();
265            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
266            //System.out.println("c  = " + c);
267            //System.out.println("d  = " + d);
268            //System.out.println("e  = " + e);
269            assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
270
271            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
272            //System.out.println("e  = " + e);
273            assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO());
274
275            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
276            //System.out.println("e  = " + e);
277            assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO());
278        }
279    }
280
281
282    /**
283     * Test Hensel gcd 3 variables.
284     */
285    public void testHenselGCD3() {
286        BigInteger ifa = new BigInteger(1);
287        //dfac = new GenPolynomialRing<BigInteger>(ifa, 2, to , new String[] {"x", "y" });
288        dfac = new GenPolynomialRing<BigInteger>(ifa, 3, to , new String[] { "x" , "y", "z" });
289
290        for (int i = 0; i < 1; i++) {
291            a = dfac.random(kl, ll, el + i, q);
292            b = dfac.random(kl, ll, el, q);
293            c = dfac.random(kl, ll, el, q);
294            // make monic and c with univariate head term
295            ExpVector ev = a.leadingExpVector();
296            if ( ev != null ) {
297                a.doPutToMap(ev,ifa.getONE());
298            }
299            ev = b.leadingExpVector();
300            if ( ev != null ) {
301                b.doPutToMap(ev,ifa.getONE());
302            }
303            ev = c.leadingExpVector();
304            if ( ev != null ) {
305                //c.doPutToMap(ev,ifa.getONE());
306            }
307            assertFalse("ev == null ", ev == null);
308            if ( ev.dependencyOnVariables().length > 1 ) {
309                c = dfac.univariate(1); //getONE();
310            }
311            //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 ");
312            //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 ");
313            //a = dfac.parse(" x + 2 y + z^2 + 5 ");
314            //b = dfac.parse(" x - y - 3 + y z ");
315            //c = dfac.parse(" x y + z^2 + y ");
316            //a = dfac.parse("7 y^4 - (35 x^3 - 32) y^3 - 160 x^3 y^2 + (105 x^2 - 119) y + (480 x^2 - 544) ");
317            //b = dfac.parse(" 7 y^4 + 39 y^3 + 32 y^2 ");
318            //c = dfac.parse(" 7 y + 32 ");
319
320            //a = dfac.parse(" ( -13 x^2 ) z^5 + ( 182 x^2 - 143  ) z^3 - ( x^2 * y^3 - 8 x^2 ) z^2 + ( 14 x^2 * y^3 - 11 y^3 - 112 x^2 + 88  ) ");
321            //b = dfac.parse(" ( -13 x^3 * y^3 ) z^6 + ( 65 y ) z^4 - ( x^3 * y^6 - 8 x^3 * y^3 - 52 y^3 - 195 y + 156  ) z^3 + ( 5 y^4 - 40 y ) z + ( 4 y^6 + 15 y^4 - 44 y^3 - 120 y + 96  ) ) ");
322            //c = dfac.parse(" 13 z^3 + y^3 - 8 ");
323
324            //a = dfac.parse(" 3 z^3 + ( 4 y^2 + 25 x^3 + 16 x^2 + 25  ) z^2 - ( 84 y^4 - 22 x^3 * y^2 + 128 x^2 * y^2 + 138 y^2 - 52 x^6 - 71 x^5 + 35 x^4 - 109 x^3 + 59 x^2 + 18  ) z ");
325            //b = dfac.parse(" 10 z^5 + ( 60 y^2 + 40 x^3 + 70 x^2 + 90  ) z^4 + ( 14 x + 3  ) z^2 + ( 84 x * y^2 + 18 y^2 + 56 x^4 + 110 x^3 + 21 x^2 + 126 x + 27  ) z ");
326            //c = dfac.parse("z^2 + ( 6 y^2 + 4 x^3 + 7 x^2 + 9  ) z");
327
328            //a = a.abs();
329            //b = b.abs();
330            //c = c.abs();
331            //System.out.println("a = " + a);
332            //System.out.println("b = " + b);
333            //System.out.println("c = " + c);
334            if (a.isZERO() || b.isZERO() || c.isZERO()) {
335                // skip for this turn
336                continue;
337            }
338
339            a = a.multiply(c);
340            b = b.multiply(c);
341            //System.out.println("a = " + a);
342            //System.out.println("b = " + b);
343
344            d = ufd.gcd(a, b);
345            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
346            //System.out.println("e = " + e);
347            //System.out.println("d = " + d);
348            //System.out.println("c = " + c);
349            assertTrue("c | gcd(ac,bc) " + e + ", d = " + d, e.isZERO());
350        }
351    }
352
353}