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 }