 java.lang.Object

 org.dyn4j.geometry.AdaptiveDecimal

class AdaptiveDecimal extends java.lang.Object
This is an implementation of multiprecision decimals based on the original work by Jonathan Richard Shewchuk, "Routines for Arbitrary Precision Floatingpoint 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 nonoverlapping property, that is the corresponding bit representation of adjacent components must not overlap. SeecheckInvariants()
and the corresponding paper for more info.This code requires that the floating point model is IEEE754 with roundtoeven 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 Summary
Constructors Modifier Constructor Description protected
AdaptiveDecimal(double a0, double a1)
Internal helper constructor to create aAdaptiveDecimal
with two componentsAdaptiveDecimal(int length)
Creates a newAdaptiveDecimal
with the specified length.AdaptiveDecimal(AdaptiveDecimal other)
Deep copy constructor.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description AdaptiveDecimal
append(double value)
Appends a new component after all the existing components.AdaptiveDecimal
appendNonZero(double value)
Appends a new component after all the existing components, but only if it has a non zero value.int
capacity()
boolean
checkInvariants()
Returns a boolean value describing if thisAdaptiveDecimal
is a valid representation as described in the header of this class.AdaptiveDecimal
clear()
Removes the components of thisAdaptiveDecimal
.AdaptiveDecimal
copy()
void
copyFrom(AdaptiveDecimal other)
Copies the components of anotherAdaptiveDecimal
into this.void
ensureInvariants()
static AdaptiveDecimal
fromDiff(double a, double b)
Creates aAdaptiveDecimal
that holds the result of the difference of two double values.(package private) 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 givenAdaptiveDecimal
result
.static AdaptiveDecimal
fromProduct(double a, double b)
Creates aAdaptiveDecimal
that holds the result of the product of two double values.static AdaptiveDecimal
fromSum(double a, double b)
Creates aAdaptiveDecimal
that holds the result of the addition of two double values.double
get(int index)
(package private) 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).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).(package private) 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).double
getEstimation()
Computes an approximation for the value of thisAdaptiveDecimal
that fits in a double.AdaptiveDecimal
negate()
Negates the logical value of thisAdaptiveDecimal
.AdaptiveDecimal
normalize()
Ensures thisAdaptiveDecimal
has at least one component.AdaptiveDecimal
removeZeros()
Removes all the components with zero value from thisAdaptiveDecimal
.int
size()
AdaptiveDecimal
sum(AdaptiveDecimal f)
Performs addition and also allocates a newAdaptiveDecimal
with the appropriate capacity to store the result.AdaptiveDecimal
sum(AdaptiveDecimal f, AdaptiveDecimal result)
Performs the addition of thisAdaptiveDecimal
with the givenAdaptiveDecimal
f and stores the result in the providedAdaptiveDecimal
result
.(package private) AdaptiveDecimal
sumEpilogue(double carry, AdaptiveDecimal e, int eIndex, AdaptiveDecimal result)
Helper method to implement the sum procedure.java.lang.String
toString()
static AdaptiveDecimal
valueOf(double value)
Creates aAdaptiveDecimal
with only a single component.



Constructor Detail

AdaptiveDecimal
public AdaptiveDecimal(int length)
Creates a newAdaptiveDecimal
with the specified length. The initialAdaptiveDecimal
created does not contains any components. Parameters:
length
 The maximum number of components thisAdaptiveDecimal
can store

AdaptiveDecimal
public AdaptiveDecimal(AdaptiveDecimal other)
Deep copy constructor. Parameters:
other
 theAdaptiveDecimal
to copy from

AdaptiveDecimal
protected AdaptiveDecimal(double a0, double a1)
Internal helper constructor to create aAdaptiveDecimal
with two components Parameters:
a0
 the component with the smallest magnitudea1
 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

copy
public AdaptiveDecimal copy()
 Returns:
 A deep copy of this
AdaptiveDecimal

copyFrom
public void copyFrom(AdaptiveDecimal other)
Copies the components of anotherAdaptiveDecimal
into this. The capacity of the thisAdaptiveDecimal
is not modified and it should be enough to hold all the components. Parameters:
other
 TheAdaptiveDecimal
to copy from

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 thisAdaptiveDecimal
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 thisAdaptiveDecimal
is a valid representation as described in the header of this class. Checks for the magnitude and nonoverlapping property. The invariants can be violated if bad input components are appended to thisAdaptiveDecimal
. 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
 iffcheckInvariants()
returns false

clear
public AdaptiveDecimal clear()
Removes the components of thisAdaptiveDecimal
. Returns:
 this
AdaptiveDecimal

removeZeros
public AdaptiveDecimal removeZeros()
Removes all the components with zero value from thisAdaptiveDecimal
. Returns:
 this
AdaptiveDecimal

normalize
public AdaptiveDecimal normalize()
Ensures thisAdaptiveDecimal
has at least one component. That is, appends the zero value if there are currently zero components. Returns:
 this
AdaptiveDecimal

negate
public AdaptiveDecimal negate()
Negates the logical value of thisAdaptiveDecimal
. This can be used with sum to perform subtraction . Returns:
 this
AdaptiveDecimal

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

sum
public AdaptiveDecimal sum(AdaptiveDecimal f)
Performs addition and also allocates a newAdaptiveDecimal
with the appropriate capacity to store the result. Parameters:
f
 TheAdaptiveDecimal
to sum with thisAdaptiveDecimal
 Returns:
 A new
AdaptiveDecimal
that holds the result of the addition  See Also:
sum(AdaptiveDecimal, AdaptiveDecimal)

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

sum
public AdaptiveDecimal sum(AdaptiveDecimal f, AdaptiveDecimal result)
Performs the addition of thisAdaptiveDecimal
with the givenAdaptiveDecimal
f and stores the result in the providedAdaptiveDecimal
result
. Ifresult
is null it allocates a newAdaptiveDecimal
with the appropriate capacity to store the result. Otherwise the components ofresult
are cleared and the resulting value is stored there, assuming there is enough capacity. Be careful that it must bef
≠result
≠this
. Parameters:
f
 TheAdaptiveDecimal
to sum with thisAdaptiveDecimal
result
 TheAdaptiveDecimal
in which the sum is stored or null to allocate a new one Returns:
 The result

toString
public java.lang.String toString()
 Overrides:
toString
in classjava.lang.Object

valueOf
public static AdaptiveDecimal valueOf(double value)
Creates aAdaptiveDecimal
with only a single component. Parameters:
value
 The component Returns:
AdaptiveDecimal

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

fromDiff
public static AdaptiveDecimal fromDiff(double a, double b)
Creates aAdaptiveDecimal
that holds the result of the difference of two double values. Parameters:
a
 The first valueb
 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 givenAdaptiveDecimal
result
. In the same way as withsum(AdaptiveDecimal, AdaptiveDecimal)
ifresult
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 newAdaptiveDecimal
and performing the generalized sum procedure. Parameters:
a0
 The first component of aa1
 The second component of ab0
 The first component of bb1
 The second component of bresult
 TheAdaptiveDecimal
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 aAdaptiveDecimal
that holds the result of the product of two double values. Parameters:
a
 The first valueb
 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 valueb
 The second valuesum
 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 valueb
 The second valuediff
 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 valueb
 The second valueproduct
 Their product, must always be product = fl(a * b) Returns:
 The error described above

