On Sun, 13 Oct 2024 15:40:27 GMT, fabioromano1 <d...@openjdk.org> wrote:
>> src/java.base/share/classes/java/math/BigDecimal.java line 5270:
>>
>>> 5268:
>>> 5269: intVal = intVal.shiftRight(powsOf2); // remove powers of 2
>>> 5270: // maxPowsOf5 >= floor(log5(intVal)) >= max{n : (intVal %
>>> 5^n) == 0}
>>
>> Suggestion:
>>
>> // Let k = max{n : (intVal % 5^n) == 0}, m = max{n : 5^n <= intVal},
>> so m >= k.
>> // Let b = intVal.bitLength(). It can be shown that
>> // | b * LOG_5_OF_2 - b log5(2) | < 2^(-21) (fp viz. real
>> arithmetic),
>> // which entails m <= maxPowsOf5 <= m + 1, where maxPowsOf5 is as
>> below.
>> // Hence, maxPowsOf5 >= k and is never off by more than 1 from the
>> theoretical m.
>
> @rgiulietti Good, but I would not put the inequality `maxPowsOf5 <= m + 1`
> and say that `maxPowsOf5` is never off by more than 1 from the theoretical
> `m`, because it is not crucial as `m <= maxPowsOf5`, and because `m` is in
> function of `intVal`, while `maxPowsOf5` is in function of `2^b`, so it is
> not obvious that there's no power of five `pow` such that `intVal < pow <
> 2^b`...
What's really crucial for _correctness_ is to ensure maxPowsOf5 >= k.
But for performance you also want maxPowsOf5 to be as small as possible. So,
the fact that it turns out that maxPowsOf5 <= m + 1 guarantees that maxPowsOf5
is the best value that can be computed very efficiently. It's more a "quality
of service" guarantee than anything fundamental.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/21323#discussion_r1798429260
