Module org.dyn4j

Class AdaptiveDecimal


  • class AdaptiveDecimal
    extends java.lang.Object
    This is an implementation of multi-precision decimals based on the original work by Jonathan Richard Shewchuk, "Routines for Arbitrary Precision Floating-point Arithmetic and Fast Robust Geometric Predicates".

    More information about the algorithms, the original code in C and proofs of correctness can all be found at http://www.cs.cmu.edu/~quake/robust.html

    Short description: The value of this AdaptiveDecimal is represented as the sum of some components, where each component is a double value. The components must be stored in increasing magnitude order, but there can be any amount of zeros between components. The components must also satisfy the non-overlapping property, that is the corresponding bit representation of adjacent components must not overlap. See checkInvariants() and the corresponding paper for more info.

    This code requires that the floating point model is IEEE-754 with round-to-even in order to work properly in all cases and fulfill the above properties. This is not a problem because this is the default and only model the Java specification describes.

    Since:
    3.4.0
    Version:
    3.4.0
    Author:
    Manolis Tsamis
    • Constructor Detail

      • AdaptiveDecimal

        public AdaptiveDecimal​(int length)
        Creates a new AdaptiveDecimal with the specified length. The initial AdaptiveDecimal created does not contains any components.
        Parameters:
        length - The maximum number of components this AdaptiveDecimal can store
      • AdaptiveDecimal

        protected AdaptiveDecimal​(double a0,
                                  double a1)
        Internal helper constructor to create a AdaptiveDecimal with two components
        Parameters:
        a0 - the component with the smallest magnitude
        a1 - the component with the largest magnitude
    • Method Detail

      • size

        public int size()
        Returns:
        The number of components this AdaptiveDecimal currently has
      • capacity

        public int capacity()
        Returns:
        The maximum number of components this AdaptiveDecimal can hold
      • get

        public double get​(int index)
        Parameters:
        index - index of the component to return
        Returns:
        the component at the specified position
        Throws:
        java.lang.IndexOutOfBoundsException - if the index is not in the range [0, size)
      • append

        public AdaptiveDecimal append​(double value)
        Appends a new component after all the existing components.
        Parameters:
        value - The component
        Returns:
        this AdaptiveDecimal
        Throws:
        java.lang.IndexOutOfBoundsException - if this AdaptiveDecimal has no capacity for more components
      • appendNonZero

        public AdaptiveDecimal appendNonZero​(double value)
        Appends a new component after all the existing components, but only if it has a non zero value.
        Parameters:
        value - The component
        Returns:
        this AdaptiveDecimal
      • checkInvariants

        public boolean checkInvariants()
        Returns a boolean value describing if this AdaptiveDecimal is a valid representation as described in the header of this class. Checks for the magnitude and non-overlapping property. The invariants can be violated if bad input components are appended to this AdaptiveDecimal. The append methods do not check for those conditions because there is a big overhead for the check. The output of the exposed operations must satisfy the invariants, given that their input also does so.
        Returns:
        true iff this AdaptiveDecimal satisfies the described invariants
      • ensureInvariants

        public void ensureInvariants()
        Throws:
        java.lang.IllegalStateException - iff checkInvariants() returns false
      • getEstimation

        public double getEstimation()
        Computes an approximation for the value of this AdaptiveDecimal that fits in a double.
        Returns:
        The approximation
      • sumEpilogue

        AdaptiveDecimal sumEpilogue​(double carry,
                                    AdaptiveDecimal e,
                                    int eIndex,
                                    AdaptiveDecimal result)
        Helper method to implement the sum procedure. Sums the remaining components of a single AdaptiveDecimal to the result and the initial carry value from previous computations
        Parameters:
        carry - The carry from previous computations
        e - The AdaptiveDecimal that probably has more components
        eIndex - The index to the next component of e that has to be examined
        result - The AdaptiveDecimal in which the result is stored
        Returns:
        The result
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • fromSum

        public static AdaptiveDecimal fromSum​(double a,
                                              double b)
        Creates a AdaptiveDecimal that holds the result of the addition of two double values.
        Parameters:
        a - The first value
        b - The second value
        Returns:
        A new AdaptiveDecimal that holds the resulting sum
      • fromDiff

        public static AdaptiveDecimal fromDiff​(double a,
                                               double b)
        Creates a AdaptiveDecimal that holds the result of the difference of two double values.
        Parameters:
        a - The first value
        b - The second value
        Returns:
        A new AdaptiveDecimal that holds the resulting difference
      • fromDiff

        static AdaptiveDecimal fromDiff​(double a0,
                                        double a1,
                                        double b0,
                                        double b1,
                                        AdaptiveDecimal result)
        Given two unrolled expansions (a0, a1) and (b0, b1) performs the difference (a0, a1) - (b0, b1) and stores the 4 component result in the given AdaptiveDecimal result. In the same way as with sum(AdaptiveDecimal, AdaptiveDecimal) if result is null a new one is allocated, otherwise the existing is cleared and used. Does not perform zero elimination. This is also a helper method to allow fast computation of the cross product without the overhead of creating new AdaptiveDecimal and performing the generalized sum procedure.
        Parameters:
        a0 - The first component of a
        a1 - The second component of a
        b0 - The first component of b
        b1 - The second component of b
        result - The AdaptiveDecimal in which the difference is stored or null to allocate a new one
        Returns:
        The result
      • fromProduct

        public static AdaptiveDecimal fromProduct​(double a,
                                                  double b)
        Creates a AdaptiveDecimal that holds the result of the product of two double values.
        Parameters:
        a - The first value
        b - The second value
        Returns:
        A new AdaptiveDecimal that holds the resulting product
      • getErrorComponentFromSum

        static double getErrorComponentFromSum​(double a,
                                               double b,
                                               double sum)
        Given two values a, b and their sum = fl(a + b) calculates the value error for which fl(a) + fl(b) = fl(a + b) + fl(error).
        Parameters:
        a - The first value
        b - The second value
        sum - Their sum, must always be sum = fl(a + b)
        Returns:
        The error described above
      • getErrorComponentFromDifference

        static double getErrorComponentFromDifference​(double a,
                                                      double b,
                                                      double diff)
        Given two values a, b and their difference = fl(a - b) calculates the value error for which fl(a) - fl(b) = fl(a - b) + fl(error).
        Parameters:
        a - The first value
        b - The second value
        diff - Their difference, must always be diff = fl(a - b)
        Returns:
        The error described above
      • getErrorComponentFromProduct

        public static double getErrorComponentFromProduct​(double a,
                                                          double b,
                                                          double product)
        Given two values a, b and their product = fl(a * b) calculates the value error for which fl(a) * fl(b) = fl(a * b) + fl(error).
        Parameters:
        a - The first value
        b - The second value
        product - Their product, must always be product = fl(a * b)
        Returns:
        The error described above