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