You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "MaxFreedomPollard (via GitHub)" <gi...@apache.org> on 2026/09/07 13:12:02 UTC
[PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
MaxFreedomPollard opened a new pull request, #762:
URL: https://github.com/apache/datasketches-java/pull/762
`Util.numDigits(0)` and `Util.numDigits(1)` both return 0, and `Util.numDigits(1000000000000000000L)` returns 18 for a number with 19 digits.
The method is at `src/main/java/org/apache/datasketches/common/Util.java:805`:
```java
public static int numDigits(long n) {
if ((n % 10) == 0) { n++; }
return (int) ceil(log(n) / log(10));
}
```
The `n++` is there for exact multiples of ten, where `ceil` otherwise lands one short. It does not help 0 or 1: both reach `ceil(log(1) / log(10))`, which is `ceil(0.0)`, which is 0. It also stops working once a long has no exact double. At n = 1E18 the nudged value 1000000000000000001 rounds back to 1E18, the ratio comes out at 17.999999999999996, and `ceil` gives 18.
Measured on current main against `Long.toString(n).length()`:
```
n=0 current=0 expected=1
n=1 current=0 expected=1
n=1000000000000000000 current=18 expected=19
```
Everything from 2 to 999999999999999999 is already right, and so is `Long.MAX_VALUE`.
The fix drops the floating point for an integer loop, exact across the whole long range. Zero and negatives now return 1, which is what `LongsAsOrderableStrings.digits` in the test tree already does for `maxValue <= 0`. That method is the same computation and its javadoc caps it below 1E15; the loop has no ceiling.
The two halves are used together: `numDigits` sizes the pad that `longToFixedLengthString` and `LongsAsOrderableStrings.getString` apply so longs rendered as strings sort in numeric order. An under-reported width leaves the wider values unpadded and breaks that ordering.
Verification on macOS 15 aarch64, Temurin 25.0.4.1, Maven 3.9.16, toolchain per the README.
With only the new test applied to main, `mvn --toolchains ... test -Dtest=UtilTest -DfailIfNoTests=false` gives `Tests run: 44, Failures: 1` at `UtilTest.checkNumDigits:248 expected [1] but found [0]`. The same command with the fix gives `Tests run: 44, Failures: 0, Errors: 0, Skipped: 0`.
Every in-repo caller of `Util.numDigits` is a test class. Running all of them, `-Dtest=UtilTest,KllItemsSketchTest,KllMiscItemsTest,KllHelperTest,KllDirectCompactItemsSketchTest,PartitionBoundariesTest,KllCrossLanguageTest`, gives `Tests run: 134, Failures: 0, Errors: 0, Skipped: 0`.
Full suite with the fix, `mvn --toolchains ... test`, single threaded: `Tests run: 2208, Failures: 0, Errors: 0, Skipped: 0`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#issuecomment-5576527483
Thank you for finding this. I did a library search and this little function is used in many places. It is 100% used in test and 100% used in conjunction with Util.longToFixedLengthString(long number, int length), which means it is used for printing alignment to make numbers easier to read in columns. Every case only uses positive numbers, so far.
Nonetheless, you have correctly found a more robust way of computing this function that works over a wider range of positive numbers. So why stop there? If we are going to the trouble to fix this function, why not make it even more useful and allow it to work for negative numbers as well and make the documentation more clear.
Let's assume the context is printing alignment of simply expressed decimal numbers with the possibility of a minus sign for negative number, but no commas, underscores or other special characters. This assumption needs to be in the javadoc. I would alter your approach to make the algorithm more visible:
```java
/**
* Computes the minimum number of characters required to print the number n as a decimal.
* Negative numbers add one for the minus sign character.
* No other non-digit characters are assumed.
* @param n the given number, which may be negative.
* @return the number of characters required to print the number n as a decimal
*/
public static int numDigits(final long n) {
if (n == 0) { return 1; } // handles the zero special case
int count = (n < 0) ? 1 : 0; // handles the minus sign
while (n != 0) {
n /= 10;
count++;
}
return count;
}
```
Your test uses magic numbers, let's not do that:
```java
@Test
static void checkNumDigits() {
for (long n = 1; n < Long.MAX_VALUE && n > 0; n *= 10) {
checkN(n);
checkN(n - 1);
checkN(-n);
checkN(-n + 1);
}
checkN(Long.MAX_VALUE);
checkN(Long.MIN_VALUE);
}
private static void checkN(long n) {
assertEquals(numDigits2(n), String.valueOf(n).length());
}
```
If you want to redo this PR more like the above then go ahead. If not, let me know and I'll submit a separate PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#issuecomment-5655335024
Interesting. GitHub Advanced Security identified a condition that is always true, but it identified (n > 0), the wrong one!
In the expression:
`for (long n = 1; n < Long.MAX_VALUE && n > 0; n *= 10) {}`
It is the (n < Long.MAX_VALUE) that is always true not the (n > 0). So this expression could be simplified to:
`for (long n = 1; n > 0; n *= 10) {}` // When rollover occurs it initially goes negative, which halts the loop.
I should have caught that, my bad.
Nonetheless, I still prefer this simple loop over what you did and here is why:
YOU know that 10^18 is the largest multiple of 10 that doesn't exceed Long.MAX_VALUE. So you set maxExp = 18, again a magic value. So the success of your loop depends on this magic value.
It is preferable to not depend on magic values if we don't have to, because magic values can become incorrect if something else in this little algorithm changed ... like if _n_ was defined as a 32 bit signed integer. Magic numbers can be fragile.
Instead let's use intrinsic properties of the language: when a signed positive integer rolls over it becomes negative. This is independent of whether _n_ is defined as a byte, short, int or long.
And what is this loop from -1000 to 1000 all about? Are you concerned that the main loop will miss a value that will fail?
If you closely examine the actual sequence of values of _n_ from the main loop you will discover the sequence:
_n_ = 1, 0, -1, 0, 10, 9, -10, -9, 100, 99, -100, -99, 1000, 999, -1000, -999 ...
In the decimal system, the points where the number of decimal characters change are the transitions:
-1 <-> 0, 9 <-> 10, -10 <-> -9, 100 <-> 99, -100 <-> -99, etc.
If we know our algorithm works at all the transition points, it is easy to show that it will work for all the numbers in between. The only transition left is the Long.MAX_VALUE, Long.MIN_VALUE, which is also tested.
So I would prefer if you change the test method back to what I suggested before, minus the redundant condition that I missed:
```
/**
* Check all the transition points where the number of decimal characters change.
*/
@Test
static void checkNumDigits() {
for (long n = 1; n > 0; n *= 10) { // n goes negative on rollover, which halts the loop.
checkN(n);
checkN(n - 1);
checkN(-n);
checkN(-n + 1);
}
checkN(Long.MAX_VALUE);
checkN(Long.MIN_VALUE);
}
private static void checkN(long n) {
assertEquals(numDigits2(n), String.valueOf(n).length());
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#issuecomment-5622246677
@MaxFreedomPollard,
Thank you for you interest in our library.
With respect to this particular item, if I don't hear from you in the next few days I will assume you are not interested in following up and I will submit my own PR.
Cheers,
Lee.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "github-advanced-security[bot] (via GitHub)" <gi...@apache.org>.
github-advanced-security[bot] commented on code in PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#discussion_r3975543229
##########
src/test/java/org/apache/datasketches/common/UtilTest.java:
##########
@@ -241,6 +242,25 @@
assertEquals(out,"zzzzzzzzzzzzPad 30, prepend z:");
}
+ @Test
+ public void checkNumDigits() {
+ for (long n = -1000; n <= 1000; n++) {
+ checkN(n);
+ }
+ for (long n = 1; (n < Long.MAX_VALUE) && (n > 0); n *= 10) {
Review Comment:
## CodeQL / Useless comparison test
Test is always true.
[Show more details](https://github.com/apache/datasketches-java/security/code-scanning/971)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho merged PR #762:
URL: https://github.com/apache/datasketches-java/pull/762
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "MaxFreedomPollard (via GitHub)" <gi...@apache.org>.
MaxFreedomPollard commented on PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#issuecomment-5671602978
Done, pushed as accfafb.
Before the check runs again, one thing worth knowing: the alert was raised against `n > 0`, not against `n < Long.MAX_VALUE`. CodeQL's range analysis does not model signed overflow, so from `long n = 1` and `n *= 10` it concludes n never drops below 1 and calls `n > 0` always true. It has no upper bound for n, which is why it said nothing about `n < Long.MAX_VALUE`. This version keeps `n > 0` as the only condition, so I expect alert 971 to come back once the workflow is approved on this commit.
The loop behaves exactly as you described: 19 iterations, last positive value 1E18, and 1E18 * 10 wraps to -8446744073709551616, which ends it. The generated sequence matches the one you wrote out, and the test passes.
I kept `public void` to match every other @Test in UtilTest and left `final` on checkN's parameter. TestNG 7.12 does run a package-private static @Test, so say the word if you would rather have the exact shape you wrote.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] Fix Util.numDigits returning 0 for 0 and 1, and 18 for 1E18 (datasketches-java)
Posted by "github-advanced-security[bot] (via GitHub)" <gi...@apache.org>.
github-advanced-security[bot] commented on code in PR #762:
URL: https://github.com/apache/datasketches-java/pull/762#discussion_r4021258454
##########
src/test/java/org/apache/datasketches/common/UtilTest.java:
##########
@@ -241,6 +242,25 @@
assertEquals(out,"zzzzzzzzzzzzPad 30, prepend z:");
}
+ /**
+ * Check all the transition points where the number of decimal characters change.
+ */
+ @Test
+ public void checkNumDigits() {
+ for (long n = 1; n > 0; n *= 10) { //n goes negative on rollover, which halts the loop
Review Comment:
## CodeQL / Useless comparison test
Test is always true.
[Show more details](https://github.com/apache/datasketches-java/security/code-scanning/973)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org