On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
On Fri, 2 Aug 2024 06:31:05 GMT, fabioromano1 wrote:
> Mmh, benchmarks show a slight slowdown with the iterative variant (except for
> the XS case). I tried several times, this one is the most favorable run:
>
> ```
> BenchmarkMode Cnt Score Error Units
> BigI
On Thu, 1 Aug 2024 21:38:47 GMT, Raffaello Giulietti
wrote:
> Mmh, benchmarks show a slight slowdown with the iterative variant (except for
> the XS case). I tried several times, this one is the most favorable run:
>
> ```
> BenchmarkMode Cnt Score Error Unit
On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
On Thu, 1 Aug 2024 19:10:51 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Last small changes
>
> I guess the overhead is negligible when compared to the arithmetic operation
> (shifts,
On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
On Thu, 1 Aug 2024 10:22:10 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Last small changes
>
> I have no further comments, but I'll wait for a couple of days more before
> approving,
On Thu, 1 Aug 2024 10:16:59 GMT, fabioromano1 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
> 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 New
On Wed, 31 Jul 2024 18:52:12 GMT, fabioromano1 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
On Wed, 31 Jul 2024 18:52:12 GMT, fabioromano1 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
> 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 New
> 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 New
On Sat, 27 Jul 2024 15:01:30 GMT, fabioromano1 wrote:
>> On my M1 Pro/32 GiB
>>
>> Current
>>
>> Benchmark Mode CntScore
>> Error Units
>> BigIntegerSquareRoot.testBigSqrtAndRemainderavgt 15 45.655 ?
>> 0.273 ns/op
>> BigInt
On Mon, 29 Jul 2024 20:51:39 GMT, Raffaello Giulietti
wrote:
>>> 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
>>
On Mon, 29 Jul 2024 18:25:54 GMT, fabioromano1 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
On Mon, 29 Jul 2024 16:48:32 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> If the input is a square, then s0 == 0, so testing for non-zero remainder
>> is redundant
>
> src/java.base/sh
On Mon, 29 Jul 2024 16:50:32 GMT, Raffaello Giulietti
wrote:
> 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
On Mon, 29 Jul 2024 16:50:10 GMT, Raffaello Giulietti
wrote:
> 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 t
On Mon, 29 Jul 2024 17:00:09 GMT, Raffaello Giulietti
wrote:
> Sorry, not `<<` but `*`
or `(x.intLen & 1) << 5`
-
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1695649080
On Mon, 29 Jul 2024 16:49:04 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> If the input is a square, then s0 == 0, so testing for non-zero remainder
>> is redundant
>
> src/java.base/sh
On Mon, 29 Jul 2024 13:18:16 GMT, fabioromano1 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
> 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 New
> 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 New
On Sat, 27 Jul 2024 14:44:15 GMT, fabioromano1 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
On Sat, 27 Jul 2024 14:55:04 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with two additional
>> commits since the last revision:
>>
>> - Correct test method name
>> - Updated sqrt speed test benchmark
>
> On my M1 Pro/32 GiB
>
> Current
>
> Be
On Sat, 27 Jul 2024 14:44:15 GMT, fabioromano1 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
> 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 New
On Sat, 27 Jul 2024 13:46:14 GMT, Raffaello Giulietti
wrote:
>> The benchmark `BigIntegers.java`, on which I based this, has the same
>> problem.
>
> It wasn't the overflow by itself that worried me, but that a later invocation
> of `sqrt*()` could throw.
>
> Again, the "huge" numbers are les
On Sat, 27 Jul 2024 12:18:19 GMT, fabioromano1 wrote:
>> test/micro/org/openjdk/bench/java/math/BigIntegerSquareRoot.java line 74:
>>
>>> 72:
>>> 73: for (int i = 0; i < TESTSIZE; i++) {
>>> 74: int value = Math.abs(r.nextInt());
>>
>> There's a risk of an overflow here if
> 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 New
> 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 New
On Sat, 27 Jul 2024 11:47:23 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> More accurate condition for MBI.safeRightShift()
>
> test/micro/org/openjdk/bench/java/math/BigIntegerSquareRoo
On Sat, 27 Jul 2024 09:40:54 GMT, fabioromano1 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
> 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 New
> 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 New
On Wed, 24 Jul 2024 13:20:31 GMT, fabioromano1 wrote:
>> The aim is not about having even more efficient code (yours is already
>> faster than the existing algorithm), but to have simpler code.
>>
>> The two denormalization code snippets, while based on the same underlying
>> math, are quite d
> 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 New
> 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 New
> 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 New
On Wed, 24 Jul 2024 11:46:03 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Made normalization consistent with that of the C code in the paper
>
> The aim is not about having even more ef
> 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 New
> 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 New
On Wed, 24 Jul 2024 10:32:08 GMT, fabioromano1 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
On Wed, 24 Jul 2024 10:07:48 GMT, Raffaello Giulietti
wrote:
> As I see it, there are some advantages in making the PR code as similar as
> possible to the code in the paper:
>
> * It might result in simpler code (and maybe even faster code).
>
> * It would make the Java code easier t
> 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 New
On Thu, 18 Jul 2024 17:22:50 GMT, fabioromano1 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
On Tue, 23 Jul 2024 15:19:30 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Conditions' order reversed in MBI.ulongSqrt()
>
> To clarify, the PR's code seems correct, but I wonder if it c
On Tue, 23 Jul 2024 15:16:27 GMT, Raffaello Giulietti
wrote:
> AFAIU, the wrapper performs the normalization, invokes the core algorithm,
> and does the denormalization just before returning the final result. There's
> no mention that normalization/denormalization need to be performed at each
On Thu, 18 Jul 2024 17:22:50 GMT, fabioromano1 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
On Thu, 18 Jul 2024 17:22:50 GMT, fabioromano1 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
On Tue, 23 Jul 2024 14:42:36 GMT, Raffaello Giulietti
wrote:
> AFAIU, in the Bertot, Magaud, Zimmermann paper there is just one
> "denormalization" step in the wrapper, before returning the final result to
> the client.
>
> Here, there seems to be a denormalization before returning from each
On Thu, 18 Jul 2024 17:22:50 GMT, fabioromano1 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
On Thu, 18 Jul 2024 16:14:02 GMT, fabioromano1 wrote:
>> I guess you are concerned about an overflow in `s2 + 2 * s`?
>>
>> If s = 2^32 - 1, then s2 = 2^64 - 2·2^32 + 1 and 2s = 2·2^32 - 2, without
>> overflows.
>> Thus, s2 + 2s = 2^64 - 1, without overflows.
>
> @rgiulietti True, it's almost b
> 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 New
> 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 New
On Thu, 18 Jul 2024 16:06:31 GMT, Raffaello Giulietti
wrote:
>>> Experimentally, the following seems a bit faster. In some cases, it avoids
>>> a full multiplication, some updates, and has one less test. I hope it is
>>> correct as well ;-)
>>
>> It's a nice code, but I'm afraid that if `s ==
On Thu, 18 Jul 2024 15:55:08 GMT, fabioromano1 wrote:
>> src/java.base/share/classes/java/math/MutableBigInteger.java line 2032:
>>
>>> 2030: s = s1;
>>> 2031: }
>>> 2032: return s;
>>
>> Experimentally, the following seems a bit faster.
>> In some cases, it avoi
On Thu, 18 Jul 2024 15:27:53 GMT, Raffaello Giulietti
wrote:
> Experimentally, the following seems a bit faster. In some cases, it avoids a
> full multiplication, some updates, and has one less test. I hope it is
> correct as well ;-)
It's a nice code, but I'm afraid that if `s == LONG_MASK`
On Thu, 18 Jul 2024 15:22:39 GMT, Raffaello Giulietti
wrote:
>> I found the way: I can test directly the code through
>> `java.math.Accessor.java`
>
> I think there's a misunderstanding here.
>
> What I'd like to see is a test that verifies the claim
>
> /* For every long value s in [
On Thu, 18 Jul 2024 13:09:08 GMT, fabioromano1 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
On Thu, 18 Jul 2024 15:09:41 GMT, fabioromano1 wrote:
>>> I mean only restricted to unsigned `long` perfect squares, something like
>>> the following, but written as a proper test
>>>
>>> ```
>>> long i = 0;
>>> for (; i < 1L << 32; ++i) {
>>> long x = i * i;
>>>
On Thu, 18 Jul 2024 15:01:22 GMT, fabioromano1 wrote:
>> It takes about 5 s on my laptop.
>
>> I mean only restricted to unsigned `long` perfect squares, something like
>> the following, but written as a proper test
>>
>> ```
>> long i = 0;
>> for (; i < 1L << 32; ++i) {
>>
On Thu, 18 Jul 2024 14:55:30 GMT, fabioromano1 wrote:
>> src/java.base/share/classes/java/math/MutableBigInteger.java line 2135:
>>
>>> 2133: * @param limit the offset which is the end of valid words in the
>>> input value
>>> 2134: * @param blockLen the length of the block in units o
On Thu, 18 Jul 2024 14:50:00 GMT, Raffaello Giulietti
wrote:
>> I mean only restricted to unsigned `long` perfect squares, something like
>> the following, but written as a proper test
>>
>>
>> long i = 0;
>> for (; i < 1L << 32; ++i) {
>> long x = i * i;
>>
On Thu, 18 Jul 2024 13:40:38 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> More accurate comment
>
> src/java.base/share/classes/java/math/MutableBigInteger.java line 2135:
>
>> 2133:
On Thu, 18 Jul 2024 14:39:16 GMT, fabioromano1 wrote:
>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1973:
>>
>>> 1971:
>>> 1972: /* For every long value s in [0, 2^32) such that x == s *
>>> s,
>>> 1973: * it is true that s == Math.round(Math.sqr
On Thu, 18 Jul 2024 14:49:19 GMT, Raffaello Giulietti
wrote:
>> I did it, although I'm afraid it takes up too much running time due to the
>> overhead of BigInteger's wrapping...
>
> I mean only restricted to unsigned `long` perfect squares, something like the
> following, but written as a pro
On Thu, 18 Jul 2024 13:39:01 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> More accurate comment
>
> src/java.base/share/classes/java/math/MutableBigInteger.java line 1973:
>
>> 1971:
On Wed, 17 Jul 2024 15:33:39 GMT, fabioromano1 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
> 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 New
> 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 New
On Wed, 17 Jul 2024 16:39:10 GMT, fabioromano1 wrote:
>> Can try with the old release and the incorrect code again?
>> If the results disagree with newer releases then I'd be interested in which
>> release you were using, as to analyze the generated code and possibly file a
>> bug report for th
On Wed, 17 Jul 2024 16:16:12 GMT, Raffaello Giulietti
wrote:
>> Can try with the old release and the incorrect code again?
>> If the results disagree with newer releases then I'd be interested in which
>> release you were using, as to analyze the generated code and possibly file a
>> bug repor
On Wed, 17 Jul 2024 16:16:12 GMT, Raffaello Giulietti
wrote:
>> Can try with the old release and the incorrect code again?
>> If the results disagree with newer releases then I'd be interested in which
>> release you were using, as to analyze the generated code and possibly file a
>> bug repor
On Wed, 17 Jul 2024 15:59:30 GMT, fabioromano1 wrote:
>> Sorry, disregard the above as it doesn't work for x = 0.
>
> @rgiulietti Probably I used a too older release to try the incorrect code
Can try with the old release and the incorrect code again?
If the results disagree with newer releases t
On Wed, 17 Jul 2024 16:15:47 GMT, Raffaello Giulietti
wrote:
>> @rgiulietti Probably I used a too older release to try the incorrect code
>
> Can try with the old release and the incorrect code again?
> If the results disagree with newer releases then I'd be interested in which
> release you we
On Wed, 17 Jul 2024 15:11:36 GMT, Raffaello Giulietti
wrote:
>> Also, this avoids a test
>>
>> if (Long.compareUnsigned(x, s * s - 1) <= 0) { // benign over-
>> and underflows
>> s--;
>> }
>
> Sorry, disregard the above as it doesn't work for x = 0.
@r
> 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 New
On Wed, 17 Jul 2024 15:11:36 GMT, Raffaello Giulietti
wrote:
>> Also, this avoids a test
>>
>> if (Long.compareUnsigned(x, s * s - 1) <= 0) { // benign over-
>> and underflows
>> s--;
>> }
>
> Sorry, disregard the above as it doesn't work for x = 0.
>
> 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 New
On Wed, 17 Jul 2024 15:08:22 GMT, Raffaello Giulietti
wrote:
>> @rgiulietti This is so strange... anyway, I tried also `long x = n * n`,
>> `long s = Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64))` with the test `s <
>> n`, which I think it's more mathematically natural, and also this never
On Wed, 17 Jul 2024 14:30:33 GMT, fabioromano1 wrote:
>> I tried on older release, they all agree.
>
> @rgiulietti This is so strange... anyway, I tried also `long x = n * n`,
> `long s = Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64))` with the test `s <
> n`, which I think it's more mathemati
On Wed, 17 Jul 2024 14:11:20 GMT, fabioromano1 wrote:
>> There are no counterexamples for perfect squares if you write `long s =
>> (long) Math.rint(Math.sqrt(x >= 0 ? x : x + 0x1p64));`.
>
> @rgiulietti Is it normal that the same code did not find counterexamples
> until recently, and now it f
On Wed, 17 Jul 2024 14:17:48 GMT, Raffaello Giulietti
wrote:
>> @rgiulietti Is it normal that the same code did not find counterexamples
>> until recently, and now it finds them?
>
> I tried on older release, they all agree.
@rgiulietti This is so strange... anyway, I tried also `long x = n *
On Wed, 17 Jul 2024 13:57:20 GMT, Raffaello Giulietti
wrote:
>> I hope these errors are not due to an implementation change in the virtual
>> machine instructions...
>
> There are no counterexamples for perfect squares if you write `long s =
> (long) Math.rint(Math.sqrt(x >= 0 ? x : x + 0x1p64
On Wed, 17 Jul 2024 13:57:06 GMT, fabioromano1 wrote:
>> In fact, if you run this code:
>> `long limit = 1L << 32;
>> for (long n = 0; n < limit; n++) {
>> long x = n * n;
>> if (n != (long) Math.sqrt(x >= 0 ? x : x + 0x1p64)) {
>> System.out.println(n);
>> }
>> }`
>>
On Wed, 17 Jul 2024 13:48:59 GMT, fabioromano1 wrote:
>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1978:
>>
>>> 1976: * is either correct, or rounded up by one if the value
>>> is too high
>>> 1977: * and too close to the next perfect square.
>>
On Wed, 17 Jul 2024 13:15:17 GMT, Raffaello Giulietti
wrote:
>> fabioromano1 has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Optimized shift-and-add operations
>
> src/java.base/share/classes/java/math/MutableBigInteger.java line 1978:
On Mon, 15 Jul 2024 19:58:23 GMT, fabioromano1 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
On Mon, 15 Jul 2024 19:58:23 GMT, fabioromano1 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
> 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 New
> 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 New
> 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 New
> 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 New
On Fri, 12 Jul 2024 14:39:51 GMT, Raffaello Giulietti
wrote:
>> The full explanation for the unnormalization is in the second paper, "A
>> proof of GMP square root", par. 3.2 at page 11.
>
> Well, I have to compare that section, which is clear to me, with the code
> again.
@rgiulietti I notic
> 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 New
On Fri, 12 Jul 2024 14:22:33 GMT, fabioromano1 wrote:
>> src/java.base/share/classes/java/math/MutableBigInteger.java line 2054:
>>
>>> 2052:
>>> 2053: rem.add(ONE);
>>> 2054: rem.subtract(twiceSqrt);
>>
>> Shouldn't these be `rem + twiceSqrt - 1`?
>
> No, becau
1 - 100 of 168 matches
Mail list logo
