Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.root;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.arith.BigDecimal;
012import edu.jas.arith.BigRational;
013import edu.jas.kern.ComputerThreads;
014import edu.jas.poly.Complex;
015import edu.jas.poly.ComplexRing;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019import edu.jas.poly.TermOrder;
020import edu.jas.structure.Power;
021
022import junit.framework.Test;
023import junit.framework.TestCase;
024import junit.framework.TestSuite;
025
026
027/**
028 * RootUtil tests with JUnit.
029 * @author Heinz Kredel
030 */
031
032public class RootUtilTest extends TestCase {
033
034
035    /**
036     * main.
037     */
038    public static void main(String[] args) {
039        junit.textui.TestRunner.run(suite());
040    }
041
042
043    /**
044     * Constructs a <CODE>RootUtilTest</CODE> object.
045     * @param name String.
046     */
047    public RootUtilTest(String name) {
048        super(name);
049    }
050
051
052    /**
053     */
054    public static Test suite() {
055        TestSuite suite = new TestSuite(RootUtilTest.class);
056        return suite;
057    }
058
059
060    TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063    GenPolynomialRing<BigRational> dfac;
064
065
066    BigRational ai, bi, ci, di, ei, eps;
067
068
069    GenPolynomial<BigRational> a, b, c, d, e;
070
071
072    int rl = 1;
073
074
075    int kl = 3;
076
077
078    int ll = 5;
079
080
081    int el = 7;
082
083
084    float q = 0.7f;
085
086
087    @Override
088    protected void setUp() {
089        a = b = c = d = e = null;
090        ai = bi = ci = di = ei = null;
091        String[] vars = new String[] { "x" };
092        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
093        // eps = new BigRational(1L,1000000L*1000000L*1000000L);
094        eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
095    }
096
097
098    @Override
099    protected void tearDown() {
100        a = b = c = d = e = null;
101        ai = bi = ci = di = ei = null;
102        dfac = null;
103        eps = null;
104        ComputerThreads.terminate();
105    }
106
107
108    /**
109     * Test sign variations.
110     */
111    public void testSignVar() {
112        int[] li = new int[] { 1, 0, 0, -1, 2, 3, 0, 1, 0, 0, 0, -1 };
113
114        List<BigRational> Li = new ArrayList<BigRational>();
115
116        ai = new BigRational();
117
118        for (int i = 0; i < li.length; i++) {
119            bi = ai.fromInteger(li[i]);
120            Li.add(bi);
121        }
122        //System.out.println("Li = " + Li);
123
124        long v = RootUtil.<BigRational> signVar(Li);
125        //System.out.println("v = " + v);
126
127        assertEquals("varSign(Li)", v, 3);
128
129        List<BigRational> Mi = new ArrayList<BigRational>();
130        for (int i = 0; i < 7; i++) {
131            bi = ai.random(kl);
132            Mi.add(bi);
133        }
134        //System.out.println("Mi = " + Mi);
135
136        v = RootUtil.<BigRational> signVar(Mi);
137        //System.out.println("v = " + v);
138        long vv = v;
139
140        assertTrue("varSign(Mi)>=0", v >= 0);
141
142        List<BigRational> Ni = new ArrayList<BigRational>(Mi);
143        Ni.addAll(Li);
144        //System.out.println("Ni = " + Ni);
145
146        v = RootUtil.<BigRational> signVar(Ni);
147        //System.out.println("v = " + v);
148
149        assertTrue("varSign(Mi)>=3", v >= 3 + vv);
150
151        Ni = new ArrayList<BigRational>(Ni);
152        Ni.addAll(Mi);
153        //System.out.println("Ni = " + Ni);
154
155        v = RootUtil.<BigRational> signVar(Ni);
156        //System.out.println("v = " + v);
157
158        assertTrue("varSign(Mi)>=3", v >= 3 + vv);
159    }
160
161
162    /**
163     * Test intervals.
164     */
165    public void testIntervals() {
166        a = dfac.random(kl, ll * 2, el * 2, q);
167        b = dfac.random(kl, ll * 2, el * 2, q);
168        b = b.multiply(b);
169        //System.out.println("a = " + a);
170        //System.out.println("b = " + b);
171
172        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
173
174        ai = rr.realRootBound(a);
175        bi = rr.realRootBound(b);
176        //System.out.println("ai = " + ai);
177        //System.out.println("bi = " + bi);
178
179        Interval<BigRational> v1 = new Interval<BigRational>(ai.negate(), ai);
180        Interval<BigRational> v2 = new Interval<BigRational>(bi.negate(), bi.sum(BigRational.ONE));
181        //System.out.println("v1 = " + v1);
182        //System.out.println("v2 = " + v2);
183
184        Interval<BigRational> v3 = v1.sum(v2);
185        Interval<BigRational> v4 = v1.subtract(v2);
186        Interval<BigRational> v5 = v1.multiply(v2);
187        //System.out.println("v3 = " + v3);
188        //System.out.println("v4 = " + v4);
189        //System.out.println("v5 = " + v5);
190        assertTrue("v1 in v3", v3.contains(v1));
191        assertTrue("v2 in v3", v3.contains(v2));
192
193        assertTrue("v1 in v4", v4.contains(v1));
194        assertTrue("v2 in v4", v4.contains(v2));
195
196        assertTrue("v3 in v5", v5.contains(v3));
197        assertTrue("v4 in v5", v5.contains(v4));
198    }
199
200
201    /**
202     * Test real algebraic factory.
203     */
204    public void testRealAlgebraicFactory() {
205        a = dfac.random(kl, ll * 2, el * 2, q);
206        //a = a.multiply( dfac.univariate(0) );
207        //System.out.println("a = " + a);
208
209        List<RealAlgebraicNumber<BigRational>> lrn = RootFactory.<BigRational> realAlgebraicNumbers(a);
210        //System.out.println("lrn = " + lrn);
211        //assertTrue("#roots >= 0 ", lrn.size() >= 0);
212        assertTrue("#roots >= 0 ", lrn != null);
213        for (RealAlgebraicNumber<BigRational> ra : lrn) {
214            //System.out.println("ra = " + ra.toScript() + " in " + ra.toScriptFactory());
215            assertTrue("f(r) == 0: " + ra, RootFactory.<BigRational> isRoot(a, ra));
216        }
217
218        lrn = RootFactory.<BigRational> realAlgebraicNumbersField(a);
219        //System.out.println("lrn = " + lrn);
220        assertTrue("#roots >= 0 ", lrn != null);
221        for (RealAlgebraicNumber<BigRational> ra : lrn) {
222            //System.out.println("ra = " + ra.toScript() + " in " + ra.toScriptFactory());
223            assertTrue("f(r) == 0: " + ra, RootFactory.<BigRational> isRoot(a, ra));
224        }
225    }
226
227
228    /**
229     * Test complex algebraic factory.
230     */
231    public void testComplexAlgebraicFactory() {
232        a = dfac.random(kl, ll, el, q);
233        //a = a.multiply( dfac.univariate(0) );
234        //System.out.println("a = " + a);
235        ComplexRing<BigRational> cf = new ComplexRing<BigRational>(new BigRational());
236        GenPolynomialRing<Complex<BigRational>> cfac = new GenPolynomialRing<Complex<BigRational>>(cf, dfac);
237
238        GenPolynomial<Complex<BigRational>> ca = PolyUtil.<BigRational> toComplex(cfac, a);
239        //System.out.println("ca = " + ca);
240        List<ComplexAlgebraicNumber<BigRational>> lcn = RootFactory
241                        .<BigRational> complexAlgebraicNumbersComplex(ca);
242        //System.out.println("lcn = " + lcn);
243        assertTrue("#roots == deg(a): " + a, lcn.size() == a.degree(0));
244
245        for (ComplexAlgebraicNumber<BigRational> car : lcn) {
246            //System.out.println("car = " + car.toScript() + " in " + car.toScriptFactory());
247            //System.out.println("car = " + car.ring.root);
248            //System.out.println("car = " + car.ring.root.centerApprox() + ", "
249            //        + (Roots.sqrt(new BigDecimal(car.ring.root.rationalLength()))) + ", " + car.ring.root);
250            assertTrue("f(r) == 0: " + car, RootFactory.<BigRational> isRoot(a, car));
251        }
252    }
253
254
255    /**
256     * Test complex rational factory.
257     */
258    public void testComplexRationalFactory() {
259        a = dfac.random(kl, ll, el, q);
260        //a = a.multiply( dfac.univariate(0) );
261        //a = dfac.parse(" 1/8 x^6 - 5/3 x^5 + 3/20 x^4 - 2 x^3 ");
262        //System.out.println("a = " + a);
263
264        List<ComplexAlgebraicNumber<BigRational>> lcn = RootFactory.<BigRational> complexAlgebraicNumbers(a);
265        //System.out.println("lcn = " + lcn);
266        assertTrue("#roots == deg(a): " + a, lcn.size() == a.degree(0));
267
268        for (ComplexAlgebraicNumber<BigRational> car : lcn) {
269            //System.out.println("car = " + car.toScript() + " in " + car.toScriptFactory());
270            //System.out.println("car = " + car.ring.root);
271            //System.out.println("car = " + car.ring.root.centerApprox() + ", "
272            //        + (Roots.sqrt(new BigDecimal(car.ring.root.rationalLength()))) + ", " + car.ring.root);
273            assertTrue("f(r) == 0: " + car, RootFactory.<BigRational> isRoot(a, car));
274        }
275    }
276
277
278    /**
279     * Test algebraic roots, i.e. real and complex algebraic roots.
280     */
281    public void testAlgebraicRoots() {
282        a = dfac.random(kl, ll, el, q);
283        //a = a.multiply( dfac.univariate(0) );
284        //System.out.println("a = " + a);
285
286        AlgebraicRoots<BigRational> lcn = RootFactory.<BigRational> algebraicRoots(a);
287        String ts = lcn.toScript();
288        //System.out.println("lcn = " + ts);
289        assertTrue("complex in lcn: " + ts, ts.indexOf("real") >= 0 || ts.indexOf("complex") >= 0);
290        ts = lcn.toDecimalScript();
291        //System.out.println("lcn = " + ts);
292        assertTrue("complex in lcn: " + ts, ts.indexOf("real") >= 0 || ts.indexOf("complex") >= 0);
293
294        long r = lcn.real.size() + lcn.complex.size();
295        ////Roots<BigRational> linalg = new Roots<BigRational>();
296        ////List<Complex<BigDecimal>> cd = linalg.complexRoots(a);
297        ////System.out.println("cd = " + cd);
298
299        // some real roots eventually not detected under complex roots
300        assertTrue("#roots == degree(f): " + r, r >= a.degree());
301    }
302
303
304    /**
305     * Test decimal algebraic roots, i.e. real and complex decimal algebraic
306     * roots.
307     */
308    public void testDecimalRoots() {
309        a = dfac.random(kl, ll - 1, el, q);
310        //a = a.multiply( dfac.univariate(0) );
311        //System.out.println("a = " + a);
312        int prec = BigDecimal.DEFAULT_PRECISION / 2;
313        BigRational eps = (new BigRational(1, 10)).power(prec);
314        //System.out.println("prec = " + prec + ", eps = " + eps);
315
316        DecimalRoots<BigRational> lcn = RootFactory.<BigRational> decimalRoots(a, eps);
317        String ts = lcn.toScript();
318        //System.out.println("lcn = " + ts);
319        assertTrue("complex in lcn: " + ts, ts.indexOf("real") >= 0 || ts.indexOf("complex") >= 0);
320
321        long r = lcn.real.size() + lcn.complex.size();
322        // some real roots eventually not detected under complex roots
323        assertTrue("#roots == degree(f): " + r, r >= a.degree());
324    }
325
326}