Source code

001/*
002 * $Id: RealAlgebraicTest.java 4039 2012-07-25 14:35:06Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015import org.apache.log4j.BasicConfigurator;
016
017import edu.jas.arith.BigDecimal;
018import edu.jas.arith.BigRational;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.structure.NotInvertibleException;
022import edu.jas.structure.Power;
023
024
025/**
026 * RealAlgebraicNumber Test using JUnit.
027 * @author Heinz Kredel.
028 */
029
030public class RealAlgebraicTest extends TestCase {
031
032
033    /**
034     * main.
035     */
036    public static void main(String[] args) {
037        BasicConfigurator.configure();
038        junit.textui.TestRunner.run(suite());
039    }
040
041
042    /**
043     * Constructs a <CODE>RealAlgebraicTest</CODE> object.
044     * @param name String.
045     */
046    public RealAlgebraicTest(String name) {
047        super(name);
048    }
049
050
051    /**
052     * suite.
053     */
054    public static Test suite() {
055        TestSuite suite = new TestSuite(RealAlgebraicTest.class);
056        return suite;
057    }
058
059
060    //private final static int bitlen = 100;
061
062    RealAlgebraicRing<BigRational> fac;
063
064
065    GenPolynomialRing<BigRational> mfac;
066
067
068    RealAlgebraicNumber<BigRational> a;
069
070
071    RealAlgebraicNumber<BigRational> b;
072
073
074    RealAlgebraicNumber<BigRational> c;
075
076
077    RealAlgebraicNumber<BigRational> d;
078
079
080    RealAlgebraicNumber<BigRational> e;
081
082
083    RealAlgebraicNumber<BigRational> alpha;
084
085
086    int rl = 1;
087
088
089    int kl = 10;
090
091
092    int ll = 10;
093
094
095    int el = ll;
096
097
098    float q = 0.5f;
099
100
101    @Override
102    protected void setUp() {
103        a = b = c = d = e = null;
104        BigRational l = new BigRational(1);
105        BigRational r = new BigRational(2);
106        Interval<BigRational> positiv = new Interval<BigRational>(l, r);
107        String[] vars = new String[] { "alpha" };
108        mfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, vars);
109        GenPolynomial<BigRational> mo = mfac.univariate(0, 2);
110        mo = mo.subtract(mfac.fromInteger(2)); // alpha^2 -2 
111        fac = new RealAlgebraicRing<BigRational>(mo, positiv);
112        alpha = fac.getGenerator();
113    }
114
115
116    @Override
117    protected void tearDown() {
118        a = b = c = d = e = null;
119        fac = null;
120        alpha = null;
121    }
122
123
124    /**
125     * Test constructor and toString.
126     * 
127     */
128    public void testConstruction() {
129        c = fac.getONE();
130        //System.out.println("c = " + c);
131        //System.out.println("c.getVal() = " + c.getVal());
132        assertTrue("length( c ) = 1", c.number.getVal().length() == 1);
133        assertTrue("isZERO( c )", !c.isZERO());
134        assertTrue("isONE( c )", c.isONE());
135
136        d = fac.getZERO();
137        //System.out.println("d = " + d);
138        //System.out.println("d.getVal() = " + d.getVal());
139        assertTrue("length( d ) = 0", d.number.getVal().length() == 0);
140        assertTrue("isZERO( d )", d.isZERO());
141        assertTrue("isONE( d )", !d.isONE());
142    }
143
144
145    /**
146     * Test random polynomial.
147     * 
148     */
149    public void testRandom() {
150        for (int i = 0; i < 7; i++) {
151            a = fac.random(el);
152            //System.out.println("a = " + a);
153            if (a.isZERO() || a.isONE()) {
154                continue;
155            }
156            // fac.random(rl+i, kl*(i+1), ll+2*i, el+i, q );
157            assertTrue("length( a" + i + " ) <> 0", a.number.getVal().length() >= 0);
158            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
159            assertTrue(" not isONE( a" + i + " )", !a.isONE());
160        }
161    }
162
163
164    /**
165     * Test addition.
166     * 
167     */
168    public void testAddition() {
169        a = fac.random(ll);
170        b = fac.random(ll);
171
172        c = a.sum(b);
173        d = c.subtract(b);
174        assertEquals("a+b-b = a", a, d);
175
176        c = a.sum(b);
177        d = b.sum(a);
178        assertEquals("a+b = b+a", c, d);
179
180        c = fac.random(ll);
181        d = c.sum(a.sum(b));
182        e = c.sum(a).sum(b);
183        assertEquals("c+(a+b) = (c+a)+b", d, e);
184
185
186        c = a.sum(fac.getZERO());
187        d = a.subtract(fac.getZERO());
188        assertEquals("a+0 = a-0", c, d);
189
190        c = fac.getZERO().sum(a);
191        d = fac.getZERO().subtract(a.negate());
192        assertEquals("0+a = 0+(-a)", c, d);
193    }
194
195
196    /**
197     * Test object multiplication.
198     * 
199     */
200    public void testMultiplication() {
201        a = fac.random(ll);
202        assertTrue("not isZERO( a )", !a.isZERO());
203
204        b = fac.random(ll);
205        assertTrue("not isZERO( b )", !b.isZERO());
206
207        c = b.multiply(a);
208        d = a.multiply(b);
209        assertTrue("not isZERO( c )", !c.isZERO());
210        assertTrue("not isZERO( d )", !d.isZERO());
211
212        //System.out.println("a = " + a);
213        //System.out.println("b = " + b);
214        e = d.subtract(c);
215        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
216
217        assertTrue("a*b = b*a", c.equals(d));
218        assertEquals("a*b = b*a", c, d);
219
220        c = fac.random(ll);
221        //System.out.println("c = " + c);
222        d = a.multiply(b.multiply(c));
223        e = (a.multiply(b)).multiply(c);
224
225        //System.out.println("d = " + d);
226        //System.out.println("e = " + e);
227
228        //System.out.println("d-e = " + d.subtract(c) );
229
230        assertEquals("a(bc) = (ab)c", d, e);
231        assertTrue("a(bc) = (ab)c", d.equals(e));
232
233        c = a.multiply(fac.getONE());
234        d = fac.getONE().multiply(a);
235        assertEquals("a*1 = 1*a", c, d);
236
237
238        c = a.inverse();
239        d = c.multiply(a);
240        //System.out.println("a = " + a);
241        //System.out.println("c = " + c);
242        //System.out.println("d = " + d);
243        assertEquals("a*1/a = 1", fac.getONE(), d);
244
245        try {
246            a = fac.getZERO().inverse();
247        } catch (NotInvertibleException expected) {
248            return;
249        }
250        fail("0 invertible");
251    }
252
253
254    /**
255     * Test distributive law.
256     * 
257     */
258    public void testDistributive() {
259        a = fac.random(ll);
260        b = fac.random(ll);
261        c = fac.random(ll);
262
263        d = a.multiply(b.sum(c));
264        e = a.multiply(b).sum(a.multiply(c));
265
266        assertEquals("a(b+c) = ab+ac", d, e);
267    }
268
269
270    /**
271     * Test sign of real algebraic numbers.
272     * 
273     */
274    public void testSignum() {
275        a = fac.random(ll);
276        b = fac.random(ll);
277        c = fac.random(ll);
278
279        int sa = a.signum();
280        int sb = b.signum();
281        int sc = c.signum();
282
283        d = a.multiply(b);
284        e = a.multiply(c);
285
286        int sd = d.signum();
287        int se = e.signum();
288
289        assertEquals("sign(a*b) = sign(a)*sign(b) ", sa * sb, sd);
290        assertEquals("sign(a*c) = sign(a)*sign(c) ", sa * sc, se);
291
292        b = a.negate();
293        sb = b.signum();
294        assertEquals("sign(-a) = -sign(a) ", -sa, sb);
295    }
296
297
298    /**
299     * Test compareTo of real algebraic numbers.
300     * 
301     */
302    public void testCompare() {
303        a = fac.random(ll).abs();
304        b = a.sum(fac.getONE());
305        c = b.sum(fac.getONE());
306
307        int ab = a.compareTo(b);
308        int bc = b.compareTo(c);
309        int ac = a.compareTo(c);
310
311        assertTrue("a < a+1 ", ab < 0);
312        assertTrue("a+1 < a+2 ", bc < 0);
313        assertTrue("a < a+2 ", ac < 0);
314
315        a = a.negate();
316        b = a.sum(fac.getONE());
317        c = b.sum(fac.getONE());
318
319        ab = a.compareTo(b);
320        bc = b.compareTo(c);
321        ac = a.compareTo(c);
322
323        assertTrue("a < a+1 ", ab < 0);
324        assertTrue("a+1 < a+2 ", bc < 0);
325        assertTrue("a < a+2 ", ac < 0);
326    }
327
328
329    /**
330     * Test arithmetic of magnitude of real algebraic numbers.
331     * 
332     */
333    public void testMagnitude() {
334        a = fac.random(ll);
335        b = fac.random(ll);
336        c = fac.random(ll);
337
338        //BigDecimal ad = new BigDecimal(a.magnitude());
339        //BigDecimal bd = new BigDecimal(b.magnitude());
340        //BigDecimal cd = new BigDecimal(c.magnitude());
341
342        d = a.multiply(b);
343        e = a.sum(b);
344
345        BigDecimal dd = new BigDecimal(d.magnitude());
346        BigDecimal ed = new BigDecimal(e.magnitude());
347
348        BigDecimal dd1 = new BigDecimal(a.magnitude().multiply(b.magnitude()));
349        BigDecimal ed1 = new BigDecimal(a.magnitude().sum(b.magnitude()));
350
351        //System.out.println("ad  = " + ad);
352        //System.out.println("bd  = " + bd);
353        //System.out.println("cd  = " + cd);
354        //System.out.println("dd  = " + dd);
355        //System.out.println("dd1 = " + dd1);
356        //System.out.println("ed  = " + ed);
357        //System.out.println("ed1 = " + ed1);
358
359        //BigRational eps = Power.positivePower(new BigRational(1L,10L),BigDecimal.DEFAULT_PRECISION);
360        BigRational eps = Power.positivePower(new BigRational(1L, 10L), 8);
361        BigDecimal epsd = new BigDecimal(eps);
362
363        assertTrue("mag(a*b) = mag(a)*mag(b): " + dd + ", " + dd1, dd.subtract(dd1).abs().compareTo(epsd) <= 0);
364        assertTrue("mag(a+b) = mag(a)+mag(b): " + ed + ", " + ed1, ed.subtract(ed1).abs().compareTo(epsd) <= 0);
365
366
367        d = a.divide(b);
368        e = a.subtract(b);
369
370        dd = new BigDecimal(d.magnitude());
371        ed = new BigDecimal(e.magnitude());
372
373        dd1 = new BigDecimal(a.magnitude().divide(b.magnitude()));
374        ed1 = new BigDecimal(a.magnitude().subtract(b.magnitude()));
375
376        //System.out.println("dd  = " + dd);
377        //System.out.println("dd1 = " + dd1);
378        //System.out.println("ed  = " + ed);
379        //System.out.println("ed1 = " + ed1);
380
381        assertTrue("mag(a/b) = mag(a)/mag(b)", dd.subtract(dd1).abs().compareTo(epsd) <= 0);
382        assertTrue("mag(a-b) = mag(a)-mag(b)", ed.subtract(ed1).abs().compareTo(epsd) <= 0);
383    }
384
385
386    /**
387     * Test real root isolation. Tests nothing.
388     */
389    public void notestRealRootIsolation() {
390        System.out.println();
391        GenPolynomialRing<RealAlgebraicNumber<BigRational>> dfac;
392        dfac = new GenPolynomialRing<RealAlgebraicNumber<BigRational>>(fac, 1);
393
394        GenPolynomial<RealAlgebraicNumber<BigRational>> ar;
395        RealAlgebraicNumber<BigRational> epsr;
396
397        ar = dfac.random(3, 5, 7, q);
398        System.out.println("ar = " + ar);
399
400        RealRoots<RealAlgebraicNumber<BigRational>> rrr = new RealRootsSturm<RealAlgebraicNumber<BigRational>>();
401
402        List<Interval<RealAlgebraicNumber<BigRational>>> R = rrr.realRoots(ar);
403        System.out.println("R = " + R);
404
405        assertTrue("#roots >= 0 ", R.size() >= 0);
406
407        BigRational eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
408        //BigRational eps = Power.positivePower(new BigRational(1L,10L),10);
409
410        epsr = dfac.coFac.getONE().multiply(eps);
411        //System.out.println("epsr = " + epsr);
412
413        R = rrr.refineIntervals(R, ar, epsr);
414        //System.out.println("R = " + R);
415        for (Interval<RealAlgebraicNumber<BigRational>> v : R) {
416            BigDecimal dd = v.toDecimal(); //.sum(eps1);
417            System.out.println("v = " + dd);
418            // assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
419        }
420    }
421
422
423    /**
424     * Test real root isolation for Wilkinson like polynomials.
425     * product_{i=1..n}( x - i * alpha )
426     * 
427     */
428    public void testRealRootIsolationWilkinson() {
429        //System.out.println();
430        GenPolynomialRing<RealAlgebraicNumber<BigRational>> dfac;
431        dfac = new GenPolynomialRing<RealAlgebraicNumber<BigRational>>(fac, 1);
432
433        GenPolynomial<RealAlgebraicNumber<BigRational>> ar, br, cr, dr, er;
434
435        RealRoots<RealAlgebraicNumber<BigRational>> rrr = new RealRootsSturm<RealAlgebraicNumber<BigRational>>();
436
437        final int N = 3;
438        dr = dfac.getONE();
439        er = dfac.univariate(0);
440
441        List<Interval<RealAlgebraicNumber<BigRational>>> Rn = new ArrayList<Interval<RealAlgebraicNumber<BigRational>>>(
442                N);
443        ar = dr;
444        for (int i = 0; i < N; i++) {
445            cr = dfac.fromInteger(i).multiply(alpha); // i * alpha
446            Rn.add(new Interval<RealAlgebraicNumber<BigRational>>(cr.leadingBaseCoefficient()));
447            br = er.subtract(cr); // ( x - i * alpha )
448            ar = ar.multiply(br);
449        }
450        //System.out.println("ar = " + ar);
451
452        List<Interval<RealAlgebraicNumber<BigRational>>> R = rrr.realRoots(ar);
453        //System.out.println("R = " + R);
454
455        assertTrue("#roots = " + N + " ", R.size() == N);
456
457        BigRational eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
458        //BigRational eps = Power.positivePower(new BigRational(1L,10L),10);
459        //System.out.println("eps = " + eps);
460        //BigDecimal eps1 = new BigDecimal(eps);
461        //System.out.println("eps1 = " + eps1);
462        RealAlgebraicNumber<BigRational> epsr = dfac.coFac.getONE().multiply(eps);
463        //System.out.println("epsr = " + epsr);
464
465        R = rrr.refineIntervals(R, ar, epsr);
466        //System.out.println("R = " + R);
467        int i = 0;
468        for (Interval<RealAlgebraicNumber<BigRational>> v : R) {
469            BigDecimal dd = v.toDecimal();//.sum(eps1);
470            BigDecimal di = Rn.get(i++).toDecimal();
471            //System.out.println("v  = " + dd);
472            //System.out.println("vi = " + di);
473            assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
474        }
475    }
476
477}