Re: [geometry] 1.0-beta2
On Wed, 21 Apr 2021 at 03:33, Matt Juntunen wrote: > Hi Alex, > > First of all, thanks for all of the work you've done here! Second, I vote > to go with the fast dot2s implementation for LinearCombination and use it > as a static method in commons-geometry. The reason is that the scale of > accuracy improvements we're talking about here is not going to mean much > for practical purposes, whereas a performance hit in a critical piece of > code like this definitely is. Also, I'd prefer to keep the choice of > LinearCombination algorithm internal to the library and not make it > configurable. The vast majority of users are not going to want to have to > think about it and it will keep the API cleaner if we don't explicitly > allow it to be changed. If users want to use a different algorithm for > something in commons-geometry, they can write a utility method that > leverages other parts of commons-numbers. > OK. Note that exact computation is most important when small absolute differences result in large relative differences between the computed and actual answer. The case for the Complex class was in a computation that approaches zero. Here the relative error can be very large. If this type of computation is not being done in Geometry then favouring speed over precision makes sense. If a critical computation requires this precision then support can be added for specific use cases when they are found. I'll create a PR that updates the current method to the faster (and essentially the same accuracy) dot2s method. Alex
Re: [geometry] 1.0-beta2
Hi Alex, First of all, thanks for all of the work you've done here! Second, I vote to go with the fast dot2s implementation for LinearCombination and use it as a static method in commons-geometry. The reason is that the scale of accuracy improvements we're talking about here is not going to mean much for practical purposes, whereas a performance hit in a critical piece of code like this definitely is. Also, I'd prefer to keep the choice of LinearCombination algorithm internal to the library and not make it configurable. The vast majority of users are not going to want to have to think about it and it will keep the API cleaner if we don't explicitly allow it to be changed. If users want to use a different algorithm for something in commons-geometry, they can write a utility method that leverages other parts of commons-numbers. Regards, Matt J From: Alex Herbert Sent: Tuesday, April 20, 2021 12:25 PM To: Commons Developers List Subject: Re: [geometry] 1.0-beta2 On Tue, 20 Apr 2021 at 13:51, Gilles Sadowski wrote: > Hi Alex. > > Le mar. 20 avr. 2021 à 11:17, Alex Herbert a > écrit : > > > > [...] > > I'm a bit lost in all these bits... ;-) > I also had to remind myself of the work since it was a long time ago. > > > Any opinions on how changing LinearComination may affect Geometry? Either > > we clean up the implementation to use the fast dot2s algorithm with > correct > > support for splitting 53-bit mantissas, or switch to the extended > precision > > version. But I do not think we should leave it as the current > > implementation which has disadvantages against either of the > alternatives. > > What is your suggestion? > Some background... The dot2s is a specialisation of the DotK algorithm where the K represents the k-fold increase in precision over a standard scalar product and denotes qualitatively the level of robustness for a sum with massive cancellation (e.g. 1e-100 + 1e200 - 2e-100 - 1e200 = -1e-100). Any floating-point sum is limited by the representation of a 64-bit double as a binary floating point number with only 53-bits of precision and an exponent. When adding numbers the result is computed and any extra bits that cannot fit into the mantissa are lost. Whether this occurs is dependent on the input numbers, but in general as the difference in magnitude becomes greater then the result will contain progressively less of the true result due to the 53-bit mantissa. If two numbers are different by more than 2^53 then adding them makes no difference to the bigger number. In the example above a standard precision result is 0. Only with extended precision can you hold the result of 1e-100 + 1e200, etc. In a sum of magnitude this only really matters when cancellation (opposite signs) may occur. Take the recently discussed code to compute the 3D vector length: len = sqrt(x^2 + y^2 + z^2) This uses a sum where the sign of the terms is the same. There will be no cancellation and thus the answer will be close to the true result (within a few ulps). But if the sum of multiple values has different signs then the answer may be in between the magnitudes of the terms. So the intermediate sum should store knowledge of more bits of the intermediate result than the 64-bits of a double. The LinearCombination is actually providing two operations, multiplication and addition: sum_i {a_i * b_i} The multiplication has a potential 106-bit mantissa for the result with a single exponent. Any addition may require a longer mantissa with a single exponent which is how BigDecimal would store the result. An extended precision double number would represent the result as an array of two doubles of very different magnitudes. Adding or multiplying the extended precision result can increase the length of the result further. The use of arrays of double to represent a number in extended precision is well described in Shewchuk (1997): Arbitrary Precision Floating-Point Arithmetic [1], on which a lot of the work in Numbers-142 is based. There could be a case for a class to implement this generically: public class ExtendedDouble { public static ExtendedDouble of(double a); public ExtendedDouble add(double a); public ExtendedDouble add(ExtendedDouble a); public ExtendedDouble multiply(double a); public ExtendedDouble multiply(ExtendedDouble a); public double toDouble(); } That could be in another module in numbers. Shewchuk does not describe division but it may be in references he provides. His paper is based upon developing exact arithmetic for geometry applications so addition and multiplication are all that are used. As for LinearCombination then I would suggest that the use case is for any dot product where cancellation may be expected. If handling cancellation is more important than speed then using the most accurate method would seem to be a
Re: [geometry] 1.0-beta2
On Tue, 20 Apr 2021 at 13:51, Gilles Sadowski wrote: > Hi Alex. > > Le mar. 20 avr. 2021 à 11:17, Alex Herbert a > écrit : > > > > [...] > > I'm a bit lost in all these bits... ;-) > I also had to remind myself of the work since it was a long time ago. > > > Any opinions on how changing LinearComination may affect Geometry? Either > > we clean up the implementation to use the fast dot2s algorithm with > correct > > support for splitting 53-bit mantissas, or switch to the extended > precision > > version. But I do not think we should leave it as the current > > implementation which has disadvantages against either of the > alternatives. > > What is your suggestion? > Some background... The dot2s is a specialisation of the DotK algorithm where the K represents the k-fold increase in precision over a standard scalar product and denotes qualitatively the level of robustness for a sum with massive cancellation (e.g. 1e-100 + 1e200 - 2e-100 - 1e200 = -1e-100). Any floating-point sum is limited by the representation of a 64-bit double as a binary floating point number with only 53-bits of precision and an exponent. When adding numbers the result is computed and any extra bits that cannot fit into the mantissa are lost. Whether this occurs is dependent on the input numbers, but in general as the difference in magnitude becomes greater then the result will contain progressively less of the true result due to the 53-bit mantissa. If two numbers are different by more than 2^53 then adding them makes no difference to the bigger number. In the example above a standard precision result is 0. Only with extended precision can you hold the result of 1e-100 + 1e200, etc. In a sum of magnitude this only really matters when cancellation (opposite signs) may occur. Take the recently discussed code to compute the 3D vector length: len = sqrt(x^2 + y^2 + z^2) This uses a sum where the sign of the terms is the same. There will be no cancellation and thus the answer will be close to the true result (within a few ulps). But if the sum of multiple values has different signs then the answer may be in between the magnitudes of the terms. So the intermediate sum should store knowledge of more bits of the intermediate result than the 64-bits of a double. The LinearCombination is actually providing two operations, multiplication and addition: sum_i {a_i * b_i} The multiplication has a potential 106-bit mantissa for the result with a single exponent. Any addition may require a longer mantissa with a single exponent which is how BigDecimal would store the result. An extended precision double number would represent the result as an array of two doubles of very different magnitudes. Adding or multiplying the extended precision result can increase the length of the result further. The use of arrays of double to represent a number in extended precision is well described in Shewchuk (1997): Arbitrary Precision Floating-Point Arithmetic [1], on which a lot of the work in Numbers-142 is based. There could be a case for a class to implement this generically: public class ExtendedDouble { public static ExtendedDouble of(double a); public ExtendedDouble add(double a); public ExtendedDouble add(ExtendedDouble a); public ExtendedDouble multiply(double a); public ExtendedDouble multiply(ExtendedDouble a); public double toDouble(); } That could be in another module in numbers. Shewchuk does not describe division but it may be in references he provides. His paper is based upon developing exact arithmetic for geometry applications so addition and multiplication are all that are used. As for LinearCombination then I would suggest that the use case is for any dot product where cancellation may be expected. If handling cancellation is more important than speed then using the most accurate method would seem to be a better choice. I do recall seeing LinearCombination used in the Geometry code inside a loop with the result stored as a double on each iteration. This would result in loss of the extended precision intermediate sum and so could cause error due to cancellation. So there is a case for going through Geometry to find use cases for LinearCombination and potentially find places where changes should be made to compute all the terms in advance and call LinearCombination once with the two input arrays. > My impression is that [Geometry] emphasizes accuracy over ultimate > speed (as opposed to libraries used for real-time rendering, I guess). > > However, could it be possible to leave this as a user's decision? > Quoting from Matt's tutorial: > ---CUT--- > Typically, users of Commons Geometry will construct a single instance > of this type for use by multiple objects throughout an entire > operation, or even application. Since we don't want our class to > assume such a heavy responsibility, we will simply accept a > DoublePrecisionContext in the constructor. > ---CUT--- > Would it be conceivable that the choice of the imple
Re: [geometry] 1.0-beta2
Hi Alex. Le mar. 20 avr. 2021 à 11:17, Alex Herbert a écrit : > > [...] I'm a bit lost in all these bits... ;-) > Any opinions on how changing LinearComination may affect Geometry? Either > we clean up the implementation to use the fast dot2s algorithm with correct > support for splitting 53-bit mantissas, or switch to the extended precision > version. But I do not think we should leave it as the current > implementation which has disadvantages against either of the alternatives. What is your suggestion? My impression is that [Geometry] emphasizes accuracy over ultimate speed (as opposed to libraries used for real-time rendering, I guess). However, could it be possible to leave this as a user's decision? Quoting from Matt's tutorial: ---CUT--- Typically, users of Commons Geometry will construct a single instance of this type for use by multiple objects throughout an entire operation, or even application. Since we don't want our class to assume such a heavy responsibility, we will simply accept a DoublePrecisionContext in the constructor. ---CUT--- Would it be conceivable that the choice of the implementation activated by a call to the "LinearCombination" facility is also encapsulated in the "DoublePrecisionContext"? Regards, Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] 1.0-beta2
On Mon, 19 Apr 2021 at 22:30, Gilles Sadowski wrote: > Le lun. 19 avr. 2021 à 20:26, Matt Juntunen > > > What needs to be done on numbers before we're ready for > > 1.0 (aside from moving over some code from geometry)? > > The most basic utilities haven't fundamentally changed. It > will be nice to increase the visibility of the many consistency > and performance improvements. > Modules to perhaps be left out are also TBD (in another thread). > I did a lot of work investigating improving the accuracy of LinearCombination (see Numbers 142 [1]). This ended by improving the accuracy of the linear combination that is used inside the Complex class in a very special use case summing terms close to zero (i.e. where large cancellations of terms are significant). However that is private to the class. The main LinearCombination class remains the same which uses an approximate quad level accuracy (128-bit) sum of linear terms. This could be changed to improve accuracy at the expense of runtime speed. Even if we keep the quad level accuracy the method to split the upper and lower parts of the number before multiplication can be improved to retain an extra bit of information and support sub-normal numbers. All the code for variations and the performance benchmarks are in 'o.a.c.numbers.examples.jmh.arrays'. The main LinearCombinations class in that package has all variants. Currently the LinearCombination class is implementing a variant of the dot2s method of Ogita et al (2005). The method for array inputs uses array allocation in the computation. It also uses a split of the 53-bit double mantissa (including the leading 1-bit) to two 26-bit doubles. This can be changed to the reference dot2s method to avoid array allocation and use Dekker's split to extract a 27-bit double and a 26-bit double with support for sub-normal numbers. This would be the implementation in the LinearCominations.Dot2s class. Alternatively there is a version which computes an exact summation without using BigDecimal (LinearCominations.ExtendedPrecision using ExactSum for the summation). It is slower than the current 2-fold precision method but much faster than using BigDecimal. Changing to this implementation may have a big impact on the performance of Geometry which uses LinearCombination extensively. The Jira ticket has a lot of performance information. This post [2] seems to summarise the speed relative to the current implementation as: Value Method Relative twoD dot2s 0.73 twoD extended 1.13 threeD dot2s 0.75 threeD extended 1.48 fourD dot2s 0.75 fourD extended 1.68 nD dot2s 0.56 nD extended 2.95 So an exact dot2s implementation is faster and the extended precision implementation is about 3x slower on long arrays but not much slower on small combinations. Here the extended precision sum is accurate to 1 ULP. Making it exact to 0 ULP (extended2) takes a bit more time and the performance is summarised later as: "Using the extended2 method versus the fast dot2s will have a performance impact dependent on the condition number of the dot product and the length of the dot product. For short lengths (2 to 4) the method is about 1.2 to 2.5x slower. Long dot products are much slower (8x). The runtime is insignificant compared to using BigDecimal which is a magnitude slower." Any opinions on how changing LinearComination may affect Geometry? Either we clean up the implementation to use the fast dot2s algorithm with correct support for splitting 53-bit mantissas, or switch to the extended precision version. But I do not think we should leave it as the current implementation which has disadvantages against either of the alternatives. Alex [1] https://issues.apache.org/jira/browse/NUMBERS-142 [2] https://issues.apache.org/jira/browse/NUMBERS-142?focusedCommentId=17040111&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-17040111
Re: [geometry] 1.0-beta2
Le lun. 19 avr. 2021 à 20:26, Matt Juntunen a écrit : > > Hi Gilles, > > Are you suggesting skipping another beta version and having numbers 1.0 and > geometry 1.0 be the next releases? Yes, that's the question which I'm asking. There is no point in waiting much longer for feedback that may never come... Of course, we aim for the perfect design but if we get it wrong and must evolve the library in a non-compatible way, all that will happen is that the base package will change name. > I could get on board with that. It would be great to have an > official release of these. Well, it's up to the main contributor(s) to let us know when it seems that the design is good enough given the knowledge shared within the current community. > What needs to be done on numbers before we're ready for > 1.0 (aside from moving over some code from geometry)? The most basic utilities haven't fundamentally changed. It will be nice to increase the visibility of the many consistency and performance improvements. Modules to perhaps be left out are also TBD (in another thread). > > On another note, I don't feel like the enclosing and hull > modules in geometry are quite ready for prime time yet. > So, I would leave those out of 1.0. That would be quite fine, I think. Gilles >> [...] - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] 1.0-beta2
Hi Gilles, Are you suggesting skipping another beta version and having numbers 1.0 and geometry 1.0 be the next releases? I could get on board with that. It would be great to have an official release of these. What needs to be done on numbers before we're ready for 1.0 (aside from moving over some code from geometry)? On another note, I don't feel like the enclosing and hull modules in geometry are quite ready for prime time yet. So, I would leave those out of 1.0. Regards, Matt From: Gilles Sadowski Sent: Monday, April 19, 2021 12:37 PM To: Commons Developers List Subject: Re: [geometry] 1.0-beta2 Hello Matt. Le lun. 19 avr. 2021 à 15:20, Matt Juntunen a écrit : > > I'd like to release commons-geometry 1.0-beta2 within the next couple of > weeks. I'm planning on including GEOMETRY-118 (additional methods for > transform matrix classes) in that if possible. Is there anything else anyone > would like to include? Thanks a lot for your work on [Geometry]. Could we perhaps make progress with the issue of what code can be moved to [Numbers]? Rationale is that some project might be unwilling to allow "beta" code in its dependencies (if just because there is the risk JAR hell, which we explicitly permit in beta releases). Since it isn't likely that additional feedback will come about the beta components, it would be good to plan for an "official" release of [Numbers] and [Geometry], in that order. [It's not mandatory to include all modules.] WDYT? Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] 1.0-beta2
Hello Matt. Le lun. 19 avr. 2021 à 15:20, Matt Juntunen a écrit : > > I'd like to release commons-geometry 1.0-beta2 within the next couple of > weeks. I'm planning on including GEOMETRY-118 (additional methods for > transform matrix classes) in that if possible. Is there anything else anyone > would like to include? Thanks a lot for your work on [Geometry]. Could we perhaps make progress with the issue of what code can be moved to [Numbers]? Rationale is that some project might be unwilling to allow "beta" code in its dependencies (if just because there is the risk JAR hell, which we explicitly permit in beta releases). Since it isn't likely that additional feedback will come about the beta components, it would be good to plan for an "official" release of [Numbers] and [Geometry], in that order. [It's not mandatory to include all modules.] WDYT? Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
[geometry] 1.0-beta2
I'd like to release commons-geometry 1.0-beta2 within the next couple of weeks. I'm planning on including GEOMETRY-118 (additional methods for transform matrix classes) in that if possible. Is there anything else anyone would like to include? Regards, Matt J