001/*
002 * $Id: RealRootTest.java 4010 2012-07-21 20:39:56Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
011
012import junit.framework.Test;
013import junit.framework.TestCase;
014import junit.framework.TestSuite;
015
016import edu.jas.arith.BigDecimal;
017import edu.jas.arith.BigRational;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.TermOrder;
021import edu.jas.structure.Power;
022
023
024/**
025 * RealRoot tests with JUnit.
026 * @author Heinz Kredel.
027 */
028
029public class RealRootTest extends TestCase {
030
031
032    /**
033     * main.
034     */
035    public static void main(String[] args) {
036        junit.textui.TestRunner.run(suite());
037    }
038
039
040    /**
041     * Constructs a <CODE>RealRootTest</CODE> object.
042     * @param name String.
043     */
044    public RealRootTest(String name) {
045        super(name);
046    }
047
048
049    /**
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(RealRootTest.class);
053        return suite;
054    }
055
056
057    //private final static int bitlen = 100;
058
059    TermOrder to = new TermOrder(TermOrder.INVLEX);
060
061
062    GenPolynomialRing<BigRational> dfac;
063
064
065    BigRational ai;
066
067
068    BigRational bi;
069
070
071    BigRational ci;
072
073
074    BigRational di;
075
076
077    BigRational ei;
078
079
080    BigRational eps;
081
082
083    GenPolynomial<BigRational> a;
084
085
086    GenPolynomial<BigRational> b;
087
088
089    GenPolynomial<BigRational> c;
090
091
092    GenPolynomial<BigRational> d;
093
094
095    GenPolynomial<BigRational> e;
096
097
098    int rl = 1;
099
100
101    int kl = 5;
102
103
104    int ll = 7;
105
106
107    int el = 7;
108
109
110    float q = 0.7f;
111
112
113    @Override
114    protected void setUp() {
115        a = b = c = d = e = null;
116        ai = bi = ci = di = ei = null;
117        String[] vars = new String[] { "x" };
118        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
119        // eps = new BigRational(1L,1000000L*1000000L*1000000L);
120        eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
121    }
122
123
124    @Override
125    protected void tearDown() {
126        a = b = c = d = e = null;
127        ai = bi = ci = di = ei = null;
128        dfac = null;
129        eps = null;
130    }
131
132
133    /**
134     * Test Sturm sequence.
135     * 
136     */
137    public void testSturmSequence() {
138        a = dfac.random(kl, ll, el, q);
139        //System.out.println("a = " + a);
140
141        RealRootsSturm<BigRational> rrs = new RealRootsSturm<BigRational>();
142
143        List<GenPolynomial<BigRational>> S = rrs.sturmSequence(a);
144        //System.out.println("S = " + S);
145
146        try {
147            b = a.remainder(S.get(0));
148        } catch (Exception e) {
149            fail("not S(0)|f " + e);
150        }
151        assertTrue("a mod S(0) == 0 ", b.isZERO());
152
153        assertTrue("S(-1) == 1 ", S.get(S.size() - 1).isConstant());
154    }
155
156
157    /**
158     * Test root bound.
159     * 
160     */
161    public void testRootBound() {
162        a = dfac.random(kl, ll, el, q);
163        //System.out.println("a = " + a);
164
165        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
166
167        BigRational M = rr.realRootBound(a);
168
169        //System.out.println("M = " + M);
170        assertTrue("M >= 1 ", M.compareTo(BigRational.ONE) >= 0);
171
172        a = a.monic();
173        //System.out.println("a = " + a);
174        M = rr.realRootBound(a);
175
176        //System.out.println("M = " + M);
177        assertTrue("M >= 1 ", M.compareTo(BigRational.ONE) >= 0);
178    }
179
180
181    /**
182     * Test real root isolation.
183     * 
184     */
185    public void testRealRootIsolation() {
186        a = dfac.random(kl, ll * 2, el * 2, q);
187        //a = a.multiply( dfac.univariate(0) );
188        //System.out.println("a = " + a);
189
190        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
191
192        List<Interval<BigRational>> R = rr.realRoots(a);
193        //System.out.println("R = " + R);
194        assertTrue("#roots >= 0 ", R.size() >= 0);
195    }
196
197
198    /**
199     * Test real root isolation Wilkinson polynomials.
200     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
201     */
202    public void testRealRootIsolationWilkinson() {
203        final int N = 10;
204        d = dfac.getONE();
205        e = dfac.univariate(0);
206
207        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
208        a = d;
209        for (int i = 0; i < N; i++) {
210            c = dfac.fromInteger(i);
211            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
212            b = e.subtract(c);
213            a = a.multiply(b);
214        }
215        //System.out.println("a = " + a);
216
217        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
218
219        List<Interval<BigRational>> R = rr.realRoots(a);
220        //System.out.println("R = " + R);
221
222        assertTrue("#roots = " + N + " ", R.size() == N);
223
224        //System.out.println("eps = " + eps);
225        //BigDecimal eps1 = new BigDecimal(eps);
226        //System.out.println("eps1 = " + eps1);
227
228        R = rr.refineIntervals(R, a, eps);
229        //System.out.println("R = " + R);
230        int i = 0;
231        for (Interval<BigRational> v : R) {
232            BigDecimal dd = v.toDecimal(); //.sum(eps1);
233            BigDecimal di = Rn.get(i++).toDecimal();
234            //System.out.println("v  = " + dd);
235            //System.out.println("vi = " + di);
236            assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
237        }
238    }
239
240
241    /**
242     * Test real root isolation Wilkinson polynomials inverse.
243     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
244     */
245    public void testRealRootIsolationWilkinsonInverse() {
246        final int N = 9;
247        d = dfac.getONE();
248        e = dfac.univariate(0);
249
250        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
251        a = d;
252        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
253            c = dfac.fromInteger(i);
254            if (i != 0) {
255                c = d.divide(c);
256            }
257            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
258            b = e.subtract(c);
259            a = a.multiply(b);
260        }
261        //System.out.println("a = " + a);
262        //System.out.println("Rn = " + Rn);
263        Collections.reverse(Rn);
264        //System.out.println("Rn = " + Rn);
265
266        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
267
268        List<Interval<BigRational>> R = rr.realRoots(a);
269        //System.out.println("R = " + R);
270
271        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
272
273        //System.out.println("eps = " + eps);
274        //BigDecimal eps1 = new BigDecimal(eps);
275        //System.out.println("eps1 = " + eps1);
276
277        R = rr.refineIntervals(R, a, eps);
278        //System.out.println("R = " + R);
279        int i = 0;
280        for (Interval<BigRational> v : R) {
281            BigDecimal dd = v.toDecimal(); //.sum(eps1);
282            BigDecimal di = Rn.get(i++).toDecimal();
283            //System.out.println("v  = " + dd);
284            //System.out.println("vi = " + di);
285            assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
286        }
287    }
288
289
290    /**
291     * Test real algebraic number sign.
292     * 
293     */
294    public void testRealAlgebraicNumberSign() {
295        d = dfac.fromInteger(2);
296        e = dfac.univariate(0);
297
298        a = e.multiply(e);
299        // a = a.multiply(e).multiply(e).multiply(e);
300        a = a.subtract(d); // x^2 -2
301        //System.out.println("a = " + a);
302
303        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
304
305        ai = new BigRational(1);
306        bi = new BigRational(2);
307        Interval<BigRational> iv = new Interval<BigRational>(ai, bi);
308        //System.out.println("iv = " + iv);
309        assertTrue("sign change", rr.signChange(iv, a));
310
311        b = dfac.random(kl, (int) a.degree() + 1, (int) a.degree(), 1.0f);
312        //b = dfac.getZERO();
313        //b = dfac.random(kl,ll,el,q);
314        //b = b.multiply(b);
315        //b = b.abs().negate();
316        //System.out.println("b = " + b);
317        if (b.isZERO()) {
318            int s = rr.realSign(iv, a, b);
319            assertTrue("algebraic sign", s == 0);
320            return;
321        }
322
323        int as = rr.realSign(iv, a, b);
324        //System.out.println("as = " + as);
325        // how to test?
326        int asn = rr.realSign(iv, a, b.negate());
327        //System.out.println("asn = " + asn);
328        assertTrue("algebraic sign", as != asn);
329
330        iv = new Interval<BigRational>(bi.negate(), ai.negate());
331        //System.out.println("iv = " + iv);
332        assertTrue("sign change", rr.signChange(iv, a));
333
334        int as1 = rr.realSign(iv, a, b);
335        //System.out.println("as1 = " + as1);
336        // how to test?
337        int asn1 = rr.realSign(iv, a, b.negate());
338        //System.out.println("asn1 = " + asn1);
339        assertTrue("algebraic sign", as1 != asn1);
340
341        assertTrue("algebraic sign", as * as1 == asn * asn1);
342    }
343
344
345    /**
346     * Test real root isolation and decimal refinement of Wilkinson polynomials.
347     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
348     */
349    public void testRealRootIsolationDecimalWilkinson() {
350        final int N = 10;
351        d = dfac.getONE();
352        e = dfac.univariate(0);
353
354        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
355        a = d;
356        for (int i = 0; i < N; i++) {
357            c = dfac.fromInteger(i);
358            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
359            b = e.subtract(c);
360            a = a.multiply(b);
361        }
362        //System.out.println("a = " + a);
363
364        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
365
366        List<Interval<BigRational>> R = rr.realRoots(a);
367        //System.out.println("R = " + R);
368
369        assertTrue("#roots = " + N + " ", R.size() == N);
370
371        eps = eps.multiply(new BigRational(10000));
372        //System.out.println("eps = " + eps);
373        BigDecimal eps1 = new BigDecimal(eps);
374        BigDecimal eps2 = eps1.multiply(new BigDecimal("100"));
375        //System.out.println("eps1 = " + eps1);
376        //System.out.println("eps2 = " + eps2);
377
378        try {
379            int i = 0;
380            for (Interval<BigRational> v : R) {
381                //System.out.println("v = " + v);
382                BigDecimal dd = rr.approximateRoot(v,a,eps);
383                BigDecimal di = Rn.get(i++).toDecimal();
384                //System.out.println("di = " + di);
385                //System.out.println("dd = " + dd);
386                assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
387            }
388        } catch (NoConvergenceException e) {
389            fail(e.toString());
390        }
391    }
392
393
394    /**
395     * Test real root isolation and decimal refinement of Wilkinson polynomials, inverse roots.
396     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
397     */
398    public void testRealRootIsolationDecimalWilkinsonInverse() {
399        final int N = 10;
400        d = dfac.getONE();
401        e = dfac.univariate(0);
402
403        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
404        a = d;
405        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
406            c = dfac.fromInteger(i);
407            if (i != 0) {
408                c = d.divide(c);
409            }
410            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
411            b = e.subtract(c);
412            a = a.multiply(b);
413        }
414        //System.out.println("a = " + a);
415        //System.out.println("Rn = " + Rn);
416        Collections.reverse(Rn);
417        //System.out.println("Rn = " + Rn);
418
419        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
420
421        List<Interval<BigRational>> R = rr.realRoots(a);
422        //System.out.println("R = " + R);
423
424        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
425
426        eps = eps.multiply(new BigRational(1000000));
427        //System.out.println("eps = " + eps);
428        BigDecimal eps1 = new BigDecimal(eps);
429        BigDecimal eps2 = eps1.multiply(new BigDecimal("10"));
430        //System.out.println("eps1 = " + eps1);
431        //System.out.println("eps2 = " + eps2);
432
433        try {
434            int i = 0;
435            for (Interval<BigRational> v : R) {
436                //System.out.println("v = " + v);
437                BigDecimal dd = rr.approximateRoot(v,a,eps);
438                BigDecimal di = Rn.get(i++).toDecimal();
439                //System.out.println("di = " + di);
440                //System.out.println("dd = " + dd);
441                assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
442            }
443        } catch (NoConvergenceException e) {
444            fail(e.toString());
445        }
446    }
447
448
449    /**
450     * Test real root isolation and decimal refinement of Wilkinson polynomials, all roots.
451     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
452     */
453    public void testRealRootIsolationDecimalWilkinsonAll() {
454        final int N = 10; 
455        d = dfac.getONE();
456        e = dfac.univariate(0);
457
458        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
459        a = d;
460        for (int i = 0; i < N; i++) {
461            c = dfac.fromInteger(i);
462            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
463            b = e.subtract(c);
464            a = a.multiply(b);
465        }
466        //System.out.println("a = " + a);
467
468        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
469
470        eps = eps.multiply(new BigRational(10000));
471        //System.out.println("eps = " + eps);
472        BigDecimal eps1 = new BigDecimal(eps);
473        BigDecimal eps2 = eps1.multiply(new BigDecimal("100"));
474        //System.out.println("eps1 = " + eps1);
475        //System.out.println("eps2 = " + eps2);
476
477        List<BigDecimal> R = null;
478        R = rr.approximateRoots(a,eps);
479        //System.out.println("R = " + R);
480        assertTrue("#roots = " + N + " ", R.size() == N);
481
482        int i = 0;
483        for (BigDecimal dd : R) {
484            //System.out.println("dd = " + dd);
485            BigDecimal di = Rn.get(i++).toDecimal();
486            //System.out.println("di = " + di);
487            assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
488        }
489        boolean t = rr.isApproximateRoot(R,a,eps);
490        assertTrue("some |a(dd)| < eps ", t);
491    }
492
493
494    /**
495     * Test real root isolation and decimal refinement of Wilkinson polynomials, inverse roots, all roots.
496     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
497     */
498    public void testRealRootIsolationDecimalWilkinsonInverseAll() {
499        final int N = 10;
500        d = dfac.getONE();
501        e = dfac.univariate(0);
502
503        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
504        a = d;
505        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
506            c = dfac.fromInteger(i);
507            if (i != 0) {
508                c = d.divide(c);
509            }
510            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
511            b = e.subtract(c);
512            a = a.multiply(b);
513        }
514        //System.out.println("a = " + a);
515        //System.out.println("Rn = " + Rn);
516        Collections.reverse(Rn);
517        //System.out.println("Rn = " + Rn);
518
519        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
520
521        eps = eps.multiply(new BigRational(1000000));
522        //System.out.println("eps = " + eps);
523        BigDecimal eps1 = new BigDecimal(eps);
524        BigDecimal eps2 = eps1.multiply(new BigDecimal("10"));
525        //System.out.println("eps1 = " + eps1);
526        //System.out.println("eps2 = " + eps2);
527
528        List<BigDecimal> R = null;
529        R = rr.approximateRoots(a,eps);
530        //System.out.println("R = " + R);
531        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
532
533        int i = 0;
534        for (BigDecimal dd : R) {
535            //System.out.println("dd = " + dd);
536            BigDecimal di = Rn.get(i++).toDecimal();
537            //System.out.println("di = " + di);
538            assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
539        }
540        boolean t = rr.isApproximateRoot(R,a,eps);
541        assertTrue("some |a(dd)| < eps ", t);
542    }
543
544}