[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17362665#comment-17362665
]
Gilles Sadowski commented on NUMBERS-155:
-
bq. What type of API do you want?
I'm not sure. The use-case is to store a symmetric matrix as a one-dimensional
array; but nothing urgent.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361819#comment-17361819
]
Alex Herbert commented on NUMBERS-155:
--
Re: Triangle array.
I have a class that implements an API as a helper to generate indices into an
index of a upper triangular array. I wrote this to store all-vs-all comparison
matrices. Thus it does not support i==j as the self-comparison score is known.
It suited my use case. But I think it could be modified to support the i==j
index. I cannot remember if I worked out the indexing math or copied it. The
methods are below. The reverse method has a sqrt so will not be fast.
{code:java}
/**
* Convert from ij to linear index. Index j must be greater than i.
*
* Behaviour is undefined if i==j.
*
* @param n the size of the array in 1 dimension
* @param i the index i
* @param j the index j
* @return the linear index
*/
public static int toIndex(int n, int i, int j) {
return (n * (n - 1) / 2) - (n - i) * ((n - i) - 1) / 2 + j - i - 1;
}
/**
* Convert from linear index to ij.
*
* @param n the size of the array in 1 dimension (total length = n*(n-1)/2)
* @param k the linear index (Must be with the bound 0:length-1)
* @param ij the ij data (Must be size 2 or greater)
*/
public static void fromIndex(int n, int k, int[] ij) {
final int i = n - 2 - (int) Math.floor(Math.sqrt(-8.0 * k + 4 * n * (n - 1) -
7) / 2.0 - 0.5);
ij[0] = i;
ij[1] = k + i + 1 - (n * (n - 1) / 2) + (n - i) * ((n - i) - 1) / 2;
}
{code}
This was all in a class that could precompute some values and provided methods
for fast iteration over rows or columns by initialising the row/column then
outputting the indices in a separate call to be used in a loop.
What type of API do you want? A simple version is:
{code:java}
// Upper or lower triangle
TriangularArrayIndex index = TriangularArrayIndex.of(n, true);
double[] data = new double[index.size()];
for (int i = 0; i < n; i++) {
// Upper
for (int j = i; j < n; j++) {
data[index.get(i, j)] = i * j;
}
}
TriangularArrayIndex index = TriangularArrayIndex.of(n, false);
double[] data = new double[index.size()];
for (int i = 0; i < n; i++) {
// Lower
for (int j = 0; j <= i; j++) {
data[index.get(i, j)] = i * j;
}
}
{code}
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361812#comment-17361812
]
Gilles Sadowski commented on NUMBERS-155:
-
{quote}
{code}
public int[] toMulti(int index, int[] indices);
{code}
{quote}
Yes but we should first assess the performance cost of creating many small
arrays (given that this is handled at the JVM level).
bq. If you are repeat accessing a single dimension array via the counter then
there are a lot of calls to create an index
Indeed; but maybe there should be another API for such cases, e.g. passing a
"transformer" that modifies the elements in-place or return a stream.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361796#comment-17361796
]
Alex Herbert commented on NUMBERS-155:
--
{quote}However, for each access to an element of a virtual multidimensional
array, the utility must instantiate an int[].
{quote}
Requires an API change?
Which method is the main problem:
{noformat}
// Creates an int[] for the result
public int[] toMulti(int index);
// Creates an int[] for the arguments
public int toUni(int... c);
{noformat}
The first can be solved by accepting the output array as an argument:
{noformat}
// Reuses the int[] for the result.
// If null -> exception or create the array
// If too small -> exception or create the array
// If too big -> exception or use it anyway
public int[] toMulti(int index, int[] indices);
{noformat}
The second just requires the user to maintain an array to be passed in.
For single access to elements the performance may be negligible. If you are
repeat accessing a single dimension array via the counter then there are a lot
of calls to create an index. When repeat accessing elements this is either
random positions or a series. In the later case the API does not cater for
iterating over columns as it does not expose the stride length offsets. Here is
an example of using the offset of a given dimension:
{code:java}
int[] size = {2, 3, 4};
MultidimensionalCounter mc = MultidimensionalCounter.of(size);
double[] data = new double[mc.getSize()];
int x = 1;
int z = 2;
for (int y = 0,
index = mc.toUni(x, y, z),
stride = mc.getOffset(1); y < size[1]; y++, index += stride) {
data[index] = 42;
}
{code}
The class could be made more efficient with specialisations for 2D, 3D, etc.
But to be optimal they would have to declare their own toUni method:
{code:java}
public int toUni(int i, int j);
public int toUni(int i, int j, int k);
public int toUni(int i, int j, int k, int l);
{code}
If they all stick to using {{toUni(int...)}} then the factory constructor can
still return specialised instances which would improve performance by
eliminating the loop over the dimension and storing the sizes and offsets as
primitives.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361749#comment-17361749
]
Gilles Sadowski commented on NUMBERS-155:
-
{quote}Q. What is the implication of moving these class to the core module,
under the same package names, and then creating an arrays module and/or
rootfinder module in a future release?That is, can any packages released in the
core jar be later moved to a separate module for those packages if they are to
be expanded.
{quote}
I'd keep away of the trouble which you mention in the "A."
[In these components, Maven modules are also intended as JPMS modules.]
bq. other use cases for an arrays package.
The primary rationale was for representing multidimensional arrays (that are
inordinately costly in Java) by a single array.
However, for each access to an element of a virtual multidimensional array, the
utility must instantiate an {{int[]}}. I have no idea whether it entails a
performance hit that would prohibit usage in all but trivial use cases.
bq. Or a 2D MatrixTranspose wrapper that reverses the input indices to allow
addressing an underlying 2D matrix as its transpose.
Cf. transpose in the API proposed in MATH-928.
More than 7 years old... :-}
bq. symmetric matrix data structure [...] halving the memory requirement by
storing the square matrix as a triangle.
+1
I have a use-case for such a utility. Choice of row- or column-major storage
should be available.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361664#comment-17361664
]
Alex Herbert commented on NUMBERS-155:
--
Looking at the entire numbers codebase each package is in a separate module. So
if the code does not fit as a core number utility it should not go into core,
it should be in a different package and hence different module.
I think it fine to keep these modules with single classes. This is the current
case for complex.
Q. What is the implication of moving these class to the core module, under the
same package names, and then creating an arrays module and/or rootfinder module
in a future release?That is, can any packages released in the core jar be later
moved to a separate module for those packages if they are to be expanded.
A. Such a moved would keep source compatibility for downstream projects but
with a change of their dependencies. If they are updating their version numbers
then they can also add a new module dependency. One issue would be a transitive
dependency resolving a newer version of numbers core that had a package moved
to a new module. Any code assuming the previous version would be missing
classes. So this could be bad. A safer option is to keep packages in modules.
I can think of a few other use cases for an arrays package. The cases are for
methods of indexing into arrays. MultidimensionalCounter is one example. A
trivial example would be to have a wrapper object that translates 1-based
indexing to 0-based indexing into an underlying array data structure. This
would be for users familiar with 1-based indexing such as matlab. Or a 2D
MatrixTranspose wrapper that reverses the input indices to allow addressing an
underlying 2D matrix as its transpose. Or a 2D symmetric matrix data structure
where [i][j] == [j][i], thus halving the memory requirement by storing the
square matrix as a triangle.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17361596#comment-17361596
]
Gilles Sadowski commented on NUMBERS-155:
-
bq. Shouldn't some functionality currently in module commons-numbers-arrays be
moved to commons-number-core?
Done in NUMBERS-159.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17333433#comment-17333433
]
Gilles Sadowski commented on NUMBERS-155:
-
Thanks.
Do you think that it makes sense to have a {{rootfinder}} package in the
{{commons-numbers-core}} module rather than another module with just this one
functionality? Or do you imagine that we'd add something else in the
{{commons-numbers-rootfinder}} module? [IIRC, there was never a case where any
of the other root finders in Commons Math were better than Brent's solver.]
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=1762#comment-1762
]
Alex Herbert commented on NUMBERS-155:
--
Looking at the Brent solver I think this does not require extra precision. The
algorithm aims to find b such that f(b) == 0. The input function f is user
provided and computes in standard precision. So you only need to find b as a
standard precision value. The algorithm is computing updates to b such that the
function f(b) moves closer to zero. Any use of extended precision is applicable
to computing the factors used perform the inverse quadratic interpolation. This
only uses one subtraction of two other composite terms:
{code:java}
p = s * (2 * m * q * (q - r) - (b - a) * (r - 1));
p = s * (X - Y);
{code}
Thus there is not a chance of large cancellation and the update step will be
close to a true unlimited precision result. As long as the solver does not blow
up to use increasingly larger steps when alternating around a root, or compute
insignificant steps (and there is detection for this with a reversion to
bisection) then the only effect of a less than perfect computation of the
inverse linear interpolation would be a few more iterations before the root is
found.
Or another argument is you need to find b within tolerance where:
{code:java}
a < b < c
f(a) < 0
f(c) > 0
f(b) == 0 (within tolerance)
{code}
Given a correct bracket of a root then just moving the closest to zero end in
and setting b as the midpoint (bisection) would eventually find the root to the
same tolerance. No extended precision need. The Brent solver is just computing
the update using not the midpoint but using a smarter approximation of the
local curve to jump towards the root.
You could modify the BrentSolver to use floats to do all the computation of the
inverse quadratic interpolation to effectively lower the precision and then
verify it still solves functions. If it takes a lot more iterations then there
may be a case for seeing if an extended precision computation of the update
step would take significantly less iterations to solve the same function. But
the accuracy of the solution should not change as the tolerance is chosen by
the caller.
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=1727#comment-1727
]
Gilles Sadowski commented on NUMBERS-155:
-
In practice (deferring the issue of public API), could a "high-precision"
version (that would use a package-private {{ExtendedPrecision}} of the root
finder be useful? IOW, if the higher precision is only used internally (i.e.
not for computing the function's values), would it produce a better zero?
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (NUMBERS-155) About modules "arrays" and "rootfinder"
[
https://issues.apache.org/jira/browse/NUMBERS-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17333293#comment-17333293
]
Alex Herbert commented on NUMBERS-155:
--
Currently the {{o.a.c.numbers.arrays.ExtendedPrecision}} class is package
private and has some package private methods exposed for unit testing. The two
methods of interest for a public API are:
{code:java}
/**
* Compute the low part of the double length number {@code (z,zz)} for the
exact
* product of {@code x} and {@code y}. This is equivalent to computing a
{@code double}
* containing the magnitude of the rounding error when converting the exact
106-bit
* significand of the multiplication result to a 53-bit significand.
*
* @param x First factor.
* @param y Second factor.
* @param xy Product of the factors (x * y).
* @return the low part of the product double length number
* @see #highPartUnscaled(double)
*/
static double productLow(double x, double y, double xy);
/**
* Compute the round-off from the sum of two numbers {@code a} and {@code
b} using
* Knuth's two-sum algorithm. The values are not required to be ordered by
magnitude.
* The standard precision sum must be provided.
*
* @param a First part of sum.
* @param b Second part of sum.
* @param sum Sum of the parts (a + b).
* @return (b - (sum - (sum - b))) + (a - (sum - b))
*/
static double twoSumLow(double a, double b, double sum) {
{code}
Both of these methods assume that the user has already computed either the
product or the sum of the two input arguments. If they are not called with this
value then the methods will compute an incorrect result. Two options for public
use are to remove the input argument and just compute it:
{code:java}
public static double productLow(double x, double y) {
return productLow(x, y, x * y);
}
{code}
However in most cases you would not require the low (extended precision) part
if you did not also require the high (standard precision) part. The other
option is therefore to provide a paired result. There is an example of this in
the source material in the JMH examples package in class
{{o.a.c.numbers.examples.jmh.arrays.DoublePrecision}}:
{code:java}
/**
* Represents a floating-point number with twice the precision of a {@code
double}.
*/
static final class Quad {
// This is treated as a simple struct.
/** The high part of the number. */
double hi;
/** The low part of the number. */
double lo;
}
/**
* Multiply the values {@code x} and {@code y} into a double-precision
result {@code c}.
*
* @param x First value
* @param y Second value
* @param c Result
*/
static void multiply(double x, double y, Quad c);
{code}
There are two implementations that do the same but one adds scaling to protect
against intermediate over/underflow. The methods are tested using for example:
{code:java}
cd commons-numbers-examples/examples-jmh
mvn package -Pexamples-jmh
java -jar target/examples-jmh.jar DoubleSplitPerformance.productLow -p
size=1 -p exp=600 -p edge=0.999
{code}
This tests multiplication of 1 pairs of two numbers, each of which has an
exponent of 600 with a probability of 0.001, and exponent of 1 otherwise (i.e.
some product pairs will overflow).
> About modules "arrays" and "rootfinder"
> ---
>
> Key: NUMBERS-155
> URL: https://issues.apache.org/jira/browse/NUMBERS-155
> Project: Commons Numbers
> Issue Type: Task
> Components: arrays, core
>Affects Versions: 1.0-beta1
>Reporter: Gilles Sadowski
>Priority: Major
> Labels: refactoring
> Fix For: 1.0
>
>
> Shouldn't some functionality currently in module {{commons-numbers-arrays}}
> be moved to {{commons-number-core}}?
> Rationale is that the utilities focus on extended precision of some
> computations (on numbers that happen to be stored in an array).
> Wouldn't the Brent solver (in module {{commons-numbers-rootfinder}}) benefit
> from a version based on the new {{ExtendedPrecision}} class?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
