Class Real

  • All Implemented Interfaces:
    java.io.Serializable

    @GwtIncompatible("No javascript support for strictfp.")
    class Real
    extends java.lang.Number
    This class provides portable support for several exact arithmetic operations on double values, without loss of precision. It stores an array of double values, and operations that require additional bits of precision return Reals with larger arrays.

    Converting a sequence of a dozen strictfp arithmetic operations to use Real can take up to 20 times longer than the natural but imprecise approach of using built in double operators like + and *. Compared to other approaches like BigDecimal that consume more memory and typically slow operations down by a factor of 100, that's great, but use of this class should still be avoided when imprecise results will suffice.

    This class exists as a package private element of the geometry library for the predicates in S2Predicates, that require arbitrary precision arithmetic. It could be made suitable for general usage by adding robust implementations of multiplication and division between two Reals, and a toString() implementation that prints the exact summation of all the components.

    Many of the algorithms in this class were adapted from the multiple components technique for extended 64-bit IEEE 754 floating point precision, as described in:

     Robust Adaptive Floating-Point Geometric Predicates
     Jonathan Richard Shewchuk
     School of Computer Science
     Carnegie Mellon University
     

    Faster adaptive techniques are also presented in that paper, but are not implemented here.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static long serialVersionUID  
      private static double SPLITTER
      Used to split doubles into two half-length values, for exact multiplication.
      private double[] values
      A sequence of ordinary double values, ordered by magnitude in ascending order, containing no zeroes and with no overlapping base 2 digits.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        Real​(double value)
      Creates a Real based on the given double value.
      private Real​(double... values)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static Real add​(double a, double b)
      Returns the result of a + b, without loss of precision.
      Real add​(Real that)
      Returns the result of a + b, without loss of precision.
      private static Real add​(Real a, Real b, boolean negateB)
      Returns the result of adding together the components of a and b, inverting each element of b if negateB is true.
      java.math.BigDecimal bigValue()
      Returns a BigDecimal representation of this extended precision real value.
      private static double[] copyOf​(double[] array, int newLength)  
      double doubleValue()  
      private static double fastTwoSumError​(double a, double b, double x)
      Returns the error in the sum x=a+b, when |a|>=|b|.
      float floatValue()  
      int intValue()  
      long longValue()  
      Real mul​(double scale)
      Returns the result of this * scale, without loss of precision.
      static Real mul​(double a, double b)
      Returns the result of a * b, without loss of precision.
      Real negate()
      Returns the negative of this number.
      int signum()
      Returns the signum of this number more quickly than via Math.signum(doubleValue()).
      private static boolean smallerMagnitude​(double a, double b)
      Returns true if the magnitude of a is less than the magnitude of b.
      private static double splitHigh​(double a)
      Returns the high split for the given value.
      private static double splitLow​(double a, double ahi)
      Returns the low split for the given value and previously-computed high split as returned by splitHigh(double).
      static Real sub​(double a, double b)
      Returns the result of a - b, without loss of precision.
      Real sub​(Real that)
      Returns the result of a - b, without loss of precision.
      java.lang.String toString()
      Returns the string representation of the double value nearest this Real.
      private static double twoDiffError​(double a, double b, double x)
      Returns the error in the difference x=a-b.
      private static double twoProductError​(double a, double bhi, double blo, double x)
      Returns the error in the product x=a*b, with precomputed splits for b.
      private static double twoSumError​(double a, double b, double x)
      Returns the error in the sum x=a+b, when the relative magnitudes of a and b are not known in advance.
      • Methods inherited from class java.lang.Number

        byteValue, shortValue
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • SPLITTER

        private static final double SPLITTER
        Used to split doubles into two half-length values, for exact multiplication. The value should be Math.pow(2, Math.ceil(mantissaBits / 2)) + 1.
      • values

        private final double[] values
        A sequence of ordinary double values, ordered by magnitude in ascending order, containing no zeroes and with no overlapping base 2 digits.
    • Constructor Detail

      • Real

        public Real​(double value)
        Creates a Real based on the given double value.
      • Real

        private Real​(double... values)
    • Method Detail

      • add

        public static Real add​(double a,
                               double b)
        Returns the result of a + b, without loss of precision.
      • sub

        public static Real sub​(double a,
                               double b)
        Returns the result of a - b, without loss of precision.
      • mul

        public static Real mul​(double a,
                               double b)
        Returns the result of a * b, without loss of precision.
      • add

        public Real add​(Real that)
        Returns the result of a + b, without loss of precision.
      • sub

        public Real sub​(Real that)
        Returns the result of a - b, without loss of precision.
      • add

        private static Real add​(Real a,
                                Real b,
                                boolean negateB)
        Returns the result of adding together the components of a and b, inverting each element of b if negateB is true.
      • smallerMagnitude

        private static boolean smallerMagnitude​(double a,
                                                double b)
        Returns true if the magnitude of a is less than the magnitude of b.
      • mul

        public Real mul​(double scale)
        Returns the result of this * scale, without loss of precision.
      • negate

        public Real negate()
        Returns the negative of this number.
      • signum

        public int signum()
        Returns the signum of this number more quickly than via Math.signum(doubleValue()).
      • toString

        public java.lang.String toString()
        Returns the string representation of the double value nearest this Real.
        Overrides:
        toString in class java.lang.Object
      • intValue

        public int intValue()
        Specified by:
        intValue in class java.lang.Number
      • longValue

        public long longValue()
        Specified by:
        longValue in class java.lang.Number
      • floatValue

        public float floatValue()
        Specified by:
        floatValue in class java.lang.Number
      • doubleValue

        public double doubleValue()
        Specified by:
        doubleValue in class java.lang.Number
      • bigValue

        public java.math.BigDecimal bigValue()
        Returns a BigDecimal representation of this extended precision real value.
      • copyOf

        private static double[] copyOf​(double[] array,
                                       int newLength)
      • fastTwoSumError

        private static double fastTwoSumError​(double a,
                                              double b,
                                              double x)
        Returns the error in the sum x=a+b, when |a|>=|b|.
      • twoSumError

        private static double twoSumError​(double a,
                                          double b,
                                          double x)
        Returns the error in the sum x=a+b, when the relative magnitudes of a and b are not known in advance.
      • twoDiffError

        private static double twoDiffError​(double a,
                                           double b,
                                           double x)
        Returns the error in the difference x=a-b.
      • splitHigh

        private static double splitHigh​(double a)
        Returns the high split for the given value.
      • splitLow

        private static double splitLow​(double a,
                                       double ahi)
        Returns the low split for the given value and previously-computed high split as returned by splitHigh(double).
      • twoProductError

        private static double twoProductError​(double a,
                                              double bhi,
                                              double blo,
                                              double x)
        Returns the error in the product x=a*b, with precomputed splits for b.