RFR: 8367603: Optimize exact division in BigDecimal [v13]

[Raffaello Giulietti]

On Mon, 15 Sep 2025 17:59:28 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> HI @fabioromano1,
>> Ah, I haven't worked on that code for exact divide in a while!
>> For some historical context, the method was added as part of JSR 13, Decimal Arithmetic Enhancement, in JDK 5. A fuller derivation of the old bound is discussed in:
>> 
>> Fixed, Floating, and Exact Computation with Java's BigDecimalFixed, Floating, and Exact Computation with Java's BigDecimal
>> Dr. Dobb's Journal · Jun 1, 2004
>> https://web.archive.org/web/20210505132021/http://www.drdobbs.com/jvm/fixed-floating-and-exact-computation-wit/184405721
>> 
>> At the time I wrote the code, I looked around at the usual sources, Knuth, etc. and asked around for a bound of decimal digits of 1/b if 1/b is representable, but didn't find anything.
>> 
>> I see you're still revising the implementation. Once this settles down, a review comment from me will be "restore some textual discussion of what the algorithm is doing."
>> 
>> For testing, I think it would be good to probe at some values where the old and new digit estimation techniques differ.
>> 
>> Also, I think both @rgiulietti and myself look at this PR before it goes back; I'll adjust the reviewer count accordingly.
>
> @jddarcy The technique used here is the following: take $a/b$, compute $b' = b/(2^i 5^j)$, where $i = \max(n \in N \mid b \equiv 0 \mod 2^n)$ and $j = \max(n \in N \mid b \equiv 0 \mod 5^n)$. If $a \not\equiv 0 \mod b'$, then $a/b$ is not a finite decimal number. Otherwise:
> 
> - if $i \le j$, then $a/b = (a/b') \cdot 2^{j-i} \cdot 10^{-j}$;
> - if $i > j$, then $a/b = (a/b') \cdot 5^{i-j} \cdot 10^{-i}$.

@fabioromano1 Please put the [comment above](https://github.com/openjdk/jdk/pull/27271#issuecomment-3293326363) in the appropriate spot in the `divide()` method, around L.1800.

More generally, everything not obvious should go in a comment in the code to help future improvements.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/27271#issuecomment-3328160026