Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v48]

2024-10-21 Thread duke
On Fri, 18 Oct 2024 08:36:30 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Refine comments to

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v48]

2024-10-21 Thread Raffaello Giulietti
On Fri, 18 Oct 2024 08:36:30 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Refine comments to

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v48]

2024-10-18 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Refine comments to point out the substructure of the method's contract better ---

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread fabioromano1
On Thu, 17 Oct 2024 15:19:52 GMT, fabioromano1 wrote: >> Will approve at the beginning of next week to let you add some last minute >> (not substantial) changes during the next few days. > >> In any reduction approach, you still need to prove that the reduced problem >> is equivalent to the ori

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread fabioromano1
On Thu, 17 Oct 2024 15:17:38 GMT, Raffaello Giulietti wrote: >> With the definition remainingZeros = scale - preferredScale, the proof above >> could be adapted almost on the fly to the old implementation. >> >> In any reduction approach, you still need to prove that the reduced problem >> is

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread Raffaello Giulietti
On Thu, 17 Oct 2024 15:12:32 GMT, Raffaello Giulietti wrote: >> @rgiulietti That's correct, although I prefer that the correctness is proved >> by "reducing the size of the problem" rather than "total number of removed >> powers", because it was the logic to prove implicitly the correctness of

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread Raffaello Giulietti
On Thu, 17 Oct 2024 14:51:28 GMT, fabioromano1 wrote: >> OK, let me reformulate the reasoning to check that we are in sync. >> For simplicity, I'm assuming that the powers of 2 are _not_ stripped away, >> so I'm using powers of 10 rather than powers of 5. Adding the powers of 2 >> optimization

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread fabioromano1
On Thu, 17 Oct 2024 14:29:36 GMT, Raffaello Giulietti wrote: >>> The comments are OK. However, there seems to be no explicit relation >>> between the "running" vars used in the reasoning and the expected outcome. >>> >>> To clarify what I mean, let v0, z0 and s0 be the initial values at method

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread Raffaello Giulietti
On Thu, 17 Oct 2024 12:59:37 GMT, fabioromano1 wrote: >> The comments are OK. However, there seems to be no explicit relation between >> the "running" vars used in the reasoning and the expected outcome. >> >> To clarify what I mean, let v0, z0 and s0 be the initial values at method >> entry o

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread fabioromano1
On Thu, 17 Oct 2024 12:38:29 GMT, Raffaello Giulietti wrote: > The comments are OK. However, there seems to be no explicit relation between > the "running" vars used in the reasoning and the expected outcome. > > To clarify what I mean, let v0, z0 and s0 be the initial values at method > entr

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-17 Thread Raffaello Giulietti
On Tue, 15 Oct 2024 09:56:30 GMT, fabioromano1 wrote: >> I would say yes... The invariant `i == max{n : 5^(2^n) <= 5^remainingZeros}` >> should be a sufficient condition to affirm it, indeed the 2nd loop ends when >> `remainingZeros == 0`, so `remainingZeros >= z` implies `z == 0`... > >> Yes,

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v47]

2024-10-15 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Refining the loop invariant for more clear proof - Changes: - all: htt

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread fabioromano1
On Tue, 15 Oct 2024 09:18:59 GMT, fabioromano1 wrote: >> Anyway, if you find a nice proof please add it to the comments. The >> algorithm is quite sophisticated, so it needs one. > > I would say yes... The invariant `i == max{n : 5^(2^n) <= 5^remainingZeros}` > should be a sufficient condition

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v46]

