commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r760901 - in /commons/proper/math/trunk/src: java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java site/xdoc/userguide/analysis.xml test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
Date Wed, 01 Apr 2009 14:29:20 GMT
Author: luc
Date: Wed Apr  1 14:29:18 2009
New Revision: 760901

URL: http://svn.apache.org/viewvc?rev=760901&view=rev
Log:
removed the constraint on low degree polynomials
when building Chebyshev, Hermite, Laguerre or Legendre polynomials

Modified:
    commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
    commons/proper/math/trunk/src/site/xdoc/userguide/analysis.xml
    commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java?rev=760901&r1=760900&r2=760901&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
(original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
Wed Apr  1 14:29:18 2009
@@ -18,7 +18,7 @@
 
 import java.util.ArrayList;
 
-import org.apache.commons.math.fraction.Fraction;
+import org.apache.commons.math.fraction.BigFraction;
 
 /**
  * A collection of static methods that operate on or return polynomials.
@@ -29,46 +29,46 @@
 public class PolynomialsUtils {
 
     /** Coefficients for Chebyshev polynomials. */
-    private static final ArrayList<Fraction> CHEBYSHEV_COEFFICIENTS;
+    private static final ArrayList<BigFraction> CHEBYSHEV_COEFFICIENTS;
 
     /** Coefficients for Hermite polynomials. */
-    private static final ArrayList<Fraction> HERMITE_COEFFICIENTS;
+    private static final ArrayList<BigFraction> HERMITE_COEFFICIENTS;
 
     /** Coefficients for Laguerre polynomials. */
-    private static final ArrayList<Fraction> LAGUERRE_COEFFICIENTS;
+    private static final ArrayList<BigFraction> LAGUERRE_COEFFICIENTS;
 
     /** Coefficients for Legendre polynomials. */
-    private static final ArrayList<Fraction> LEGENDRE_COEFFICIENTS;
+    private static final ArrayList<BigFraction> LEGENDRE_COEFFICIENTS;
 
     static {
 
         // initialize recurrence for Chebyshev polynomials
         // T0(X) = 1, T1(X) = 0 + 1 * X
-        CHEBYSHEV_COEFFICIENTS = new ArrayList<Fraction>();
-        CHEBYSHEV_COEFFICIENTS.add(Fraction.ONE);
-        CHEBYSHEV_COEFFICIENTS.add(Fraction.ZERO);
-        CHEBYSHEV_COEFFICIENTS.add(Fraction.ONE);
+        CHEBYSHEV_COEFFICIENTS = new ArrayList<BigFraction>();
+        CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
+        CHEBYSHEV_COEFFICIENTS.add(BigFraction.ZERO);
+        CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
 
         // initialize recurrence for Hermite polynomials
         // H0(X) = 1, H1(X) = 0 + 2 * X
-        HERMITE_COEFFICIENTS = new ArrayList<Fraction>();
-        HERMITE_COEFFICIENTS.add(Fraction.ONE);
-        HERMITE_COEFFICIENTS.add(Fraction.ZERO);
-        HERMITE_COEFFICIENTS.add(Fraction.TWO);
+        HERMITE_COEFFICIENTS = new ArrayList<BigFraction>();
+        HERMITE_COEFFICIENTS.add(BigFraction.ONE);
+        HERMITE_COEFFICIENTS.add(BigFraction.ZERO);
+        HERMITE_COEFFICIENTS.add(BigFraction.TWO);
 
         // initialize recurrence for Laguerre polynomials
         // L0(X) = 1, L1(X) = 1 - 1 * X
-        LAGUERRE_COEFFICIENTS = new ArrayList<Fraction>();
-        LAGUERRE_COEFFICIENTS.add(Fraction.ONE);
-        LAGUERRE_COEFFICIENTS.add(Fraction.ONE);
-        LAGUERRE_COEFFICIENTS.add(Fraction.MINUS_ONE);
+        LAGUERRE_COEFFICIENTS = new ArrayList<BigFraction>();
+        LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
+        LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
+        LAGUERRE_COEFFICIENTS.add(BigFraction.MINUS_ONE);
 
         // initialize recurrence for Legendre polynomials
         // P0(X) = 1, P1(X) = 0 + 1 * X
-        LEGENDRE_COEFFICIENTS = new ArrayList<Fraction>();
-        LEGENDRE_COEFFICIENTS.add(Fraction.ONE);
-        LEGENDRE_COEFFICIENTS.add(Fraction.ZERO);
-        LEGENDRE_COEFFICIENTS.add(Fraction.ONE);
+        LEGENDRE_COEFFICIENTS = new ArrayList<BigFraction>();
+        LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
+        LEGENDRE_COEFFICIENTS.add(BigFraction.ZERO);
+        LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
 
     }
 
@@ -94,9 +94,9 @@
     public static PolynomialFunction createChebyshevPolynomial(final int degree) {
         return buildPolynomial(degree, CHEBYSHEV_COEFFICIENTS,
                 new RecurrenceCoefficientsGenerator() {
-            private final Fraction[] coeffs = { Fraction.ZERO, Fraction.TWO, Fraction.ONE};
+            private final BigFraction[] coeffs = { BigFraction.ZERO, BigFraction.TWO, BigFraction.ONE
};
             /** {@inheritDoc} */
-            public Fraction[] generate(int k) {
+            public BigFraction[] generate(int k) {
                 return coeffs;
             }
         });
@@ -120,11 +120,11 @@
         return buildPolynomial(degree, HERMITE_COEFFICIENTS,
                 new RecurrenceCoefficientsGenerator() {
             /** {@inheritDoc} */
-            public Fraction[] generate(int k) {
-                return new Fraction[] {
-                        Fraction.ZERO,
-                        Fraction.TWO,
-                        new Fraction(2 * k, 1)};
+            public BigFraction[] generate(int k) {
+                return new BigFraction[] {
+                        BigFraction.ZERO,
+                        BigFraction.TWO,
+                        new BigFraction(2 * k)};
             }
         });
     }
@@ -146,12 +146,12 @@
         return buildPolynomial(degree, LAGUERRE_COEFFICIENTS,
                 new RecurrenceCoefficientsGenerator() {
             /** {@inheritDoc} */
-            public Fraction[] generate(int k) {
+            public BigFraction[] generate(int k) {
                 final int kP1 = k + 1;
-                return new Fraction[] {
-                        new Fraction(2 * k + 1, kP1),
-                        new Fraction(-1, kP1),
-                        new Fraction(k, kP1)};
+                return new BigFraction[] {
+                        new BigFraction(2 * k + 1, kP1),
+                        new BigFraction(-1, kP1),
+                        new BigFraction(k, kP1)};
             }
         });
     }
@@ -173,12 +173,12 @@
         return buildPolynomial(degree, LEGENDRE_COEFFICIENTS,
                                new RecurrenceCoefficientsGenerator() {
             /** {@inheritDoc} */
-            public Fraction[] generate(int k) {
+            public BigFraction[] generate(int k) {
                 final int kP1 = k + 1;
-                return new Fraction[] {
-                        Fraction.ZERO,
-                        new Fraction(k + kP1, kP1),
-                        new Fraction(k, kP1)};
+                return new BigFraction[] {
+                        BigFraction.ZERO,
+                        new BigFraction(k + kP1, kP1),
+                        new BigFraction(k, kP1)};
             }
         });
     }
@@ -190,7 +190,7 @@
      * @return coefficients array
      */
     private static PolynomialFunction buildPolynomial(final int degree,
-                                                      final ArrayList<Fraction> coefficients,
+                                                      final ArrayList<BigFraction>
coefficients,
                                                       final RecurrenceCoefficientsGenerator
generator) {
 
         final int maxDegree = (int) Math.floor(Math.sqrt(2 * coefficients.size())) - 1;
@@ -228,7 +228,7 @@
      */
     private static void computeUpToDegree(final int degree, final int maxDegree,
                                           final RecurrenceCoefficientsGenerator generator,
-                                          final ArrayList<Fraction> coefficients) {
+                                          final ArrayList<BigFraction> coefficients)
{
 
         int startK = (maxDegree - 1) * maxDegree / 2;
         for (int k = maxDegree; k < degree; ++k) {
@@ -238,24 +238,24 @@
             startK += k;
 
             // Pk+1(X) = (a[0] + a[1] X) Pk(X) - a[2] Pk-1(X)
-            Fraction[] ai = generator.generate(k);
+            BigFraction[] ai = generator.generate(k);
 
-            Fraction ck     = coefficients.get(startK);
-            Fraction ckm1   = coefficients.get(startKm1);
+            BigFraction ck     = coefficients.get(startK);
+            BigFraction ckm1   = coefficients.get(startKm1);
 
             // degree 0 coefficient
             coefficients.add(ck.multiply(ai[0]).subtract(ckm1.multiply(ai[2])));
 
             // degree 1 to degree k-1 coefficients
             for (int i = 1; i < k; ++i) {
-                final Fraction ckPrev = ck;
+                final BigFraction ckPrev = ck;
                 ck     = coefficients.get(startK + i);
                 ckm1   = coefficients.get(startKm1 + i);
                 coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])).subtract(ckm1.multiply(ai[2])));
             }
 
             // degree k coefficient
-            final Fraction ckPrev = ck;
+            final BigFraction ckPrev = ck;
             ck = coefficients.get(startK + k);
             coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])));
 
