001/*
002 * $Id: GCDHenselTest.java 4014 2012-07-22 07:00:47Z 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    //private final static int bitlen = 100;
060
061    GreatestCommonDivisorAbstract<BigInteger> ufd;
062
063
064    GreatestCommonDivisorAbstract<BigInteger> ufd1;
065
066
067    TermOrder to = new TermOrder(TermOrder.INVLEX);
068
069
070    GenPolynomialRing<BigInteger> dfac;
071
072
073    GenPolynomialRing<BigInteger> cfac;
074
075
076    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
077
078
079    //PrimeList primes = new PrimeList();
080
081    BigInteger cofac;
082
083
084    BigInteger ai;
085
086
087    BigInteger bi;
088
089
090    BigInteger ci;
091
092
093    BigInteger di;
094
095
096    BigInteger ei;
097
098
099    GenPolynomial<BigInteger> a;
100
101
102    GenPolynomial<BigInteger> b;
103
104
105    GenPolynomial<BigInteger> c;
106
107
108    GenPolynomial<BigInteger> d;
109
110
111    GenPolynomial<BigInteger> e;
112
113
114    GenPolynomial<BigInteger> ac;
115
116
117    GenPolynomial<BigInteger> bc;
118
119
120    GenPolynomial<GenPolynomial<BigInteger>> ar;
121
122
123    GenPolynomial<GenPolynomial<BigInteger>> br;
124
125
126    GenPolynomial<GenPolynomial<BigInteger>> cr;
127
128
129    GenPolynomial<GenPolynomial<BigInteger>> dr;
130
131
132    GenPolynomial<GenPolynomial<BigInteger>> er;
133
134
135    GenPolynomial<GenPolynomial<BigInteger>> arc;
136
137
138    GenPolynomial<GenPolynomial<BigInteger>> brc;
139
140
141    int rl = 3;
142
143
144    int kl = 4;
145
146
147    int ll = 5;
148
149
150    int el = 4; //3;
151
152
153    float q = 0.3f;
154
155
156    @Override
157    protected void setUp() {
158        a = b = c = d = e = null;
159        ai = bi = ci = di = ei = null;
160        ar = br = cr = dr = er = null;
161        cofac = new BigInteger();
162        ufd = new GreatestCommonDivisorHensel<ModInteger>();
163        dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
164        cfac = new GenPolynomialRing<BigInteger>(cofac, rl - 1, to);
165        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
166    }
167
168
169    @Override
170    protected void tearDown() {
171        a = b = c = d = e = null;
172        ai = bi = ci = di = ei = null;
173        ar = br = cr = dr = er = null;
174        ufd = null;
175        dfac = null;
176        cfac = null;
177        rfac = null;
178    }
179
180
181    /**
182     * Test univariate Hensel algorithm gcd with subres PRS recursive algorithm.
183     */
184    public void testHenselSubresGcd() {
185
186        GenPolynomial<BigInteger> a;
187        GenPolynomial<BigInteger> b;
188        GenPolynomial<BigInteger> c;
189        GenPolynomial<BigInteger> d;
190        GenPolynomial<BigInteger> e;
191
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
202            if (a.isZERO() || b.isZERO() || c.isZERO()) {
203                // skip for this turn
204                continue;
205            }
206            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
207            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
208            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
209
210            //System.out.println("a  = " + a);
211            //System.out.println("b  = " + b);
212            //System.out.println("c  = " + c);
213
214            a = a.multiply(c); //.multiply(c);
215            b = b.multiply(c);
216
217            //System.out.println("a c = " + a);
218            //System.out.println("b c = " + b);
219
220            d = ufd.gcd(a, b);
221            //d = ufd.baseGcd(a,b);
222
223            c = ufd.basePrimitivePart(c).abs();
224            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
225            //System.out.println("c  = " + c);
226            //System.out.println("d  = " + d);
227            //System.out.println("e  = " + e);
228
229            assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
230
231            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
232            //System.out.println("e  = " + e);
233            assertTrue("gcd(a,b) | a: " + e, e.isZERO());
234
235            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
236            //System.out.println("e  = " + e);
237            assertTrue("gcd(a,b) | b: " + e, e.isZERO());
238        }
239    }
240
241
242    /**
243     * Test univariate linear Hensel algorithm gcd with subres PRS recursive
244     * algorithm.
245     */
246    public void testHenselLinearSubresGcd() {
247
248        ufd1 = new GreatestCommonDivisorHensel<ModInteger>(false);
249
250        GenPolynomial<BigInteger> a;
251        GenPolynomial<BigInteger> b;
252        GenPolynomial<BigInteger> c;
253        GenPolynomial<BigInteger> d;
254        GenPolynomial<BigInteger> e;
255
256        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
257
258        for (int i = 0; i < 1; i++) {
259            a = dfac.random(kl, ll + i, el + i, q);
260            b = dfac.random(kl, ll + i, el + i, q);
261            c = dfac.random(kl, ll + i, el + i, q);
262            c = c.multiply(dfac.univariate(0));
263            //a = ufd.basePrimitivePart(a);
264            //b = ufd.basePrimitivePart(b);
265
266            if (a.isZERO() || b.isZERO() || c.isZERO()) {
267                // skip for this turn
268                continue;
269            }
270            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
271            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
272            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
273
274            //System.out.println("a  = " + a);
275            //System.out.println("b  = " + b);
276            //System.out.println("c  = " + c);
277
278            a = a.multiply(c); //.multiply(c);
279            b = b.multiply(c);
280
281            //System.out.println("a c = " + a);
282            //System.out.println("b c = " + b);
283
284            long t = System.currentTimeMillis();
285            d = ufd1.gcd(a, b);
286            t = System.currentTimeMillis() - t;
287            //d = ufd.baseGcd(a,b);
288
289            long tq = System.currentTimeMillis();
290            //e = ufd.gcd(a,b);
291            tq = System.currentTimeMillis() - tq;
292
293
294            //System.out.println("Hensel quadratic, time = " + tq);
295            //System.out.println("Hensel linear, time    = " + t);
296
297            c = ufd.basePrimitivePart(c).abs();
298            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
299            //System.out.println("c  = " + c);
300            //System.out.println("d  = " + d);
301            //System.out.println("e  = " + e);
302
303            assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
304
305            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
306            //System.out.println("e  = " + e);
307            assertTrue("gcd(a,b) | a: " + e, e.isZERO());
308
309            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
310            //System.out.println("e  = " + e);
311            assertTrue("gcd(a,b) | b: " + e, e.isZERO());
312        }
313    }
314
315
316    /**
317     * Test Hensel gcd 3 variables.
318     * 
319     */
320    public void testHenselGCD3() {
321        BigInteger ifa = new BigInteger(1);
322        //dfac = new GenPolynomialRing<BigInteger>(ifa, 2, to , new String[] {"x", "y" });
323        dfac = new GenPolynomialRing<BigInteger>(ifa, 3, to , new String[] { "x" , "y", "z" });
324
325        for (int i = 0; i < 1; i++) {
326            a = dfac.random(kl, ll, el + i, q);
327            b = dfac.random(kl, ll, el, q);
328            c = dfac.random(kl, ll, el, q);
329            // make monic and c with univariate head term
330            ExpVector ev = a.leadingExpVector();
331            if ( ev != null ) {
332                a.doPutToMap(ev,ifa.getONE());
333            }
334            ev = b.leadingExpVector();
335            if ( ev != null ) {
336                b.doPutToMap(ev,ifa.getONE());
337            }
338            ev = c.leadingExpVector();
339            if ( ev != null ) {
340                c.doPutToMap(ev,ifa.getONE());
341            }
342            assertFalse("ev == null ", ev == null);
343            if ( ev.dependencyOnVariables().length > 1 ) {
344                c = dfac.univariate(1); //getONE();
345            }
346            //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 ");
347            //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 ");
348            //a = dfac.parse(" x + 2 y + z^2 + 5 ");
349            //b = dfac.parse(" x - y - 3 + y z ");
350            //c = dfac.parse(" x y + z^2 + y ");
351            //System.out.println("a = " + a);
352            //System.out.println("b = " + b);
353            //System.out.println("c = " + c);
354
355            if (a.isZERO() || b.isZERO() || c.isZERO()) {
356                // skip for this turn
357                continue;
358            }
359            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
360
361            a = a.multiply(c);
362            b = b.multiply(c);
363            //System.out.println("a = " + a);
364            //System.out.println("b = " + b);
365
366            d = ufd.gcd(a, b);
367            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
368            //System.out.println("e = " + e);
369            //System.out.println("d = " + d);
370            //System.out.println("c = " + c);
371            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
372        }
373    }
374
375}