2024-10-15 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: More comments for correctness proof - Changes: - all: https://git.open

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread fabioromano1
On Tue, 15 Oct 2024 09:13:48 GMT, Raffaello Giulietti wrote: >> Yes, I considered that as well. >> Not sure, however, if this is sufficient to prove that intVal has been >> indeed divided by 5^z after the 2nd loop is terminated. > > Anyway, if you find a nice proof please add it to the comments

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread Raffaello Giulietti
On Tue, 15 Oct 2024 09:11:40 GMT, Raffaello Giulietti wrote: >> @rgiulietti Actually, an useful invariant for `remainingZeros` follows >> directly from its definition: letting `z = max{n : ((intVal * 2^powsOf2) % >> 10^n) == 0 && n <= scale - preferredScale}`, at the first iteration, it is >>

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread Raffaello Giulietti
On Tue, 15 Oct 2024 09:02:58 GMT, fabioromano1 wrote: >> While I intuitively understand, and I'm convinced of the clever algorithm, >> I'm struggling to find a proof, in particular to formulate a useful >> invariant for the first loop which seamlessly would bind with the second >> loop and its

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread fabioromano1
On Tue, 15 Oct 2024 08:23:23 GMT, Raffaello Giulietti wrote: >> @rgiulietti Or maybe "i.e., 5^(2^i) is larger than the largest power of five >> that is still removable from intVal", could it be ok? > > While I intuitively understand, and I'm convinced of the clever algorithm, > I'm struggling

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-15 Thread Raffaello Giulietti
On Mon, 14 Oct 2024 15:44:20 GMT, fabioromano1 wrote: >> OK, let me give it a try, maybe tomorrow. > > @rgiulietti Or maybe "i.e., 5^(2^i) is larger than the largest power of five > that is still removable from intVal", could it be ok? While I intuitively understand, and I'm convinced of the cl

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v45]

2024-10-14 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Apply suggestions from code review - Changes: - all: https://git.openj

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-14 Thread fabioromano1
On Mon, 14 Oct 2024 15:30:16 GMT, Raffaello Giulietti wrote: >> Maybe something like "too few powers of five left to remove with respect to >> the number of removable zeros in the initial value of intVal", I can't think >> of anything better for now... > > OK, let me give it a try, maybe tomor

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-14 Thread Raffaello Giulietti
On Mon, 14 Oct 2024 15:25:44 GMT, fabioromano1 wrote: >> It's hard for me to think of something more explicit than the mathematical >> definitions already present in the comments... > > Maybe something like "too few powers of five left to remove with respect to > the maximum number of removable

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-14 Thread fabioromano1
On Mon, 14 Oct 2024 15:16:49 GMT, fabioromano1 wrote: >> src/java.base/share/classes/java/math/BigDecimal.java line 5280: >> >>> 5278: BigInteger[] qr; // quotient-remainder pair >>> 5279: // Remove 5^(2^i) from the factors of intVal, until >>> 5^remainingZeros < 5^(2^i) >>> 528

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-14 Thread fabioromano1
On Mon, 14 Oct 2024 15:06:42 GMT, Raffaello Giulietti wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Added mathematical comments for maxPowsOf5 > > src/java.base/share/classes/java/math/BigDecimal.java line 5280:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-14 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 22:45:25 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Added mathematical

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v44]

2024-10-13 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Added mathematical comments for maxPowsOf5 - Changes: - all: https://g

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 16:57:33 GMT, fabioromano1 wrote: >> It can be proven by considering >> >> - the inequality | b * LOG_5_OF_2 - b log5(2) | < 2^(-21) >> - the properties of round() (to an integer) >> - log5(2) < 1/2 >> >> The last one is crucial for the upper bound to be m + 1 rather than m

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread j3graham
On Sun, 13 Oct 2024 17:48:15 GMT, j3graham wrote: >> src/java.base/share/classes/java/math/BigDecimal.java line 5234: >> >>> 5232: */ >>> 5233: private static BigInteger fiveToTwoToThe(int n) { >>> 5234: int i = Math.min(n, FIVE_TO_2_TO.length - 1); >> >> BigInteger has “getRad

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread j3graham
On Sun, 13 Oct 2024 14:39:32 GMT, j3graham wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Minor change > > src/java.base/share/classes/java/math/BigDecimal.java line 5234: > >> 5232: */ >> 5233: private

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread fabioromano1
On Sun, 13 Oct 2024 16:34:09 GMT, Raffaello Giulietti wrote: >>> What's really crucial for _correctness_ is to ensure maxPowsOf5 >= k. >> >> Yes, I meant that the only way we know to ensure that condition is to ensure >> `m <= maxPowsOf5`... >> >>> Perhaps leave m <= maxPowsOf5 <= m + 1 and m

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 16:18:03 GMT, fabioromano1 wrote: >> Perhaps leave m <= maxPowsOf5 <= m + 1 and maxPowsOf5 >= k and drop the note >> "and is never off by more than 1 from the theoretical m" > >> What's really crucial for _correctness_ is to ensure maxPowsOf5 >= k. > > Yes, I meant that the

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread fabioromano1
On Sun, 13 Oct 2024 16:06:34 GMT, Raffaello Giulietti wrote: >> 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 >> ma

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 16:03:09 GMT, Raffaello Giulietti wrote: >> @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

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 15:40:27 GMT, fabioromano1 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^

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v43]

