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