RFR: 8334755: Asymptotically faster implementation of square root algorithm

[fabioromano1]

On Thu, 13 Jun 2024 18:31:33 GMT, fabioromano1 <duke at openjdk.org> wrote:

> I have implemented the Zimmermann's square root algorithm, available in works [here](https://inria.hal.science/inria-00072854/en/) and [here](https://www.researchgate.net/publication/220532560_A_proof_of_GMP_square_root).
> 
> The algorithm is proved to be asymptotically faster than the Newton's Method, even for small numbers. To get an idea of how much the Newton's Method is slow,  consult my article [here](https://arxiv.org/abs/2406.07751), in which I compare Newton's Method with a version of classical square root algorithm that I implemented. After implementing Zimmermann's algorithm, it turns out that it is faster than my algorithm even for small numbers.

src/java.base/share/classes/java/math/MutableBigInteger.java line 265:

> 263:      */
> 264:     final int compare(MutableBigInteger b) {
> 265:         this.normalize();

See [JDK-8334483](http://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-8334483)

src/java.base/share/classes/java/math/MutableBigInteger.java line 293:

> 291:      */
> 292:     private int compareShifted(MutableBigInteger b, int ints) {
> 293:         this.normalize();

See [JDK-8334483](http://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-8334483)

src/java.base/share/classes/java/math/MutableBigInteger.java line 826:

> 824:         while (x > 0 && y > 0) {
> 825:             x--; y--;
> 826:             int bval = y < addend.intLen ? addend.value[y+addend.offset] : 0;

See [JDK-8334434](https://bugs.openjdk.org/browse/JDK-8334434)

src/java.base/share/classes/java/math/MutableBigInteger.java line 897:

> 895:         rstart -= x;
> 896: 
> 897:         int len = Math.min(y, addend.intLen);

See [JDK-8334434](https://bugs.openjdk.org/browse/JDK-8334434)

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1644669348
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1644669676
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1644037011
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1644037695