@@ -274,7 +274,7 @@
          * @return an array of three coefficients such that
          * P<sub>k+1</sub>(X) = (a[0] + a[1] X) P<sub>k</sub>(X)
- a[2] P<sub>k-1</sub>(X)
          */
-        Fraction[] generate(int k);
+        BigFraction[] generate(int k);
     }
 
 }

Modified: commons/proper/math/trunk/src/site/xdoc/userguide/analysis.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/userguide/analysis.xml?rev=760901&r1=760900&r2=760901&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/userguide/analysis.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/userguide/analysis.xml Wed Apr  1 14:29:18 2009
@@ -324,9 +324,8 @@
           one, using traditional coefficients arrays. The <a
           href="../apidocs/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.html">
           org.apache.commons.math.analysis.polynomials.PolynomialsUtils</a> utility
class provides static
-          factory methods to build Chebyshev, Hermite, Lagrange and Legendre polynomials.
Beware that due
-          to overflows in the coefficients computations, these factory methods can only build
low degrees
-          polynomials yet.
+          factory methods to build Chebyshev, Hermite, Lagrange and Legendre polynomials.
Coefficients
+          are computed using exact fractions so these factory methods can build polynomials
up to any degree.
         </p>
       </subsection>
     </section>

Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java?rev=760901&r1=760900&r2=760901&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
(original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
Wed Apr  1 14:29:18 2009
@@ -177,34 +177,25 @@
     }
 
     public void testHighDegreeLegendre() {
-        try {
-            PolynomialsUtils.createLegendrePolynomial(40);
-            fail("an exception should have been thrown");
-        } catch (ArithmeticException ae) {
-            // expected
+        PolynomialsUtils.createLegendrePolynomial(40);
+        double[] l40 = PolynomialsUtils.createLegendrePolynomial(40).getCoefficients();
+        double denominator = 274877906944.0;
+        double[] numerators = new double[] {
+                          +34461632205.0,            -28258538408100.0,          +3847870979902950.0,
       -207785032914759300.0,
+                  +5929294332103310025.0,     -103301483474866556880.0,    +1197358103913226000200.0,
   -9763073770369381232400.0,
+              +58171647881784229843050.0,  -260061484647976556945400.0,  +888315281771246239250340.0,
-2345767627188139419665400.0,
+            +4819022625419112503443050.0, -7710436200670580005508880.0, +9566652323054238154983240.0,
-9104813935044723209570256.0,
+            +6516550296251767619752905.0, -3391858621221953912598660.0, +1211378079007840683070950.0,
 -265365894974690562152100.0,
+              +26876802183334044115405.0
+        };
+        for (int i = 0; i < l40.length; ++i) {
+            if (i % 2 == 0) {
+                double ci = numerators[i / 2] / denominator;
+                assertEquals(ci, l40[i], ci * 1.0e-15);
+            } else {
+                assertEquals(0.0, l40[i], 0.0);
+            }
         }
-//        checkPolynomial(PolynomialsUtils.createLegendrePolynomial(40), 274877906944l,
-//                        "34461632205.0"
-//                      + " - 28258538408100.0 x^2"
-//                      + " + 3847870979902950.0 x^4"
-//                      + " - 207785032914759300.0 x^6"
-//                      + " + 5929294332103310025.0 x^8"
-//                      + " - 103301483474866556880.0 x^10"
-//                      + " + 1197358103913226000200.0 x^12"
-//                      + " - 9763073770369381232400.0 x^14"
-//                      + " + 58171647881784229843050.0 x^16"
-//                      + " - 260061484647976556945400.0 x^18"
-//                      + " + 888315281771246239250340.0 x^20"
-//                      + " - 2345767627188139419665400.0 x^22"
-//                      + " + 4819022625419112503443050.0 x^24"
-//                      + " - 7710436200670580005508880.0 x^26"
-//                      + " + 9566652323054238154983240.0 x^28"
-//                      + " - 9104813935044723209570256.0 x^30"
-//                      + " + 6516550296251767619752905.0 x^32"
-//                      + " - 3391858621221953912598660.0 x^34"
-//                      + " + 1211378079007840683070950.0 x^36"
-//                      + " - 265365894974690562152100.0 x^38"
-//                      + " + 26876802183334044115405.0 x^40");
     }
 
     private void checkPolynomial(PolynomialFunction p, long denominator, String reference)
{



Mime
View raw message