You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2013/11/04 14:50:19 UTC
svn commit: r1538605 - in /sis/branches/JDK7/core/sis-utility/src:
main/java/org/apache/sis/internal/util/ main/java/org/apache/sis/math/
main/java/org/apache/sis/util/ test/java/org/apache/sis/internal/util/
test/java/org/apache/sis/math/
Author: desruisseaux
Date: Mon Nov 4 13:50:19 2013
New Revision: 1538605
URL: http://svn.apache.org/r1538605
Log:
Precompute all values of 10^n. This consume 5 kb of memory, but simplify the code and guaranteed performance.
The performance issue was not a concern for fractionDigitsForDelta and fractionDigitsForValue, because those
methods are invoked only once for a dataset. But performance become more an issue for floatToDouble and the
upcomming method for completing the error term in double-double arithmetic (to be committed later), since
those methods will be invoked for all data values instead than for the dataset.
Modified:
sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/internal/util/Numerics.java
sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/DecimalFunctions.java
sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/MathFunctions.java
sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/util/Numbers.java
sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/internal/util/NumericsTest.java
sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/math/DecimalFunctionsTest.java
Modified: sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/internal/util/Numerics.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/internal/util/Numerics.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/internal/util/Numerics.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/internal/util/Numerics.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -260,6 +260,12 @@ public final class Numerics extends Stat
* for the range of {@code double} exponents. We do not put this method in public API because it
* does not check the argument validity.
*
+ * {@section Arithmetic notes}
+ * {@code toExp10(getExponent(10ⁿ))} returns <var>n</var> only for {@code n == 0}, and <var>n</var>-1 in all other
+ * cases. This is because 10ⁿ == m × 2<sup>exp2</sup> where the <var>m</var> significand is always greater than 1,
+ * which must be compensated by a smaller {@code exp2} value such as {@code toExp10(exp2) < n}. Note that if the
+ * {@code getExponent(…)} argument is not a power of 10, then the result can be either <var>n</var> or <var>n</var>-1.
+ *
* @param exp2 The power of 2 to convert Must be in the [-2620 … 2620] range.
* @return The power of 10, rounded toward negative infinity.
*
Modified: sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/DecimalFunctions.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/DecimalFunctions.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/DecimalFunctions.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/DecimalFunctions.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -16,7 +16,6 @@
*/
package org.apache.sis.math;
-import java.util.Arrays;
import org.apache.sis.util.Static;
import org.apache.sis.util.Workaround;
import org.apache.sis.internal.util.Numerics;
@@ -26,6 +25,9 @@ import static org.apache.sis.internal.ut
/**
* Functions working of {@code float} and {@code double} values while taking in account the representation in base 10.
+ * Methods in this class may be helpful when used immediately after parsing (i.e. before any calculations are applied
+ * on the value), or just before formatting a number in base 10. Methods in this class are usually <strong>not</strong>
+ * recommended for intermediate calculations, since base 10 is not more "real" than base 2 for natural phenomenon.
*
* @author Martin Desruisseaux (Geomatys)
* @since 0.4
@@ -46,17 +48,34 @@ public final class DecimalFunctions exte
static final int EXPONENT_FOR_ZERO = -324;
/**
- * Table of some integer powers of 10. Used for faster computation in {@link #pow10(int)}.
+ * The maximal exponent value such as {@code parseDouble("1E+308")} still a finite number.
+ *
+ * @see Double#MAX_VALUE
+ */
+ static final int EXPONENT_FOR_MAX = 308;
+
+ /**
+ * Table of integer powers of 10, precomputed both for performance and accuracy reasons.
+ * This table consumes 4.9 kb of memory. We pay this cost because integer powers of ten
+ * are requested often, and {@link Math#pow(double, double)} has slight rounding errors.
*
* @see #pow10(int)
*/
- private static final double[] POW10 = {
- 1E+00, 1E+01, 1E+02, 1E+03, 1E+04, 1E+05, 1E+06, 1E+07, 1E+08, 1E+09,
- 1E+10, 1E+11, 1E+12, 1E+13, 1E+14, 1E+15, 1E+16, 1E+17, 1E+18, 1E+19,
- 1E+20, 1E+21, 1E+22
- // Do not add more elements, unless we verified that 1/x is accurate.
- // Last time we tried, it was not accurate anymore starting at 1E+23.
- };
+ @Workaround(library="JDK", version="1.4")
+ private static final double[] POW10 = new double[EXPONENT_FOR_MAX - EXPONENT_FOR_ZERO];
+ static {
+ final StringBuilder buffer = new StringBuilder("1E");
+ for (int i=0; i<POW10.length; i++) {
+ buffer.setLength(2);
+ buffer.append(i + (EXPONENT_FOR_ZERO + 1));
+ /*
+ * Double.parseDouble("1E"+i) gives as good or better numbers than Math.pow(10,i)
+ * for ALL integer powers, but is slower. We hope that the current workaround is only
+ * temporary. See http://developer.java.sun.com/developer/bugParade/bugs/4358794.html
+ */
+ POW10[i] = Double.parseDouble(buffer.toString());
+ }
+ }
/**
* Do not allow instantiation of this class.
@@ -65,6 +84,19 @@ public final class DecimalFunctions exte
}
/**
+ * Computes 10 raised to the power of <var>x</var>. This is the implementation of the
+ * public {@link MathFunctions#pow10(int)} method, defined here in order to allow the
+ * JVM to initialize the {@link #POW10} table only when first needed.
+ *
+ * @param x The exponent.
+ * @return 10 raised to the given exponent.
+ */
+ static double pow10(int x) {
+ x -= EXPONENT_FOR_ZERO + 1;
+ return (x >= 0) ? (x < POW10.length ? POW10[x] : Double.POSITIVE_INFINITY) : 0;
+ }
+
+ /**
* Converts the given {@code float} value to a {@code double} with the extra <em>decimal</em> fraction digits
* set to zero. This is different than the standard cast in the Java language, which set the extra <em>binary</em>
* fraction digits to zero.
@@ -72,11 +104,24 @@ public final class DecimalFunctions exte
*
* {@note This method is <strong>not</strong> more accurate than the standard Java cast —
* it is only more intuitive for human used to base 10.
- * If the value come directly from an ASCII file or a user input, then this method may be useful
- * because the value was probably expressed in base 10 before conversion to a <code>float</code>.
+ * If the value come from a call to <code>Float.parseFloat(String)</code> (directly or indirectly),
+ * and if that call can not be replaced by a call to <code>Double.parseDouble(String)</code>, then
+ * this method may be useful since the definitive <code>String</code> value was expressed in base 10.
* But if the value come from an instrument measurement or a calculation, then there is probably
* no reason to use this method because base 10 is not more "real" than base 2 or any other base
- * for natural phenomenon.}
+ * for natural phenomenon.
+ *
+ * <p><b>Use case:</b></p>
+ * <ul>
+ * <li>Producer A provides data in ASCII files using less fraction digits than the <code>float</code>
+ * storage capability. This is not uncommon when the primary accuracy constraint is the instrument
+ * precision.</li>
+ * <li>Producer B converts the above ASCII files to the NetCDF binary format for efficiency, with data
+ * stored as <code>float</code> values. Producer B does not distribute the original ASCII files.</li>
+ * <li>Client of producer B wants to use those data with a library working with <code>double</code> values.
+ * For some reason (e.g. formatting), the client wants the same values as if the ASCII files had been
+ * parsed with <code>Double.parseDouble(String)</code> in the first place.</li>
+ * </ul>}
*
* This method is equivalent to the following code, except that it is potentially faster since the
* actual implementation avoid to format and parse the value:
@@ -186,34 +231,17 @@ public final class DecimalFunctions exte
*/
public static int fractionDigitsForDelta(double accuracy, final boolean strict) {
accuracy = Math.abs(accuracy);
- final boolean isFraction = (accuracy < 1);
- /*
- * Compute (int) Math.log10(x) with opportunist use of the POW10 array.
- * We use the POW10 array because accurate calculation of log10 is relatively costly,
- * while we only want the integer part. A micro-benchmarking on JDK7 suggested that a
- * binary search on POW10 is about 30% faster than invoking (int) Math.log10(x).
- */
- int i = Arrays.binarySearch(POW10, isFraction ? 1/accuracy : accuracy);
- if (i >= 0) {
- return isFraction ? i : -i;
+ int i = MathFunctions.getExponent(accuracy);
+ if (i == Double.MAX_EXPONENT + 1) {
+ return 0; // NaN or infinities.
}
- i = ~i;
- double scale;
- if (i < POW10.length) {
- scale = POW10[i];
- if (!isFraction) {
- i = -(i-1);
- scale = 10 / scale;
- }
- } else { // 'x' is out of range or NaN.
- final double y = Math.log10(accuracy);
- if (Double.isInfinite(y)) {
- return (accuracy == 0) ? -EXPONENT_FOR_ZERO : 0;
- }
- i = -((int) Math.floor(y));
- scale = pow10(i);
+ i = Numerics.toExp10(i);
+ if (accuracy >= pow10(i+1)) {
+ i++;
}
+ i = -i;
if (strict) {
+ double scale = pow10(i);
while ((accuracy *= scale) >= 9.5) {
i++; // The 0.…95 special case.
accuracy -= Math.floor(accuracy);
@@ -268,64 +296,4 @@ public final class DecimalFunctions exte
}
return 0;
}
-
- /**
- * Computes 10 raised to the power of <var>x</var>. This method delegates to
- * <code>{@linkplain #pow10(int) pow10}((int) x)</code> if <var>x</var> is an
- * integer, or to <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>
- * otherwise.
- *
- * @param x The exponent.
- * @return 10 raised to the given exponent.
- *
- * @see #pow10(int)
- * @see Math#pow(double, double)
- */
- static double pow10(final double x) {
- final int ix = (int) x;
- if (ix == x) {
- return pow10(ix);
- } else {
- return Math.pow(10, x);
- }
- }
-
- /**
- * Computes 10 raised to the power of <var>x</var>. This method tries to be slightly more
- * accurate than <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>,
- * sometime at the cost of performance.
- *
- * {@note This method has been defined because the standard <code>Math.pow(10, x)</code>
- * method does not always return the closest IEEE floating point representation.
- * Slight departures (1 or 2 ULP) are often allowed in math functions for performance
- * reasons. The most accurate calculations are usually not necessary, but the base 10
- * is a special case since it is used for scaling axes or formatting human-readable
- * output.}
- *
- * @param x The exponent.
- * @return 10 raised to the given exponent.
- */
- @Workaround(library="JDK", version="1.4")
- static double pow10(final int x) {
- if (x >= 0) {
- if (x < POW10.length) {
- return POW10[x];
- }
- } else if (x != Integer.MIN_VALUE) {
- final int nx = -x;
- if (nx < POW10.length) {
- return 1 / POW10[nx];
- }
- }
- try {
- /*
- * Double.parseDouble("1E"+x) gives as good or better numbers than Math.pow(10,x)
- * for ALL integer powers, but is slower. We hope that the current workaround is only
- * temporary. See http://developer.java.sun.com/developer/bugParade/bugs/4358794.html
- */
- return Double.parseDouble("1E" + x);
- } catch (NumberFormatException exception) {
- return StrictMath.pow(10, x);
- }
- }
}
Modified: sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/MathFunctions.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/MathFunctions.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/MathFunctions.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/math/MathFunctions.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -19,7 +19,6 @@ package org.apache.sis.math;
import java.util.Arrays;
import org.apache.sis.util.Static;
import org.apache.sis.util.ArraysExt;
-import org.apache.sis.util.Workaround;
import org.apache.sis.util.ArgumentChecks;
import org.apache.sis.util.resources.Errors;
import org.apache.sis.internal.util.DoubleDouble;
@@ -79,20 +78,6 @@ public final class MathFunctions extends
* double exp10 = exp2 * LOG10_2;
* }
*
- * <blockquote><font size="-1">
- * <b>Tip:</b> for <em>integer</em> values in the [-2620 … 2620] range, the following expression:
- *
- * {@preformat java
- * int exp10 = (int) Math.floor(exp2 * LOG10_2);
- * }
- *
- * can be approximated using only integer arithmetic by:
- *
- * {@preformat java
- * int exp10 = (exp2 * 315653) >> 20;
- * }
- * </font></blockquote>
- *
* @see Math#log10(double)
* @see #getExponent(double)
*
@@ -292,10 +277,9 @@ public final class MathFunctions extends
}
/**
- * Computes 10 raised to the power of <var>x</var>. This method delegates to
- * <code>{@linkplain #pow10(int) pow10}((int) x)</code> if <var>x</var> is an
- * integer, or to <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>
- * otherwise.
+ * Computes 10 raised to the power of <var>x</var>. Invoking this method is equivalent to invoking
+ * <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>, but is slightly more accurate
+ * in the special case where the given argument is an integer.
*
* @param x The exponent.
* @return 10 raised to the given exponent.
@@ -304,13 +288,17 @@ public final class MathFunctions extends
* @see Math#pow(double, double)
*/
public static double pow10(final double x) {
- return DecimalFunctions.pow10(x);
+ final int ix = (int) x;
+ if (ix == x) {
+ return DecimalFunctions.pow10(ix);
+ } else {
+ return Math.pow(10, x);
+ }
}
/**
- * Computes 10 raised to the power of <var>x</var>. This method tries to be slightly more
- * accurate than <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>,
- * sometime at the cost of performance.
+ * Computes 10 raised to the power of <var>x</var>. This method is faster and slightly more accurate
+ * than invoking <code>{@linkplain Math#pow(double, double) Math.pow}(10, x)</code>.
*
* {@note This method has been defined because the standard <code>Math.pow(10, x)</code>
* method does not always return the closest IEEE floating point representation.
@@ -322,7 +310,6 @@ public final class MathFunctions extends
* @param x The exponent.
* @return 10 raised to the given exponent.
*/
- @Workaround(library="JDK", version="1.4")
public static double pow10(final int x) {
return DecimalFunctions.pow10(x);
}
Modified: sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/util/Numbers.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/util/Numbers.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/util/Numbers.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/main/java/org/apache/sis/util/Numbers.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -159,21 +159,6 @@ public final class Numbers extends Stati
}
/**
- * Returns {@code true} if the given {@code type} is an integer type. This method performs
- * the same test than {@link #isPrimitiveInteger}, excluding {@link BigInteger}.
- *
- * @param type The type to test (may be {@code null}).
- * @return {@code true} if {@code type} is the primitive of wrapper class of
- * {@link Long}, {@link Integer}, {@link Short} or {@link Byte}.
- *
- * @see #isInteger(Class)
- */
- private static boolean isPrimitiveInteger(final Class<?> type) {
- final Numbers mapping = MAPPING.get(type);
- return (mapping != null) && mapping.isInteger && (mapping.internal != 'L');
- }
-
- /**
* Returns the number of bits used by primitive of the specified type.
* The given type must be a primitive type or its wrapper class.
*
@@ -274,17 +259,16 @@ public final class Numbers extends Stati
final Class<? extends Number> c2)
throws IllegalArgumentException
{
+ if (c1 == null) return c2;
+ if (c2 == null) return c1;
final Numbers m1 = MAPPING.get(c1);
- if (m1 == null && c1 != null) {
+ if (m1 == null) {
throw unknownType(c1);
}
final Numbers m2 = MAPPING.get(c2);
- if (m2 == null && c2 != null) {
+ if (m2 == null) {
throw unknownType(c2);
}
- if (c1 == null) return c2;
- if (c2 == null) return c1;
- // At this point, m1 and m2 can not be null.
return (m1.ordinal >= m2.ordinal) ? c1 : c2;
}
@@ -336,17 +320,16 @@ public final class Numbers extends Stati
final Class<? extends Number> c2)
throws IllegalArgumentException
{
+ if (c1 == null) return c2;
+ if (c2 == null) return c1;
final Numbers m1 = MAPPING.get(c1);
- if (m1 == null && c1 != null) {
+ if (m1 == null) {
throw unknownType(c1);
}
final Numbers m2 = MAPPING.get(c2);
- if (m2 == null && c2 != null) {
+ if (m2 == null) {
throw unknownType(c2);
}
- if (c1 == null) return c2;
- if (c2 == null) return c1;
- // At this point, m1 and m2 can not be null.
return (m1.ordinal < m2.ordinal) ? c1 : c2;
}
Modified: sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/internal/util/NumericsTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/internal/util/NumericsTest.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/internal/util/NumericsTest.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/internal/util/NumericsTest.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -56,14 +56,19 @@ public final strictfp class NumericsTest
}
/**
- * Tests the {@link Numerics#toExp10(int)} method over the full [-2620 … 2620] range of values.
- * This is the range documented as valid.
+ * Tests the {@link Numerics#toExp10(int)} method over the full [-2620 … 2620] range of values
+ * (the validity range documented by method javadoc). Also verifies our javadoc claim that
+ * {@code toExp10(getExponent(10ⁿ))} returns {@code n-1} except for {@code n == 0}.
*/
@Test
public void testToExp10() {
for (int i=-2620; i<=2620; i++) {
assertEquals(Math.floor(i * MathFunctions.LOG10_2), toExp10(i), 0);
}
+ for (int i=-307; i<=308; i++) {
+ final String value = "1E" + i;
+ assertEquals(value, (i == 0) ? i : i-1, toExp10(StrictMath.getExponent(Double.parseDouble(value))));
+ }
}
/**
Modified: sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/math/DecimalFunctionsTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/math/DecimalFunctionsTest.java?rev=1538605&r1=1538604&r2=1538605&view=diff
==============================================================================
--- sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/math/DecimalFunctionsTest.java [UTF-8] (original)
+++ sis/branches/JDK7/core/sis-utility/src/test/java/org/apache/sis/math/DecimalFunctionsTest.java [UTF-8] Mon Nov 4 13:50:19 2013
@@ -20,6 +20,7 @@ import java.util.Random;
import org.junit.Test;
import org.apache.sis.test.TestCase;
import org.apache.sis.test.DependsOn;
+import org.apache.sis.test.DependsOnMethod;
import org.apache.sis.test.TestUtilities;
import static org.junit.Assert.*;
@@ -40,13 +41,6 @@ import static org.apache.sis.math.Decima
})
public final strictfp class DecimalFunctionsTest extends TestCase {
/**
- * The maximal exponent value such as {@code parseDouble("1E+308")} still a finite number.
- *
- * @see Double#MAX_VALUE
- */
- private static final int EXPONENT_FOR_MAX = 308;
-
- /**
* Verifies the values of {@link DecimalFunctions#EXPONENT_FOR_ZERO}.
*/
@Test
@@ -58,9 +52,22 @@ public final strictfp class DecimalFunct
}
/**
+ * Tests the {@link MathFunctions#pow10(double)} method.
+ * This will indirectly test {@link MathFunctions#pow10(int)}
+ * since the former will delegate to the later in this test.
+ */
+ @Test
+ public void testPow10() {
+ for (int i=EXPONENT_FOR_ZERO; i<=EXPONENT_FOR_MAX; i++) { // Range of allowed exponents in base 10.
+ assertEquals(parseDouble("1E"+i), pow10(i), 0);
+ }
+ }
+
+ /**
* Tests {@link DecimalFunctions#floatToDouble(float)}.
*/
@Test
+ @DependsOnMethod("testPow10")
public void testFloatToDouble() {
assertEquals(10, floatToDouble(10f), 0);
assertEquals(0.1, floatToDouble(0.1f), 0);
@@ -80,6 +87,7 @@ public final strictfp class DecimalFunct
* Tests {@link DecimalFunctions#fractionDigitsForDelta(double, boolean)}.
*/
@Test
+ @DependsOnMethod("testPow10")
public void testFractionDigitsForDelta() {
assertEquals(3, fractionDigitsForDelta(0.001, true));
assertEquals(3, fractionDigitsForDelta(0.009, true));
@@ -150,16 +158,4 @@ public final strictfp class DecimalFunct
assertEquals("Shall not be greater than ULP", 0, accuracy, StrictMath.ulp(value));
}
}
-
- /**
- * Tests the {@link MathFunctions#pow10(double)} method.
- * This will indirectly test {@link MathFunctions#pow10(int)}
- * since the former will delegate to the later in this test.
- */
- @Test
- public void testPow10() {
- for (int i=EXPONENT_FOR_ZERO; i<=EXPONENT_FOR_MAX; i++) { // Range of allowed exponents in base 10.
- assertEquals(parseDouble("1E"+i), pow10((double) i), 0);
- }
- }
}