001/*
002 * $Id: Examples.java 5248 2015-05-11 20:00:14Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.BasicConfigurator;
012
013import edu.jas.arith.BigInteger;
014import edu.jas.arith.BigRational;
015import edu.jas.arith.ModInteger;
016import edu.jas.arith.ModIntegerRing;
017import edu.jas.kern.Scripting;
018
019
020/**
021 * Examples for polynomials usage.
022 * @author Heinz Kredel.
023 */
024
025public class Examples {
026
027
028    /**
029     * main.
030     */
031    public static void main(String[] args) {
032        BasicConfigurator.configure();
033        //example0();
034        /*
035          example1();
036          example2();
037          example3();
038          example4();
039          example5();
040        */
041        //example6(); 
042        example7();
043        example7();
044        //example8();
045        //example9();
046        //example10();
047        //example11();
048        //example12();
049        //example13();
050    }
051
052
053    /**
054     * example0. for PPPJ 2006.
055     */
056    public static void example0() {
057        BigInteger z = new BigInteger();
058
059        TermOrder to = new TermOrder();
060        String[] vars = new String[] { "x1", "x2", "x3" };
061        GenPolynomialRing<BigInteger> ring;
062        ring = new GenPolynomialRing<BigInteger>(z, 3, to, vars);
063        System.out.println("ring = " + ring);
064
065        GenPolynomial<BigInteger> pol;
066        pol = ring.parse("3 x1^2 x3^4 + 7 x2^5 - 61");
067        System.out.println("pol = " + pol);
068        System.out.println("pol = " + pol.toString(ring.getVars()));
069
070        GenPolynomial<BigInteger> one;
071        one = ring.parse("1");
072        System.out.println("one = " + one);
073        System.out.println("one = " + one.toString(ring.getVars()));
074
075        GenPolynomial<BigInteger> p;
076        p = pol.subtract(pol);
077        System.out.println("p = " + p);
078        System.out.println("p = " + p.toString(ring.getVars()));
079
080        p = pol.multiply(pol);
081        System.out.println("p = " + p);
082        System.out.println("p = " + p.toString(ring.getVars()));
083    }
084
085
086    /**
087     * example1. random polynomial with rational coefficients. Q[x_1,...x_7]
088     */
089    public static void example1() {
090        System.out.println("\n\n example 1");
091
092        BigRational cfac = new BigRational();
093        System.out.println("cfac = " + cfac);
094        GenPolynomialRing<BigRational> fac;
095        fac = new GenPolynomialRing<BigRational>(cfac, 7);
096        //System.out.println("fac = " + fac);
097        System.out.println("fac = " + fac);
098
099        GenPolynomial<BigRational> a = fac.random(10);
100        System.out.println("a = " + a);
101    }
102
103
104    /**
105     * example2. random polynomial with coefficients of rational polynomials.
106     * Q[x_1,...x_7][y_1,...,y_3]
107     */
108    public static void example2() {
109        System.out.println("\n\n example 2");
110
111        BigRational cfac = new BigRational();
112        System.out.println("cfac = " + cfac);
113        GenPolynomialRing<BigRational> fac;
114        fac = new GenPolynomialRing<BigRational>(cfac, 7);
115        System.out.println("fac = " + fac);
116
117        GenPolynomialRing<GenPolynomial<BigRational>> gfac;
118        gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac, 3);
119        System.out.println("gfac = " + gfac);
120
121        GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10);
122        System.out.println("a = " + a);
123    }
124
125
126    /**
127     * example3. random rational algebraic number. Q(alpha)
128     */
129    public static void example3() {
130        System.out.println("\n\n example 3");
131
132        BigRational cfac = new BigRational();
133        System.out.println("cfac = " + cfac);
134
135        GenPolynomialRing<BigRational> mfac;
136        mfac = new GenPolynomialRing<BigRational>(cfac, 1);
137        System.out.println("mfac = " + mfac);
138
139        GenPolynomial<BigRational> modul = mfac.random(8).monic();
140        // assume !mo.isUnit()
141        System.out.println("modul = " + modul);
142
143        AlgebraicNumberRing<BigRational> fac;
144        fac = new AlgebraicNumberRing<BigRational>(modul);
145        System.out.println("fac = " + fac);
146
147        AlgebraicNumber<BigRational> a = fac.random(15);
148        System.out.println("a = " + a);
149    }
150
151
152    protected static long getPrime() {
153        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
154        for (int i = 1; i < 60; i++) {
155            prime *= 2;
156        }
157        prime -= 93;
158        //System.out.println("prime = " + prime);
159        return prime;
160    }
161
162
163    /**
164     * example4. random modular algebraic number. Z_p(alpha)
165     */
166    public static void example4() {
167        System.out.println("\n\n example 4");
168
169        long prime = getPrime();
170        ModIntegerRing cfac = new ModIntegerRing(prime);
171        System.out.println("cfac = " + cfac);
172
173        GenPolynomialRing<ModInteger> mfac;
174        mfac = new GenPolynomialRing<ModInteger>(cfac, 1);
175        System.out.println("mfac = " + mfac);
176
177        GenPolynomial<ModInteger> modul = mfac.random(8).monic();
178        // assume !modul.isUnit()
179        System.out.println("modul = " + modul);
180
181        AlgebraicNumberRing<ModInteger> fac;
182        fac = new AlgebraicNumberRing<ModInteger>(modul);
183        System.out.println("fac = " + fac);
184
185        AlgebraicNumber<ModInteger> a = fac.random(12);
186        System.out.println("a = " + a);
187    }
188
189
190    /**
191     * example5. random solvable polynomial with rational coefficients.
192     * Q{x_1,...x_6, {x_2 * x_1 = x_1 x_2 +1, ...} }
193     */
194    public static void example5() {
195        System.out.println("\n\n example 5");
196
197        BigRational cfac = new BigRational();
198        System.out.println("cfac = " + cfac);
199        GenSolvablePolynomialRing<BigRational> sfac;
200        sfac = new GenSolvablePolynomialRing<BigRational>(cfac, 6);
201        //System.out.println("sfac = " + sfac);
202
203        RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
204        //wl.generate(sfac);
205        sfac.addRelations(wl);
206        System.out.println("sfac = " + sfac);
207
208        GenSolvablePolynomial<BigRational> a = sfac.random(5);
209        System.out.println("a = " + a);
210        System.out.println("a = " + a.toString(sfac.vars));
211
212        GenSolvablePolynomial<BigRational> b = a.multiply(a);
213        System.out.println("b = " + b);
214        System.out.println("b = " + b.toString(sfac.vars));
215
216        System.out.println("sfac = " + sfac);
217    }
218
219
220    /**
221     * example6. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Z[z,y,x]
222     */
223    public static void example6() {
224        System.out.println("\n\n example 6");
225
226        BigInteger cfac = new BigInteger();
227        System.out.println("cfac = " + cfac);
228
229        TermOrder to = new TermOrder(TermOrder.INVLEX);
230        System.out.println("to   = " + to);
231
232        GenPolynomialRing<BigInteger> fac;
233        fac = new GenPolynomialRing<BigInteger>(cfac, 3, to);
234        System.out.println("fac = " + fac);
235        fac.setVars(new String[] { "z", "y", "x" });
236        System.out.println("fac = " + fac);
237
238        GenPolynomial<BigInteger> x = fac.univariate(0);
239        GenPolynomial<BigInteger> y = fac.univariate(1);
240        GenPolynomial<BigInteger> z = fac.univariate(2);
241
242        System.out.println("x = " + x);
243        System.out.println("x = " + x.toString(fac.vars));
244        System.out.println("y = " + y);
245        System.out.println("y = " + y.toString(fac.vars));
246        System.out.println("z = " + z);
247        System.out.println("z = " + z.toString(fac.vars));
248
249        GenPolynomial<BigInteger> p = x.sum(y).sum(z).sum(fac.getONE());
250        //BigInteger f = cfac.fromInteger(10000000001L);
251        // p = p.multiply( f );
252        System.out.println("p = " + p);
253        System.out.println("p = " + p.toString(fac.vars));
254
255        GenPolynomial<BigInteger> q = p;
256        for (int i = 1; i < 20; i++) {
257            q = q.multiply(p);
258        }
259        //System.out.println("q = " + q.toString( fac.vars ) );
260        System.out.println("q = " + q.length());
261
262        GenPolynomial<BigInteger> q1 = q.sum(fac.getONE());
263
264        GenPolynomial<BigInteger> q2;
265        long t = System.currentTimeMillis();
266        q2 = q.multiply(q1);
267        t = System.currentTimeMillis() - t;
268
269        System.out.println("q2 = " + q2.length());
270        System.out.println("time = " + t + " ms");
271    }
272
273
274    /**
275     * example7. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Q[z,y,x]
276     */
277    public static void example7() {
278        System.out.println("\n\n example 7");
279
280        BigRational cfac = new BigRational();
281        System.out.println("cfac = " + cfac);
282
283        TermOrder to = new TermOrder(TermOrder.INVLEX);
284        System.out.println("to   = " + to);
285
286        GenPolynomialRing<BigRational> fac;
287        fac = new GenPolynomialRing<BigRational>(cfac, 3, to);
288        System.out.println("fac = " + fac);
289        fac.setVars(new String[] { "z", "y", "x" });
290        System.out.println("fac = " + fac);
291
292        long mi = 1L;
293        //long mi = Integer.MAX_VALUE;
294        GenPolynomial<BigRational> x = fac.univariate(0, mi);
295        GenPolynomial<BigRational> y = fac.univariate(1, mi);
296        GenPolynomial<BigRational> z = fac.univariate(2, mi);
297
298        // System.out.println("x = " + x);
299        System.out.println("x = " + x.toString(fac.vars));
300        // System.out.println("y = " + y);
301        System.out.println("y = " + y.toString(fac.vars));
302        // System.out.println("z = " + z);
303        System.out.println("z = " + z.toString(fac.vars));
304
305        GenPolynomial<BigRational> p = x.sum(y).sum(z).sum(fac.getONE());
306        //BigRational f = cfac.fromInteger(10000000001L);
307        // f = f.multiply( f );
308        //p = p.multiply( f );
309        // System.out.println("p = " + p);
310        System.out.println("p = " + p.toString(fac.vars));
311
312        int mpow = 20;
313        System.out.println("mpow = " + mpow);
314        GenPolynomial<BigRational> q = p;
315        for (int i = 1; i < mpow; i++) {
316            q = q.multiply(p);
317        }
318        //System.out.println("q = " + q.toString( fac.vars ) );
319        System.out.println("len(q) = " + q.length());
320        System.out.println("deg(q) = " + q.degree());
321
322        GenPolynomial<BigRational> q1 = q.sum(fac.getONE());
323
324        GenPolynomial<BigRational> q2;
325        long t = System.currentTimeMillis();
326        q2 = q.multiply(q1);
327        t = System.currentTimeMillis() - t;
328
329        System.out.println("len(q2)    = " + q2.length());
330        System.out.println("deg(q2)    = " + q2.degree());
331        System.out.println("LeadEV(q2) = " + q2.leadingExpVector());
332        System.out.println("time       = " + t + " ms");
333    }
334
335
336    /**
337     * example8. Chebyshev polynomials
338     * 
339     * T(0) = 1 T(1) = x T(n) = 2x * T(n-1) - T(n-2)
340     */
341    public static void example8() {
342        int m = 10;
343        BigInteger fac = new BigInteger();
344        String[] var = new String[] { "x" };
345
346        GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var);
347
348        List<GenPolynomial<BigInteger>> T = new ArrayList<GenPolynomial<BigInteger>>(m);
349
350        GenPolynomial<BigInteger> t, one, x, x2, x2b;
351
352        one = ring.getONE();
353        x = ring.univariate(0);
354        //x2  = ring.parse("2 x");
355        //x2a = x.multiply( fac.fromInteger(2) );
356        x2b = x.multiply(new BigInteger(2));
357        x2 = x2b;
358
359        T.add(one);
360        T.add(x);
361        for (int n = 2; n < m; n++) {
362            t = x2.multiply(T.get(n - 1)).subtract(T.get(n - 2));
363            T.add(t);
364        }
365        for (int n = 0 /*m-2*/; n < m; n++) {
366            System.out.println("T[" + n + "] = " + T.get(n)); //.toString(var) );
367        }
368    }
369
370
371    /**
372     * example9. Legendre polynomials
373     * 
374     * P(0) = 1 P(1) = x P(n) = 1/n [ (2n-1) * x * P(n-1) - (n-1) * P(n-2) ]
375     */
376    // P(n+1) = 1/(n+1) [ (2n+1) * x * P(n) - n * P(n-1) ]
377    public static void example9() {
378        int n = 10;
379
380        BigRational fac = new BigRational();
381        String[] var = new String[] { "x" };
382
383        GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, 1, var);
384
385        List<GenPolynomial<BigRational>> P = new ArrayList<GenPolynomial<BigRational>>(n);
386
387        GenPolynomial<BigRational> t, one, x, xc;
388        BigRational n21, nn;
389
390        one = ring.getONE();
391        x = ring.univariate(0);
392
393        P.add(one);
394        P.add(x);
395        for (int i = 2; i < n; i++) {
396            n21 = new BigRational(2 * i - 1);
397            xc = x.multiply(n21);
398            t = xc.multiply(P.get(i - 1));
399            nn = new BigRational(i - 1);
400            xc = P.get(i - 2).multiply(nn);
401            t = t.subtract(xc);
402            nn = new BigRational(1, i);
403            t = t.multiply(nn);
404            P.add(t);
405        }
406        for (int i = 0; i < n; i++) {
407            System.out.println("P[" + i + "] = " + P.get(i).toString(var));
408            System.out.println();
409        }
410    }
411
412
413    /**
414     * example10. Hermite polynomials
415     * 
416     * H(0) = 1 H(1) = 2 x H(n) = 2 * x * H(n-1) - 2 * (n-1) * H(n-2)
417     */
418    // H(n+1) = 2 * x * H(n) - 2 * n * H(n-1)
419    public static void example10() {
420        int n = 100;
421
422        BigInteger fac = new BigInteger();
423        String[] var = new String[] { "x" };
424
425        GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var);
426
427        List<GenPolynomial<BigInteger>> H = new ArrayList<GenPolynomial<BigInteger>>(n);
428
429        GenPolynomial<BigInteger> t, one, x2, xc, x;
430        BigInteger n2, nn;
431
432        one = ring.getONE();
433        x = ring.univariate(0);
434        n2 = new BigInteger(2);
435        x2 = x.multiply(n2);
436        H.add(one);
437        H.add(x2);
438        for (int i = 2; i < n; i++) {
439            t = x2.multiply(H.get(i - 1));
440            nn = new BigInteger(2 * (i - 1));
441            xc = H.get(i - 2).multiply(nn);
442            t = t.subtract(xc);
443            H.add(t);
444        }
445        for (int i = n - 1; i < n; i++) {
446            System.out.println("H[" + i + "] = " + H.get(i).toString(var));
447            System.out.println();
448        }
449    }
450
451
452    /**
453     * example11. degree matrix;
454     * 
455     */
456    @SuppressWarnings("cast")
457    public static void example11() {
458        int n = 50;
459        BigRational fac = new BigRational();
460        GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, n);
461        System.out.println("ring = " + ring + "\n");
462
463        GenPolynomial<BigRational> p = ring.random(5, 3, 6, 0.5f);
464        System.out.println("p = " + p + "\n");
465
466        List<GenPolynomial<BigInteger>> dem = TermOrderOptimization.<BigRational> degreeMatrix(p);
467
468        System.out.println("dem = " + dem + "\n");
469
470        List<GenPolynomial<BigRational>> polys = new ArrayList<GenPolynomial<BigRational>>();
471        polys.add(p);
472        for (int i = 0; i < 5; i++) {
473            polys.add(ring.random(5, 3, 6, 0.1f));
474        }
475        System.out.println("polys = " + polys + "\n");
476
477        dem = TermOrderOptimization.<BigRational> degreeMatrix(polys);
478        System.out.println("dem = " + dem + "\n");
479
480        List<Integer> perm;
481        perm = TermOrderOptimization.optimalPermutation(dem);
482        System.out.println("perm = " + perm + "\n");
483
484        List<GenPolynomial<BigInteger>> pdem;
485        pdem = TermOrderOptimization.<GenPolynomial<BigInteger>> listPermutation(perm, dem);
486        System.out.println("pdem = " + pdem + "\n");
487
488        GenPolynomialRing<BigRational> pring;
489        pring = TermOrderOptimization.<BigRational> permutation(perm, ring);
490        System.out.println("ring  = " + ring);
491        System.out.println("pring = " + pring + "\n");
492
493        List<GenPolynomial<BigRational>> ppolys;
494        ppolys = TermOrderOptimization.<BigRational> permutation(perm, pring, polys);
495        System.out.println("ppolys = " + ppolys + "\n");
496
497        dem = TermOrderOptimization.<BigRational> degreeMatrix(ppolys);
498        //System.out.println("pdem = " + dem + "\n");
499
500        perm = TermOrderOptimization.optimalPermutation(dem);
501        //System.out.println("pperm = " + perm + "\n");
502        int i = 0;
503        for (Integer j : perm) {
504            if (i != (int) j) {
505                System.out.println("error = " + i + " != " + j + "\n");
506            }
507            i++;
508        }
509
510        OptimizedPolynomialList<BigRational> op;
511        op = TermOrderOptimization.<BigRational> optimizeTermOrder(ring, polys);
512        System.out.println("op:\n" + op);
513        if (!op.equals(new PolynomialList<BigRational>(pring, ppolys))) {
514            System.out.println("error = " + "\n" + op);
515        }
516    }
517
518
519    /**
520     * example12. type games.
521     */
522    public static void example12() {
523        System.out.println("\n\n example 12");
524
525        BigRational t1 = new BigRational();
526        System.out.println("t1 = " + t1);
527
528        BigInteger t2 = new BigInteger();
529        System.out.println("t2 = " + t2);
530
531        System.out.println("t1.isAssignableFrom(t2) = " + t1.getClass().isAssignableFrom(t2.getClass()));
532        System.out.println("t2.isAssignableFrom(t1) = " + t2.getClass().isAssignableFrom(t1.getClass()));
533
534        GenPolynomialRing<BigInteger> t3 = new GenPolynomialRing<BigInteger>(t2, 3);
535        System.out.println("t3 = " + t3);
536
537        GenSolvablePolynomialRing<BigInteger> t4 = new GenSolvablePolynomialRing<BigInteger>(t2, 3);
538        System.out.println("t4 = " + t4);
539
540        System.out.println("t3.isAssignableFrom(t4) = " + t3.getClass().isAssignableFrom(t4.getClass()));
541        System.out.println("t4.isAssignableFrom(t3) = " + t4.getClass().isAssignableFrom(t3.getClass()));
542
543
544        GenPolynomialRing<BigRational> t5 = new GenPolynomialRing<BigRational>(t1, 3);
545        System.out.println("t5 = " + t5);
546
547        System.out.println("t3.isAssignableFrom(t5) = " + t3.getClass().isAssignableFrom(t5.getClass()));
548        System.out.println("t5.isAssignableFrom(t3) = " + t5.getClass().isAssignableFrom(t3.getClass()));
549    }
550
551
552    /**
553     * example13. poly parser for strange syntax.
554     */
555    public static void example13() {
556        System.out.println("\n\n example 13");
557        TermOrder to = new TermOrder(TermOrder.INVLEX);
558        BigRational cfraction = new BigRational(1);
559        String[] vars = new String[] { "x" };
560
561        //Scripting.setPrecision(5);
562
563        GenPolynomialRing<BigRational> pfac 
564            = new GenPolynomialRing<BigRational>(cfraction, 1, to, vars);
565        GenPolynomial<BigRational> FF0 = pfac.parse("19(6)/10");
566        System.out.println("FF0 = " + FF0);
567        FF0 = pfac.parse("19(6)1/10");
568        System.out.println("FF0 = " + FF0);
569        FF0 = pfac.parse("19 6/10");
570        System.out.println("FF0 = " + FF0);
571        FF0 = pfac.parse("19*6/10");
572        System.out.println("FF0 = " + FF0);
573        FF0 = pfac.parse("19+6/10");
574        System.out.println("FF0 = " + FF0);
575        FF0 = pfac.parse("(x).2");
576        System.out.println("FF0 = " + FF0);
577        FF0 = pfac.parse("4.0/9.0");
578        System.out.println("FF0 = " + FF0);
579        FF0 = pfac.parse("4/9.0");
580        System.out.println("FF0 = " + FF0);
581        FF0 = pfac.parse("4.0/9");
582        System.out.println("FF0 = " + FF0);
583        FF0 = pfac.parse("-4.0/9");
584        System.out.println("FF0 = " + FF0);
585    }
586}