001/*
002 * $Id: PolyUfdUtilTest.java 4020 2012-07-22 19:19:51Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import junit.framework.Test;
009import junit.framework.TestCase;
010import junit.framework.TestSuite;
011
012import edu.jas.arith.BigInteger;
013import edu.jas.arith.BigRational;
014
015import edu.jas.kern.ComputerThreads;
016
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.TermOrder;
020import edu.jas.poly.PolyUtil;
021
022
023/**
024 * PolyUfdUtil tests with JUnit.
025 * @author Heinz Kredel.
026 */
027
028public class PolyUfdUtilTest extends TestCase {
029
030
031    /**
032     * main.
033     */
034    public static void main(String[] args) {
035        //BasicConfigurator.configure();
036        junit.textui.TestRunner.run(suite());
037        ComputerThreads.terminate();
038    }
039
040
041    /**
042     * Constructs a <CODE>PolyUtilTest</CODE> object.
043     * @param name String.
044     */
045    public PolyUfdUtilTest(String name) {
046        super(name);
047    }
048
049
050    /**
051     */
052    public static Test suite() {
053        TestSuite suite = new TestSuite(PolyUfdUtilTest.class);
054        return suite;
055    }
056
057
058    //private final static int bitlen = 100;
059
060    TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063    GenPolynomialRing<BigInteger> dfac;
064
065
066    GenPolynomialRing<BigInteger> cfac;
067
068
069    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
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<GenPolynomial<BigInteger>> ar;
103
104
105    GenPolynomial<GenPolynomial<BigInteger>> br;
106
107
108    GenPolynomial<GenPolynomial<BigInteger>> cr;
109
110
111    GenPolynomial<GenPolynomial<BigInteger>> dr;
112
113
114    GenPolynomial<GenPolynomial<BigInteger>> er;
115
116
117    int rl = 5;
118
119
120    int kl = 5;
121
122
123    int ll = 5;
124
125
126    int el = 3;
127
128
129    float q = 0.3f;
130
131
132    @Override
133    protected void setUp() {
134        a = b = c = d = e = null;
135        ai = bi = ci = di = ei = null;
136        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
137        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
138        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
139    }
140
141
142    @Override
143    protected void tearDown() {
144        a = b = c = d = e = null;
145        ai = bi = ci = di = ei = null;
146        dfac = null;
147        cfac = null;
148        rfac = null;
149        ComputerThreads.terminate();
150    }
151
152
153    protected static java.math.BigInteger getPrime1() {
154        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
155        for (int i = 1; i < 60; i++) {
156            prime *= 2;
157        }
158        prime -= 93;
159        //prime = 37;
160        //System.out.println("p1 = " + prime);
161        return new java.math.BigInteger("" + prime);
162    }
163
164
165    protected static java.math.BigInteger getPrime2() {
166        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
167        for (int i = 1; i < 30; i++) {
168            prime *= 2;
169        }
170        prime -= 35;
171        //prime = 19;
172        //System.out.println("p1 = " + prime);
173        return new java.math.BigInteger("" + prime);
174    }
175
176
177    /**
178     * Test Kronecker substitution.
179     */
180    public void testKroneckerSubstitution() {
181
182        for (int i = 0; i < 10; i++) {
183            a = dfac.random(kl, ll * 2, el * 5, q);
184            long d = a.degree() + 1L;
185            //System.out.println("\na        = " + a);
186            //System.out.println("deg(a)+1 = " + d);
187
188            b = PolyUfdUtil.<BigInteger> substituteKronecker(a, d);
189            //System.out.println("b        = " + b);
190
191            c = PolyUfdUtil.<BigInteger> backSubstituteKronecker(dfac, b, d);
192            //System.out.println("c        = " + c);
193            e = a.subtract(c);
194            //System.out.println("e        = " + e);
195            assertTrue("back(subst(a)) = a", e.isZERO());
196        }
197    }
198
199
200    /**
201     * Test recursive dense pseudo division.
202     */
203    public void testRecursivePseudoDivisionDense() {
204        String[] cnames = new String[] { "x" };
205        String[] mnames = new String[] { "t" };
206        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,cnames);
207        //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
208        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames);
209        QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac);
210        GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,rfac);
211        //System.out.println("\ndfac  = " + dfac);
212        //System.out.println("rdfac = " + rdfac);
213        //System.out.println("rfac  = " + rfac);
214        //System.out.println("qfac  = " + qfac);
215        //System.out.println("rqfac = " + rqfac);
216
217        ar = rfac.random(kl, 2*ll, el+4, q);
218        //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6  ) t^3 + ( 2 x - 8  ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13  ) ");
219        br = rfac.random(kl, 2*ll, el+2, q);
220        //ar = ar.multiply(br);
221        //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6  ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21  ) ");
222        //System.out.println("ar   = " + ar);
223        //System.out.println("br   = " + br);
224
225        dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br);
226        //System.out.println("qr   = " + dr);
227        cr = PolyUtil.<BigInteger> recursiveDensePseudoRemainder(ar, br);
228        //System.out.println("rr   = " + cr);
229
230        //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr);
231        //System.out.println("assertTrue lc^n a = q b + r: " + t);
232        //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true
233
234        GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,ar);
235        GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,br);
236        GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,cr);
237        GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,dr);
238        //System.out.println("ap  = " + ap);
239        //System.out.println("bp  = " + bp);
240        //System.out.println("cp  = " + cp);
241        ////System.out.println("dp  = " + dp);
242        //System.out.println("dp  = " + dp.monic());
243
244        GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp);
245        GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp);
246        ////System.out.println("qp  = " + qp);
247        //System.out.println("qp  = " + qp.monic());
248        //System.out.println("rp  = " + rp);
249        GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp);
250        //System.out.println("qp bp + rp  = " + rhs);
251
252        assertEquals("ap = qp bp + rp: ", ap, rhs);
253
254        assertEquals("cp = rp: ", rp.monic(), cp.monic() );
255        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
256        assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ??
257    }
258
259
260    /**
261     * Test recursive sparse pseudo division.
262     */
263    public void testRecursivePseudoDivisionSparse() {
264        String[] cnames = new String[] { "x" };
265        String[] mnames = new String[] { "t" };
266        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,cnames);
267        //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
268        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames);
269        QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac);
270        GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,rfac);
271        //System.out.println("\ndfac  = " + dfac);
272        //System.out.println("rdfac = " + rdfac);
273        //System.out.println("rfac  = " + rfac);
274        //System.out.println("qfac  = " + qfac);
275        //System.out.println("rqfac = " + rqfac);
276
277        ar = rfac.random(kl, 2*ll, el+4, q);
278        //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6  ) t^3 + ( 2 x - 8  ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13  ) ");
279        br = rfac.random(kl, 2*ll, el+2, q);
280        //ar = ar.multiply(br);
281        //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6  ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21  ) ");
282        //System.out.println("ar   = " + ar);
283        //System.out.println("br   = " + br);
284
285        dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br);
286        //System.out.println("qr   = " + dr);
287        cr = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, br);
288        //System.out.println("rr   = " + cr);
289
290        //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr);
291        //System.out.println("assertTrue lc^n a = q b + r: " + t);
292        //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true
293
294        GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,ar);
295        GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,br);
296        GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,cr);
297        GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,dr);
298        //System.out.println("ap  = " + ap);
299        //System.out.println("bp  = " + bp);
300        //System.out.println("cp  = " + cp);
301        ////System.out.println("dp  = " + dp);
302        //System.out.println("dp  = " + dp.monic());
303
304        GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp);
305        GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp);
306        ////System.out.println("qp  = " + qp);
307        //System.out.println("qp  = " + qp.monic());
308        //System.out.println("rp  = " + rp);
309        GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp);
310        //System.out.println("qp bp + rp  = " + rhs);
311
312        assertEquals("ap = qp bp + rp: ", ap, rhs);
313
314        assertEquals("cp = rp: ", rp.monic(), cp.monic() );
315        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
316        assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ??
317    }
318
319}