RFR: 8334755: Asymptotically faster implementation of square root algorithm [v47]

[Raffaello Giulietti]

On Mon, 29 Jul 2024 18:25:54 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 550:
>> 
>>> 548:      */
>>> 549:     void safeRightShift(int n) {
>>> 550:         if (n >= bitLength()) {
>> 
>> The commit message for this reads `More accurate condition for MBI.safeRightShift()`.
>> If the old version works, please switch back. But if this is a genuine bug, then it needs a separate bug issue and PR.
>
> @rgiulietti The code of `MBI.safeRightShift()` works, but it seems that its correctness relies on the implementation of `MBI.rightShift()`, rather than on its own documentation or on that of  `MBI.rightShift()`. The real problem is that, as usual, the preconditions of `MBI.rightShift()` are not clearly specified.

I tend to agree with your point of view, but
- it is a bug: then it needs to be tracked and improved in a separate JBS issue and a separate PR
- or it is not a bug, then it should not be modified in the scope of this PR if it works in the original version
You can, of course, add a comment about the precondition you identified by working on this PR, as you did in other methods ("Assumes that ...).

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1946:
>> 
>>> 1944:      * @implNote The implementation is based on Zimmermann's works available
>>> 1945:      * <a href="https://inria.hal.science/inria-00072854/en/">  here</a> and
>>> 1946:      * <a href="https://www.researchgate.net/publication/220532560_A_proof_of_GMP_square_root">  here</a>
>> 
>> The following variant should be preferred, as it has a readable figure on p. 21, whereas the same figure in the variant linked in the PR seems broken for some reason.
>> https://inria.hal.science/inria-00072113/document
>
>> The following variant should be preferred, as it has a readable figure on p. 21, whereas the same figure in the variant linked in the PR seems broken for some reason. https://inria.hal.science/inria-00072113/document
> 
> What is the figure? I can view the same things in both versions... maybe it's a problem of the pdf reader or of the file?

I'm referring to the figure that depicts the memory layout during the core algorithm (p.22 resp. p.21, depending on the variant).
I tried on macOS with the standard Preview app, on Windows with Adobe Reader, on kubuntu with the standard reader, and with the reader built in Firefox.

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1948:
>> 
>>> 1946:      * <a href="https://www.researchgate.net/publication/220532560_A_proof_of_GMP_square_root">  here</a>
>>> 1947:      */
>>> 1948:     private MutableBigInteger[] sqrtRemZimmermann(int len, boolean needRemainder) {
>> 
>> This should be called `sqrtRemKaratsuba()`. This is the name chosen by Paul Zimmermann himself.
>> 
>> Also, I wonder if it wouldn't be simpler for `len` to represent the `int` length of the square root rather than the `int` length of the argument. It would be more consistent with the Bertot, Magaud, Zimmermann paper and might slightly simplify some later computation. But I'm not sure.
>
>> Also, I wonder if it wouldn't be simpler for `len` to represent the `int` length of the square root rather than the `int` length of the argument. It would be more consistent with the Bertot, Magaud, Zimmermann paper and might slightly simplify some later computation. But I'm not sure.
> 
> Maybe. I think rather that representing the length of the square root is a bit confusing, since in recursive algorithms it's a more common practice to use the length of the input as an argument...

Up to you.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1695899148
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1695900955
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1695901939