This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
The following commit(s) were added to refs/heads/master by this push:
new a7dc330d Bound the work performed in the exact p-value computation
a7dc330d is described below
commit a7dc330d7460bfbfb3b167c0931cd4e52bdcb59d
Author: Alex Herbert <[email protected]>
AuthorDate: Sat Aug 29 17:10:30 2026 +0100
Bound the work performed in the exact p-value computation
---
.../statistics/inference/KolmogorovSmirnovTest.java | 18 ++++++++++++++++++
.../inference/KolmogorovSmirnovTestTest.java | 6 ++++++
src/changes/changes.xml | 7 +++++++
3 files changed, 31 insertions(+)
diff --git
a/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTest.java
b/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTest.java
index 64d6b893..e766c051 100644
---
a/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTest.java
+++
b/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTest.java
@@ -90,6 +90,15 @@ public final class KolmogorovSmirnovTest {
* than LARGE_SAMPLE^2 so all AUTO p-values attempt an exact computation,
i.e.
* at least 10000^2 ~ 2^26.56. */
private static final long MAX_LCM_TWO_SAMPLE_EXACT_P = 1L << 31;
+ /** The maximum number of terms to process in the exact p-value
computation for the
+ * two-sample two-sided statistic with unequal sample sizes. The lcm limit
+ * ({@link #MAX_LCM_TWO_SAMPLE_EXACT_P}) bounds the number of distinct
p-values but
+ * not the work required to compute one; Sample sizes with a large
greatest common
+ * divisor pass the lcm limit with {@code O(n * m)} work. This limit
bounds the work.
+ * It must be larger than LARGE_SAMPLE^2 so all AUTO p-values attempt an
exact
+ * computation. To avoid overflow during computation this uses half the
maximum number
+ * of terms to compute. */
+ private static final long HALF_MAX_TERMS_TWO_SAMPLE_EXACT_P = 1L << 30;
/** Placeholder to use for the two-sample sign array when the value can be
ignored. */
private static final int[] IGNORED_SIGN = new int[1];
/** Placeholder to use for the two-sample ties D array when the value can
be ignored. */
@@ -1152,6 +1161,15 @@ public final class KolmogorovSmirnovTest {
// if n and m are 2^31-1, i = n, dnm = n*m: (2^31-1)^2 + (2^31-1)^2 +
2^31-1 < 2^63
final long dnm = d * gcd;
+ // The lcm bounds the number of distinct p-values, not the work to
compute one.
+ // The inner loop processes a window of approximately 2*dnm/n + 1
values of j
+ // for each of the n values of i: terms <= min(n * (m + 1), 2 * dnm +
2 * n).
+ // Fail-fast when the work is impractical; the caller falls back to the
+ // asymptotic p-value approximation. Avoid overflow in 2 * dnm using a
half-threshold.
+ if (Math.min(n * (m + 1L) >>> 1, dnm + n) >
HALF_MAX_TERMS_TWO_SAMPLE_EXACT_P) {
+ return -1;
+ }
+
// Viehmann (2021): Updated for i in [0, n], j in [0, m]
// C_i,j = 1 if |i/n - j/m| >= d
// = 0 if |i/n - j/m| < d
and (i=0 or j=0)
diff --git
a/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTestTest.java
b/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTestTest.java
index 3804093e..8d3e7ff5 100644
---
a/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTestTest.java
+++
b/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/KolmogorovSmirnovTestTest.java
@@ -562,6 +562,12 @@ class KolmogorovSmirnovTestTest {
builder.add(Arguments.of(Integer.MAX_VALUE, 37, 3L *
Integer.MAX_VALUE, false, -1, 0));
builder.add(Arguments.of(Integer.MAX_VALUE, 37, 3L *
Integer.MAX_VALUE, true, -1, 0));
+ // Case where the lcm limit passes but the computation work is bounded.
+ // Commensurate sizes: gcd(2000000, 1000000) = 1000000; n*m/gcd =
2000000 (2^20.9)
+ // but the work for a large D is ~ min(n*(m+1), 2*dnm + 2n) ~ 2^41.4.
+ builder.add(Arguments.of(2000000, 1000000, 1500000000000L, false, -1,
0));
+ builder.add(Arguments.of(2000000, 1000000, 1500000000000L, true, -1,
0));
+
// Square underflow. These match the 2 * p1 where p1 is the one-sided
p-value
builder.add(Arguments.of(538, 538, 538 * 538, false, 2 * 4.9E-323, 0));
builder.add(Arguments.of(539, 539, 539 * 539, false, 2 * 1.5E-323, 0));
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 1b442813..ef612916 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -53,6 +53,13 @@ If the output is not quite correct, check for invisible
trailing spaces!
</properties>
<body>
<release version="1.4" date="TBD" description="Adds new features (requires
Java 8).">
+ <action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert">
+ "KolmogorovSmirnovTest": Bound the maximum number of terms allowed
during
+ the exact p-value computation for the two-sample two-sided statistic
with
+ unequal sample sizes. The caller will fall-back to the aysymptotic
+ computation to avoid an impractical computation. Behaviour using the
+ default AUTO limit is unchanged.
+ </action>
<action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert">
"ZipfDistribution": Update documentation on possible long runtimes when
using the distribution with a large number of elements.