2024-10-13 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Use log5(2) best approximation Co-authored-by: Raffaello Giulietti

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread fabioromano1
On Sun, 13 Oct 2024 13:13:30 GMT, Raffaello Giulietti wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Minor change > > src/java.base/share/classes/java/math/BigDecimal.java line 5270: > >> 5268: >> 5269:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sun, 13 Oct 2024 14:39:32 GMT, j3graham wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Minor change > > src/java.base/share/classes/java/math/BigDecimal.java line 5234: > >> 5232: */ >> 5233: private

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread fabioromano1
On Sun, 13 Oct 2024 14:39:32 GMT, j3graham wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Minor change > > src/java.base/share/classes/java/math/BigDecimal.java line 5234: > >> 5232: */ >> 5233: private

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread j3graham
On Sat, 12 Oct 2024 17:37:25 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Minor change src/j

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-13 Thread Raffaello Giulietti
On Sat, 12 Oct 2024 17:37:25 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Minor change After

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v42]

2024-10-12 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Minor change - Changes: - all: https://git.openjdk.org/jdk/pull/21323/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v41]

2024-10-12 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Update BigDecimal.java - Changes: - all: https://git.openjdk.org/jdk/p

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v40]

2024-10-12 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Refining comment - Changes: - all: https://git.openjdk.org/jdk/pull/21

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v39]

2024-10-12 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Refining comments describing the algorithm - Changes: - all: https://g

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v38]

2024-10-12 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Typo correction and code style simplification - Changes: - all: https:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v37]

2024-10-11 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Added comments explaining the algorithm in more details - Changes: - a

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v36]

