001/*
002 * $Id: PolyUfdUtilTest.java 5973 2019-04-14 11:03:45Z kredel $
003 */
004
005package edu.jas.ufd;
006
007import java.util.SortedMap;
008
009import edu.jas.arith.BigInteger;
010import edu.jas.arith.BigRational;
011import edu.jas.arith.ModLong;
012import edu.jas.arith.ModLongRing;
013import edu.jas.arith.ModInteger;
014import edu.jas.arith.ModIntegerRing;
015import edu.jas.kern.ComputerThreads;
016import edu.jas.poly.AlgebraicNumber;
017import edu.jas.poly.AlgebraicNumberRing;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.TermOrder;
022import edu.jas.poly.TermOrderByName;
023
024import junit.framework.Test;
025import junit.framework.TestCase;
026import junit.framework.TestSuite;
027
028
029/**
030 * PolyUfdUtil tests with JUnit.
031 * @author Heinz Kredel
032 */
033
034public class PolyUfdUtilTest extends TestCase {
035
036
037    /**
038     * main.
039     */
040    public static void main(String[] args) {
041        junit.textui.TestRunner.run(suite());
042        ComputerThreads.terminate();
043    }
044
045
046    /**
047     * Constructs a <CODE>PolyUtilTest</CODE> object.
048     * @param name String.
049     */
050    public PolyUfdUtilTest(String name) {
051        super(name);
052    }
053
054
055    /**
056     */
057    public static Test suite() {
058        TestSuite suite = new TestSuite(PolyUfdUtilTest.class);
059        return suite;
060    }
061
062
063    TermOrder to = TermOrderByName.INVLEX;
064
065
066    GenPolynomialRing<BigInteger> dfac;
067
068
069    GenPolynomialRing<BigInteger> cfac;
070
071
072    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
073
074
075    BigInteger ai, bi, ci, di, ei;
076
077
078    GenPolynomial<BigInteger> a, b, c, d, e;
079
080
081    GenPolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er;
082
083
084    GenPolynomialRing<BigRational> crfac;
085
086
087    GenPolynomialRing<GenPolynomial<BigRational>> rrfac;
088
089 
090    GenPolynomial<GenPolynomial<BigRational>> arr, brr, crr, drr, err, frr;
091
092
093    int rl = 5;
094
095
096    int kl = 5;
097
098
099    int ll = 5;
100
101
102    int el = 3;
103
104
105    float q = 0.3f;
106
107
108    @Override
109    protected void setUp() {
110        a = b = c = d = e = null;
111        ai = bi = ci = di = ei = null;
112        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
113        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
114        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
115    }
116
117
118    @Override
119    protected void tearDown() {
120        a = b = c = d = e = null;
121        ai = bi = ci = di = ei = null;
122        dfac = null;
123        cfac = null;
124        rfac = null;
125        ComputerThreads.terminate();
126    }
127
128
129    protected static java.math.BigInteger getPrime1() {
130        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
131        for (int i = 1; i < 60; i++) {
132            prime *= 2;
133        }
134        prime -= 93;
135        //prime = 37;
136        //System.out.println("p1 = " + prime);
137        return new java.math.BigInteger("" + prime);
138    }
139
140
141    protected static java.math.BigInteger getPrime2() {
142        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
143        for (int i = 1; i < 30; i++) {
144            prime *= 2;
145        }
146        prime -= 35;
147        //prime = 19;
148        //System.out.println("p1 = " + prime);
149        return new java.math.BigInteger("" + prime);
150    }
151
152
153    /**
154     * Test Kronecker substitution.
155     */
156    public void testKroneckerSubstitution() {
157        for (int i = 0; i < 10; i++) {
158            a = dfac.random(kl, ll * 2, el * 5, q);
159            long d = a.degree() + 1L;
160            //System.out.println("\na        = " + a);
161            //System.out.println("deg(a)+1 = " + d);
162
163            b = PolyUfdUtil.<BigInteger> substituteKronecker(a, d);
164            //System.out.println("b        = " + b);
165
166            c = PolyUfdUtil.<BigInteger> backSubstituteKronecker(dfac, b, d);
167            //System.out.println("c        = " + c);
168            e = a.subtract(c);
169            //System.out.println("e        = " + e);
170            assertTrue("back(subst(a)) = a", e.isZERO());
171        }
172    }
173
174
175    /**
176     * Test algebraic number field.
177     */
178    public void testAlgebraicNumberField() {
179        int deg = 11;
180        // characteristic non zero, small
181        ModLongRing gfp = new ModLongRing(32003);
182        //System.out.println("gfp = " + gfp.toScript());
183        AlgebraicNumberRing<ModLong> gfpq = PolyUfdUtil.<ModLong> algebraicNumberField(gfp, deg);
184        //System.out.println("gfpq = " + gfpq.toScript());
185        assertTrue("gfpq.isField: ", gfpq.isField());
186
187        // characteristic non zero, large
188        ModIntegerRing gfP = new ModIntegerRing(getPrime1());
189        //System.out.println("gfP = " + gfP.toScript());
190        AlgebraicNumberRing<ModInteger> gfPq = PolyUfdUtil.<ModInteger> algebraicNumberField(gfP, deg);
191        //System.out.println("gfPq = " + gfPq.toScript());
192        assertTrue("gfPq.isField: ", gfPq.isField());
193
194        // characteristic zero
195        BigRational q = BigRational.ONE;
196        //System.out.println("q = " + q.toScriptFactory());
197        AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg);
198        //System.out.println("gfqq = " + gfqq.toScript());
199        assertTrue("gfqq.isField: ", gfqq.isField());
200
201        //PolyUfdUtil.<BigRational> ensureFieldProperty(gfqq);
202        //System.out.println("gfqq = " + gfqq);
203        //assertTrue("gfqq.isField: ", gfqq.isField());
204    }
205
206
207    /**
208     * Test recursive dense pseudo division.
209     */
210    public void testRecursivePseudoDivisionDense() {
211        String[] cnames = new String[] { "x" };
212        String[] mnames = new String[] { "t" };
213        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, cnames);
214        //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
215        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames);
216        QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac);
217        GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,
218                                                                                                    rfac);
219        //System.out.println("\ndfac  = " + dfac);
220        //System.out.println("rdfac = " + rdfac);
221        //System.out.println("rfac  = " + rfac);
222        //System.out.println("qfac  = " + qfac);
223        //System.out.println("rqfac = " + rqfac);
224
225        ar = rfac.random(kl, 2 * ll, el + 4, q);
226        //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  ) ");
227        br = rfac.random(kl, 2 * ll, el + 2, q);
228        //ar = ar.multiply(br);
229        //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6  ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21  ) ");
230        //System.out.println("ar   = " + ar);
231        //System.out.println("br   = " + br);
232
233        dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br);
234        //System.out.println("qr   = " + dr);
235        cr = PolyUtil.<BigInteger> recursiveDensePseudoRemainder(ar, br);
236        //System.out.println("rr   = " + cr);
237
238        //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr);
239        //System.out.println("assertTrue lc^n a = q b + r: " + t);
240        //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true
241
242        GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil
243            .<BigInteger> quotientFromIntegralCoefficients(rqfac, ar);
244        GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil
245            .<BigInteger> quotientFromIntegralCoefficients(rqfac, br);
246        GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil
247            .<BigInteger> quotientFromIntegralCoefficients(rqfac, cr);
248        GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil
249            .<BigInteger> quotientFromIntegralCoefficients(rqfac, dr);
250        //System.out.println("ap  = " + ap);
251        //System.out.println("bp  = " + bp);
252        //System.out.println("cp  = " + cp);
253        ////System.out.println("dp  = " + dp);
254        //System.out.println("dp  = " + dp.monic());
255
256        GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp);
257        GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp);
258        ////System.out.println("qp  = " + qp);
259        //System.out.println("qp  = " + qp.monic());
260        //System.out.println("rp  = " + rp);
261        GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp);
262        //System.out.println("qp bp + rp  = " + rhs);
263
264        assertEquals("ap = qp bp + rp: ", ap, rhs);
265
266        assertEquals("cp = rp: ", rp.monic(), cp.monic());
267        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
268        assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ??
269    }
270
271
272    /**
273     * Test recursive sparse pseudo division.
274     */
275    public void testRecursivePseudoDivisionSparse() {
276        String[] cnames = new String[] { "x" };
277        String[] mnames = new String[] { "t" };
278        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, cnames);
279        //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
280        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames);
281        QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac);
282        GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,
283                                                                                                    rfac);
284        //System.out.println("\ndfac  = " + dfac);
285        //System.out.println("rdfac = " + rdfac);
286        //System.out.println("rfac  = " + rfac);
287        //System.out.println("qfac  = " + qfac);
288        //System.out.println("rqfac = " + rqfac);
289
290        ar = rfac.random(kl, 2 * ll, el + 4, q);
291        //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  ) ");
292        br = rfac.random(kl, 2 * ll, el + 2, q);
293        //ar = ar.multiply(br);
294        //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6  ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21  ) ");
295        //System.out.println("ar   = " + ar);
296        //System.out.println("br   = " + br);
297
298        dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br);
299        //System.out.println("qr   = " + dr);
300        cr = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, br);
301        //System.out.println("rr   = " + cr);
302
303        //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr);
304        //System.out.println("assertTrue lc^n a = q b + r: " + t);
305        //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true
306
307        GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil
308            .<BigInteger> quotientFromIntegralCoefficients(rqfac, ar);
309        GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil
310            .<BigInteger> quotientFromIntegralCoefficients(rqfac, br);
311        GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil
312            .<BigInteger> quotientFromIntegralCoefficients(rqfac, cr);
313        GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil
314            .<BigInteger> quotientFromIntegralCoefficients(rqfac, dr);
315        //System.out.println("ap  = " + ap);
316        //System.out.println("bp  = " + bp);
317        //System.out.println("cp  = " + cp);
318        ////System.out.println("dp  = " + dp);
319        //System.out.println("dp  = " + dp.monic());
320
321        GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp);
322        GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp);
323        ////System.out.println("qp  = " + qp);
324        //System.out.println("qp  = " + qp.monic());
325        //System.out.println("rp  = " + rp);
326        GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp);
327        //System.out.println("qp bp + rp  = " + rhs);
328
329        assertEquals("ap = qp bp + rp: ", ap, rhs);
330
331        assertEquals("cp = rp: ", rp.monic(), cp.monic());
332        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
333        assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ??
334    }
335
336
337    /**
338     * Test integer from rational coefficients, recursive.
339     */
340    public void testRecursiveIntegerFromRationalCoefficients() {
341        crfac = new GenPolynomialRing<BigRational>(new BigRational(1), cfac);
342        rrfac = new GenPolynomialRing<GenPolynomial<BigRational>>(crfac, rfac);
343        //System.out.println("\ncfac  = " + cfac);
344        //System.out.println("crfac = " + crfac);
345        //System.out.println("rfac  = " + rfac);
346        //System.out.println("rrfac  = " + rrfac);
347
348        // BigRational
349        arr = rrfac.random(kl*kl, 2 * ll, el + 4, q);
350        arr = arr.sum(arr).multiply(arr); //rrfac.fromInteger(11));
351        //System.out.println("arr   = " + arr);
352
353        // BigInteger
354        ar = PolyUfdUtil.integerFromRationalCoefficients(rfac, arr);
355        //System.out.println("ar   = " + ar);
356
357        crr = PolyUtil.<BigRational> monic(arr);
358        //System.out.println("crr   = " + crr);
359
360        // BigRational
361        err = PolyUfdUtil.<BigRational> fromIntegerCoefficients(rrfac, ar);
362        //System.out.println("err   = " + err);
363        err = PolyUtil.<BigRational> monic(err);
364        //System.out.println("err   = " + err);
365
366        assertEquals("crr != err: ", crr, err);
367    }
368
369
370    /**
371     * Test norm over algebraic number field.
372     */
373    public void testNormAlgebraicNumberField() {
374        int deg = 5;
375        // characteristic zero
376        BigRational q = BigRational.ONE;
377        //System.out.println("q = " + q.toScriptFactory());
378        AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg);
379        //System.out.println("gfqq = " + gfqq.toScript());
380        assertTrue("gfqq.isField: ", gfqq.isField());
381
382        GenPolynomialRing<AlgebraicNumber<BigRational>> pafac;
383        pafac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(gfqq, new String[] { "x" }, TermOrderByName.INVLEX);
384        //System.out.println("pafac = " + pafac.toScript());
385
386        GenPolynomial<AlgebraicNumber<BigRational>> P, Q, R;
387        P = pafac.random(2,4,3,0.4f).monic();
388        Q = pafac.random(2,4,3,0.4f).monic();
389        R = P.multiply(Q);
390        //System.out.println("P = " + P);
391        //System.out.println("Q = " + Q);
392        //System.out.println("R = " + R);
393
394        GenPolynomial<BigRational> nP, nQ, nR, nPQ, rem, gcd;
395        nP = PolyUfdUtil.<BigRational> norm(P);
396        nQ = PolyUfdUtil.<BigRational> norm(Q);
397        nR = PolyUfdUtil.<BigRational> norm(R);
398        nPQ = nP.multiply(nQ);
399        //System.out.println("normP  = " + nP);
400        //System.out.println("normQ  = " + nQ);
401        //System.out.println("normR  = " + nR);
402        //System.out.println("normPQ = " + nPQ);
403
404        //System.out.println("normP*normQ = norm(P*Q): " + nPQ.equals(nR) + "\n");
405        if (nPQ.equals(nR)) {
406            assertEquals("normP*normQ == norm(P*Q)", nPQ, nR);
407            return;
408        }
409        rem = nR.remainder(nPQ);
410        //System.out.println("norm(P*Q) mod normP*normQ == 0: " + rem.isZERO());
411        if (rem.isZERO()) {
412            assertTrue("norm(P*Q) mod normP*normQ == 0", rem.isZERO());
413            return;
414        }
415
416        GreatestCommonDivisorAbstract<BigRational> gcdr = GCDFactory.<BigRational>getImplementation(q);
417        gcd = gcdr.gcd(nPQ,nR);
418        //System.out.println("gcd(norm(P*Q), normP*normQ) != 1: " + (!gcd.isONE()));
419        if (!gcd.isONE()) {
420            assertFalse("gcd(norm(P*Q), normP*normQ) != 1", gcd.isONE());
421            return;
422        }
423        // unreachable:        
424        FactorAbstract<BigRational> facr = FactorFactory.<BigRational>getImplementation(q);
425        SortedMap<GenPolynomial<BigRational>,Long> fnPQ = facr.factors(nPQ);
426        System.out.println("fnPQ = " + fnPQ);
427        SortedMap<GenPolynomial<BigRational>,Long> fnR = facr.factors(nR);
428        System.out.println("fnR = " + fnR);
429    }
430
431    
432    /**
433     * Test multivariate norm over algebraic number field.
434     */
435    public void testMultiNormAlgebraicNumberField() {
436        int deg = 5;
437        // characteristic zero
438        BigRational q = BigRational.ONE;
439        //System.out.println("q = " + q.toScriptFactory());
440        AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg);
441        //System.out.println("gfqq = " + gfqq.toScript());
442        assertTrue("gfqq.isField: ", gfqq.isField());
443
444        GenPolynomialRing<AlgebraicNumber<BigRational>> pafac;
445        pafac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(gfqq, new String[] { "x", "y" }, TermOrderByName.INVLEX);
446        //System.out.println("pafac = " + pafac.toScript());
447
448        GenPolynomial<AlgebraicNumber<BigRational>> P, Q, R;
449        P = pafac.random(2,4,2,0.2f).monic();
450        Q = pafac.random(2,4,2,0.2f).monic();
451        R = P.multiply(Q);
452        //System.out.println("P = " + P);
453        //System.out.println("Q = " + Q);
454        //System.out.println("R = " + R);
455
456        GenPolynomial<BigRational> nP, nQ, nR, nPQ, rem, gcd;
457        nP = PolyUfdUtil.<BigRational> norm(P);
458        nQ = PolyUfdUtil.<BigRational> norm(Q);
459        nR = PolyUfdUtil.<BigRational> norm(R);
460        nPQ = nP.multiply(nQ);
461        //System.out.println("normP  = " + nP);
462        //System.out.println("normQ  = " + nQ);
463        //System.out.println("normR  = " + nR);
464        //System.out.println("normPQ = " + nPQ);
465
466        //System.out.println("normP*normQ == norm(P*Q): " + nPQ.equals(nR) + "\n");
467        if (nPQ.equals(nR)) {
468            assertEquals("normP*normQ == norm(P*Q)", nPQ, nR);
469            return;
470        }
471
472        rem = nR.remainder(nPQ);
473        //System.out.println("norm(P*Q) mod normP*normQ == 0: " + rem.isZERO());
474        if (rem.isZERO()) {
475            assertTrue("norm(P*Q) mod normP*normQ == 0", rem.isZERO());
476            return;
477        }
478
479        GreatestCommonDivisorAbstract<BigRational> gcdr = GCDFactory.<BigRational>getImplementation(q);
480        gcd = gcdr.gcd(nPQ,nR);
481        //System.out.println("gcd(norm(P*Q), normP*normQ) != 1: " + (!gcd.isONE()));
482        if (!gcd.isONE()) {
483            assertFalse("gcd(norm(P*Q), normP*normQ) != 1", gcd.isONE());
484            return;
485        }
486        // unreachable:        
487        FactorAbstract<BigRational> facr = FactorFactory.<BigRational>getImplementation(q);
488        SortedMap<GenPolynomial<BigRational>,Long> fnPQ = facr.factors(nPQ);
489        System.out.println("fnPQ = " + fnPQ);
490        SortedMap<GenPolynomial<BigRational>,Long> fnR = facr.factors(nR);
491        System.out.println("fnR = " + fnR);
492    }
493
494}