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