2024-10-11 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Apply suggestions from code review Co-authored-by: Raffaello Giulietti Co-auth

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 19:45:23 GMT, fabioromano1 wrote: > This doesn't say much about `maxPowsOf5`, though. You are not using `intVal` > but 2^`bitLength` > `intVal` in the computation of `maxPowsOf5`. So maybe the > property you are looking for is `maxPowsOf5` - 1 <= log5(intVal) < > `maxPowsOf

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 19:38:03 GMT, Raffaello Giulietti wrote: > This doesn't say much about `maxPowsOf5`, though. You are not using `intVal` > but 2^`bitLength` > `intVal` in the computation of `maxPowsOf5`. So maybe the > property you are looking for is `maxPowsOf5` - 1 <= log5(intVal) < > `m

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Fri, 11 Oct 2024 19:25:51 GMT, fabioromano1 wrote: >> Sorry, this is not a good question, disregard. > >> As I asked above, what's the property that should hold? 5^`maxPowsOf5` <= >> `intVal` < 5^(`maxPowsOf5` + 1)? > > Yes, as `floor(log5(intVal)) == max{integer n : 5^n <= intVal}`. This d

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 19:09:50 GMT, Raffaello Giulietti wrote: >> As I asked above, what's the property that should hold? >> 5^`maxPowsOf5` <= `intVal` < 5^(`maxPowsOf5` + 1)? > > Sorry, this is not a good question, disregard. > As I asked above, what's the property that should hold? 5^`maxPowsOf

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Fri, 11 Oct 2024 19:01:19 GMT, Raffaello Giulietti wrote: >> And considering that `Math.round()` rounds to the closest integer, it also >> should assure `maxPowsOf5 >= floor(log5(intVal))`, giving a better upper >> bound. > > As I asked above, what's the property that should hold? > 5^`maxP

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Fri, 11 Oct 2024 18:55:28 GMT, fabioromano1 wrote: >>> If the mathematical value v of the product and its floating-point value fp >>> are separated by an integer i in such a way that fp < i < v, we are in >>> trouble: the ceilings will be different, even if the values are very close >>> to

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 18:51:21 GMT, fabioromano1 wrote: >> One might prove that this cannot happen for a specific approximation of >> log5(2), like `LOG_5_OF_2` and for all bit length, but I don't think it is >> worthwhile to put too much effort on this, given the performance figures. > >> If the

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 18:41:50 GMT, Raffaello Giulietti wrote: >> If the mathematical value v of the product and its floating-point value fp >> are separated by an integer i in such a way that fp < i < v, we are in >> trouble: the ceilings will be different, even if the values are very close >>

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Fri, 11 Oct 2024 18:32:01 GMT, Raffaello Giulietti wrote: >> Actually, if we reason in terms of "ulp vs precision", the computation >> should be safe: `Math.log()`'s results are within 1 ulp of the exact result, >> and the floating point operations are a multiplication and a division. The

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Fri, 11 Oct 2024 18:20:50 GMT, fabioromano1 wrote: >> IIUC, the code assumes that the floating-point computation >> `Math.ceil(intVal.bitLength() * LOG_5_OF_2)` has the same value as the >> mathematical ⌈ `intVal.bitLength()` × log5(2) ⌉. >> I don't think this is safe, as it might happen tha

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v35]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 17:40:21 GMT, Raffaello Giulietti wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Refining mathematical definition of remainingZeros > > src/java.base/share/classes/java/math/BigDecimal.java li

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread fabioromano1
On Fri, 11 Oct 2024 17:29:59 GMT, Raffaello Giulietti wrote: >> I'll have to check... >> ... tomorrow ;-) > > IIUC, the code assumes that the floating-point computation > `Math.ceil(intVal.bitLength() * LOG_5_OF_2)` has the same value as the > mathematical ⌈ `intVal.bitLength()` × log5(2) ⌉. >

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v35]

2024-10-11 Thread Andrey Turbanov
On Thu, 10 Oct 2024 20:36:26 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Refining mathematic

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v35]

2024-10-11 Thread Raffaello Giulietti
On Thu, 10 Oct 2024 20:36:26 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Refining mathematic

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-11 Thread Raffaello Giulietti
On Thu, 10 Oct 2024 21:54:27 GMT, Raffaello Giulietti wrote: >> Could make sense using Math.round() instead of Math.ceil() to get better >> upper bound? > > I'll have to check... > ... tomorrow ;-) IIUC, the code assumes that the floating-point computation `Math.ceil(intVal.bitLength() * LOG_

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-10 Thread Raffaello Giulietti
On Thu, 10 Oct 2024 20:25:09 GMT, fabioromano1 wrote: >> The name `maxPowsOf5` has been chosen for consistence with `powsOf2`. > > Could make sense using Math.round() instead of Math.ceil() to get better > upper bound? I'll have to check... ... tomorrow ;-) - PR Review Comment: ht

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v35]

2024-10-10 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Refining mathematical definition of remainingZeros - Changes: - all: h

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-10 Thread fabioromano1
On Thu, 10 Oct 2024 19:44:21 GMT, fabioromano1 wrote: >> src/java.base/share/classes/java/math/BigDecimal.java line 5270: >> >>> 5268: intVal = intVal.shiftRight(powsOf2); // remove powers of 2 >>> 5269: // maxPowsOf5 == ceil(log5(intVal)) roughly >>> 5270: long maxPowsOf

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v34]

