001    /*
002     * $Id: RealAlgebraicTest.java 2726 2009-07-09 20:23:53Z kredel $
003     */
004    
005    package edu.jas.root;
006    
007    
008    import java.util.ArrayList;
009    import java.util.List;
010    
011    import junit.framework.Test;
012    import junit.framework.TestCase;
013    import junit.framework.TestSuite;
014    
015    import org.apache.log4j.BasicConfigurator;
016    
017    import edu.jas.arith.BigDecimal;
018    import edu.jas.arith.BigRational;
019    import edu.jas.poly.GenPolynomial;
020    import edu.jas.poly.GenPolynomialRing;
021    import edu.jas.structure.NotInvertibleException;
022    import edu.jas.structure.Power;
023    
024    
025    /**
026     * RealAlgebraicNumber Test using JUnit.
027     * @author Heinz Kredel.
028     */
029    
030    public 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.subtract(dd1).abs().compareTo(epsd) <= 0);
364            assertTrue("mag(a+b) = mag(a)+mag(b)", 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    }