JDK 14 RFR of JDK-8233452: java.math.BigDecimal.sqrt() with RoundingMode.FLOOR results in incorrect result

[Joe Darcy]

Hello,

Some further refinements to the implementation and tests ready for 
re-review:

     http://cr.openjdk.java.net/~darcy/8233452.4/

The fix-up code for directed roundings (up, down, etc.) was corrected to 
properly handle rounding down when the interim result is a power of 10, 
in this case 1.0. The adjustment down in that case needs to be reduced 
in size since the size of an ulp changes at exponent boundaries. The 
regression tests cover this situation.

The assertion checks on the numerical properties of the result were 
restructured to be more informative. One assert was overly strict and 
made weaker to accommodate the sort of situation discussed in the comments.

The comments make reference to the "2p + 2" property. This concerns 
floating-point rounding and when a double-rounding problem can be 
avoided. In brief, if you first round to (p + k) digits than then round 
that result to p digits, a difference result can be computed than if a 
single rounding to p digits occurred. For example, both the roundings to 
(p + k) and p digits could round up when a single rounding up would not 
round up. However, if the first rounding is to at least (2p + 2) digits, 
a second rounding to p digits will *not* have the double rounding hazard 
for +, -, *, / and square root.

The main Newton loop in the square root implementation has been modified 
to compute at least (2p + 2) digits so the rounding to p digits will be 
correct without a fix-up. With sufficient analysis, computing to about p 
digitis instead and doing a fix-up should be possible, but I'll leave 
that as a refinement for another day.

Thanks,

-Joe

On 11/7/2019 1:52 PM, Brian Burkhalter wrote:
>
> Hi Joe,
>
>> On Nov 5, 2019, at 6:04 PM, Joe Darcy <joe.darcy at oracle.com 
>> <mailto:joe.darcy at oracle.com>> wrote:
>>
>> Please review the changes to fix
>>
>>     JDK-8233452: java.math.BigDecimal.sqrt() with RoundingMode.FLOOR 
>> results in incorrect result
>> http://cr.openjdk.java.net/~darcy/8233452.0/
>>
>> Some background on the problem and fix.
>>
>> The core of the BigDecimal.sqrt method is a Newton-Raphson loop.
>> […]
>> The Newton iteration reduces the error at each step and, as currently 
>> written, it can settle on a value like 2, which is closer to the 
>> actual answer, but *incorrect* according to the requested rounding mode.
>>
>> There are a few ways to fix this one. One is to run the Newton loop 
>> to a higher-precision where these finer distinctions can be teased 
>> out. […]
>>
>> Another approach is to detect when the result is too large/too small 
>> and then subtract/add an ulp as a fix-up. This is the approach taken 
>> for BigDecimal.sqrt. […]
>
> This implementation change looks reasonable to me.
>
>> An approach not explored for this fix would be to arrange for the 
>> iteration to start from the "right" side of the number line depending 
>> on the rounding mode and then monotonically increase/decrease to 
>> approach the square root. […] I believe this is technically possible, 
>> but would require some additional analysis to setup.
>
> This approach seems more appealing and could perhaps be investigated 
> at a later date.
>
> In the test I think you want to replace “down” with “up" at line 238.
>
> Brian