2024-10-10 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Added comments on mathematical semantic - Changes: - all: https://git.

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-10 Thread fabioromano1
On Thu, 10 Oct 2024 16:12:57 GMT, Raffaello Giulietti wrote: >> fabioromano1 has updated the pull request incrementally with one additional >> commit since the last revision: >> >> Store log5(2) in BigDecimal > > src/java.base/share/classes/java/math/BigDecimal.java line 5270: > >> 5268:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-10 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 15:18:15 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Store log5(2) in Big

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-10 Thread Raffaello Giulietti
On Thu, 10 Oct 2024 07:32:15 GMT, fabioromano1 wrote: >> The class Javadoc mentions, in at least two places, that the two's >> complement representation conceptually has an infinite number of leading >> virtual sign bits. >> Once this point is clear, IMO the method's own Javadoc is then clear i

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-10 Thread fabioromano1
On Wed, 9 Oct 2024 21:11:16 GMT, Raffaello Giulietti wrote: >> @rgiulietti At least for me, the expression "the bits that differ from its >> sign bit" is misleading, it seems to implicitly imply that he is talking >> about the 1s bits which are not sign bits, while it means the bits whose >>

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 20:47:25 GMT, fabioromano1 wrote: >> What's wrong with the semantics? In my understanding, it should count the >> ones for non-negative values and the zeros for negative values, where >> non-negative values have an infinite prefix of zero bits and negative values >> have an

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread fabioromano1
On Wed, 9 Oct 2024 20:19:39 GMT, Raffaello Giulietti wrote: >> @rgiulietti I think I just found a problem much more serious than a simple >> optimization, I'm afraid the semantics of `BigInteger.bitCount()` is >> ill-defined, although it seems absurd to me that no one has noticed it so >> far

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread fabioromano1
On Wed, 9 Oct 2024 20:19:39 GMT, Raffaello Giulietti wrote: >> @rgiulietti I think I just found a problem much more serious than a simple >> optimization, I'm afraid the semantics of `BigInteger.bitCount()` is >> ill-defined, although it seems absurd to me that no one has noticed it so >> far

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-09 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 15:18:15 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Store log5(2) in Big

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 17:25:12 GMT, fabioromano1 wrote: >> If you are interested, you can create new PRs without reference to JBS >> issues, and I'll file them. >> As usual, it's easier for review purposes when each PR touches only small >> groups of strongly related changes rather than big modifi

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread fabioromano1
On Wed, 9 Oct 2024 16:17:59 GMT, Raffaello Giulietti wrote: >> @rgiulietti BTW of opening new issues, I've found that there are some >> optimizations and code simplifications that can be done in `BigInteger`'s >> bit operations that uses lowest non-zero word search, like `shiftRight()`, >> `g

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 16:03:05 GMT, fabioromano1 wrote: >> Oh right, `expandBigIntegerTenPowers()` indeed computes and stores a lot of >> values. >> >> I'm thinking of opening an issue to rewrite it to just keep the values that >> are actually computed as intermediate results of a repeated squari

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread fabioromano1
On Wed, 9 Oct 2024 15:46:37 GMT, Raffaello Giulietti wrote: >> @rgiulietti >> - About powers of two, there is a difference here: all powers of two are >> removed, not only the common, to use numbers as small as possible, and the >> powers are removed all in once, while if not they were remove

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread Raffaello Giulietti
On Wed, 9 Oct 2024 14:28:53 GMT, fabioromano1 wrote: >> Seems like `BigInteger`s division either takes care of removing common >> powers of 2 in the dividend and divisor (Knuth division), or removing them >> has no practical benefit (Burnikel-Ziegler). >> >> Thus, I'm wondering if using powers

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v33]

2024-10-09 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Store log5(2) in BigDecimal - Changes: - all: https://git.openjdk.org/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v32]

2024-10-09 Thread Raffaello Giulietti
On Mon, 7 Oct 2024 19:35:10 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Use log cache of Big

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread fabioromano1
On Wed, 9 Oct 2024 14:10:17 GMT, Raffaello Giulietti wrote: >> @rgiulietti FYI, I have found that `BigInteger` has already a cache for the >> repeated squares that uses in radix string conversion, and it is provided by >> the method `BigInteger.getRadixConversionCache(int radix, int exponent)`

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-09 Thread Raffaello Giulietti
On Mon, 7 Oct 2024 19:48:20 GMT, fabioromano1 wrote: >> `BigDecimal` was not designed to do astronomical computations. One would >> probably use other libraries for that, e.g., [GMP](https://gmplib.org/) and >> would not be interested too much in "stripping trailing zeros". >> The focus of this

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v32]

2024-10-09 Thread fabioromano1
On Mon, 7 Oct 2024 19:35:10 GMT, fabioromano1 wrote: >> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses >> repeated squares trick. > > fabioromano1 has updated the pull request incrementally with one additional > commit since the last revision: > > Use log cache of Big

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-07 Thread fabioromano1
On Fri, 4 Oct 2024 22:42:18 GMT, Raffaello Giulietti wrote: >> @rgiulietti Though, it's also true that if I want to do astronomical >> calculations, I probably have a machine that allows me to do so, and so I'd >> like to be able to make the most of it... > > `BigDecimal` was not designed to d

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v32]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Use log cache of BigInteger - Changes: - all: https://git.openjdk.org/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v31]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v30]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Correct typo in comment - Changes: - all: https://git.openjdk.org/jdk/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v29]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Speed up computation of shiftRight() and bitLength() - Changes: - all:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v28]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Minor change - Changes: - all: https://git.openjdk.org/jdk/pull/21323/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v27]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: More explaining variable identificator - Changes: - all: https://git.o

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v26]

2024-10-07 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with two additional commits since the last revision: - Correct indentation - Refine the estimate of remaining zeros - Change

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v25]

2024-10-05 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Minor change - Changes: - all: https://git.openjdk.org/jdk/pull/21323/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v24]

2024-10-05 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Optimization - Changes: - all: https://git.openjdk.org/jdk/pull/21323/

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v23]

2024-10-05 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: An optimization - Changes: - all: https://git.openjdk.org/jdk/pull/213

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v22]

2024-10-05 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with two additional commits since the last revision: - Correct documentation - Correct documentation - Changes: - all: htt

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v21]

2024-10-05 Thread fabioromano1
> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses > repeated squares trick. fabioromano1 has updated the pull request incrementally with one additional commit since the last revision: Changed caching of powers and removed superfluous condition - Changes:

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-04 Thread Raffaello Giulietti
On Fri, 4 Oct 2024 18:02:21 GMT, fabioromano1 wrote: >> It takes around 100 ms and less than 1 MB to build a table up to 20 rather >> than 29. >> It can be fully constructed in `static { ... }`, avoiding races. >> >> IMO, this would cover the vast majority of the cases encountered in practice.

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-04 Thread fabioromano1
On Fri, 4 Oct 2024 17:48:13 GMT, Raffaello Giulietti wrote: >> @rgiulietti Which means, however, wanting to work with a precision of >> billions of decimal digits, and therefore taking on the consequences... > > It takes around 100 ms and less than 1 MB to build a table up to 20 rather > than

Re: RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v12]

2024-10-04 Thread fabioromano1
On Fri, 4 Oct 2024 17:48:13 GMT, Raffaello Giulietti wrote: >> @rgiulietti Which means, however, wanting to work with a precision of >> billions of decimal digits, and therefore taking on the consequences... > > It takes around 100 ms and less than 1 MB to build a table up to 20 rather > than

  1   2   >