You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2023/12/23 19:51:22 UTC
(commons-statistics) 02/02: STATISTICS-81: Add integer sum of squares implementation
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
commit b560d2aad985b656ee0194f2ea798e780d6186b4
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Sat Dec 23 19:43:41 2023 +0000
STATISTICS-81: Add integer sum of squares implementation
---
.../statistics/descriptive/IntSumOfSquares.java | 206 +++++++++++++++++++++
.../statistics/descriptive/LongSumOfSquares.java | 181 ++++++++++++++++++
.../commons/statistics/descriptive/UInt128.java | 25 +++
.../commons/statistics/descriptive/UInt192.java | 25 +++
.../descriptive/IntSumOfSquaresTest.java | 115 ++++++++++++
.../descriptive/LongSumOfSquaresTest.java | 119 ++++++++++++
.../statistics/descriptive/UInt128Test.java | 35 ++++
.../statistics/descriptive/UInt192Test.java | 51 +++++
8 files changed, 757 insertions(+)
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/IntSumOfSquares.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/IntSumOfSquares.java
new file mode 100644
index 0000000..fde3728
--- /dev/null
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/IntSumOfSquares.java
@@ -0,0 +1,206 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.statistics.descriptive;
+
+import java.math.BigInteger;
+
+/**
+ * Returns the sum of the squares of the available values. Uses the following definition:
+ *
+ * <p>\[ \sum_{i=1}^n x_i^2 \]
+ *
+ * <p>where \( n \) is the number of samples.
+ *
+ * <ul>
+ * <li>The result is zero if no values are observed.
+ * </ul>
+ *
+ * <p>The implementation uses an exact integer sum to compute the sum of squared values.
+ * It supports up to 2<sup>63</sup> values. The exact sum is
+ * returned using {@link #getAsBigInteger()}. Methods that return {@code int} or
+ * {@code long} primitives will raise an exception if the result overflows.
+ *
+ * <p>Note that the implementation does not use {@code BigInteger} arithmetic; for
+ * performance the sum is computed using primitives to create an unsigned 128-bit integer.
+ *
+ * <p>This class is designed to work with (though does not require)
+ * {@linkplain java.util.stream streams}.
+ *
+ * <p><strong>This implementation is not thread safe.</strong>
+ * If multiple threads access an instance of this class concurrently,
+ * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or
+ * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally.
+ *
+ * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept}
+ * and {@link StatisticAccumulator#combine(StatisticResult) combine}
+ * as {@code accumulator} and {@code combiner} functions of
+ * {@link java.util.stream.Collector Collector} on a parallel stream,
+ * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
+ * provides the necessary partitioning, isolation, and merging of results for
+ * safe and efficient parallel execution.
+ *
+ * @since 1.1
+ */
+public final class IntSumOfSquares implements IntStatistic, StatisticAccumulator<IntSumOfSquares> {
+ /** Small array sample size.
+ * Used to avoid computing with UInt96 then converting to UInt128. */
+ private static final int SMALL_SAMPLE = 10;
+
+ /** Sum of the squared values. */
+ private final UInt128 sumSq;
+
+ /**
+ * Create an instance.
+ */
+ private IntSumOfSquares() {
+ this(UInt128.create());
+ }
+
+ /**
+ * Create an instance.
+ *
+ * @param sumSq Sum of the squared values.
+ */
+ private IntSumOfSquares(UInt128 sumSq) {
+ this.sumSq = sumSq;
+ }
+
+ /**
+ * Creates an instance.
+ *
+ * <p>The initial result is zero.
+ *
+ * @return {@code IntSumOfSquares} instance.
+ */
+ public static IntSumOfSquares create() {
+ return new IntSumOfSquares();
+ }
+
+ /**
+ * Returns an instance populated using the input {@code values}.
+ *
+ * @param values Values.
+ * @return {@code IntSumOfSquares} instance.
+ */
+ public static IntSumOfSquares of(int... values) {
+ // Small arrays can be processed using the object
+ if (values.length < SMALL_SAMPLE) {
+ final IntSumOfSquares stat = new IntSumOfSquares();
+ for (final int x : values) {
+ stat.accept(x);
+ }
+ return stat;
+ }
+
+ // Arrays can be processed using specialised counts knowing the maximum limit
+ // for an array is 2^31 values.
+ final UInt96 ss = UInt96.create();
+ // Process pairs as we know two maximum value int^2 will not overflow
+ // an unsigned long.
+ final int end = values.length & ~0x1;
+ for (int i = 0; i < end; i += 2) {
+ final long x = values[i];
+ final long y = values[i + 1];
+ ss.addPositive(x * x + y * y);
+ }
+ if (end < values.length) {
+ final long x = values[end];
+ ss.addPositive(x * x);
+ }
+
+ // Convert
+ return new IntSumOfSquares(UInt128.of(ss));
+ }
+
+ /**
+ * Updates the state of the statistic to reflect the addition of {@code value}.
+ *
+ * @param value Value.
+ */
+ @Override
+ public void accept(int value) {
+ sumSq.addPositive((long) value * value);
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Warning: This will raise an {@link ArithmeticException}
+ * if the result is not within the range {@code [0, 2^31)}.
+ *
+ * @return sum of all values.
+ * @throws ArithmeticException if the {@code result} overflows an {@code int}
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public int getAsInt() {
+ return sumSq.toIntExact();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Warning: This will raise an {@link ArithmeticException}
+ * if the result is not within the range {@code [0, 2^63)}.
+ *
+ * @return sum of all values.
+ * @throws ArithmeticException if the {@code result} overflows a {@code long}
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public long getAsLong() {
+ return sumSq.toLongExact();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Note that this conversion can lose information about the precision of the
+ * {@code BigInteger} value.
+ *
+ * @return sum of squares of all values.
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public double getAsDouble() {
+ return sumSq.toDouble();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * @return sum of squares of all values.
+ */
+ @Override
+ public BigInteger getAsBigInteger() {
+ return sumSq.toBigInteger();
+ }
+
+ @Override
+ public IntSumOfSquares combine(IntSumOfSquares other) {
+ sumSq.add(other.sumSq);
+ return this;
+ }
+}
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/LongSumOfSquares.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/LongSumOfSquares.java
new file mode 100644
index 0000000..bc3f5f8
--- /dev/null
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/LongSumOfSquares.java
@@ -0,0 +1,181 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.statistics.descriptive;
+
+import java.math.BigInteger;
+
+/**
+ * Returns the sum of the squares of the available values. Uses the following definition:
+ *
+ * <p>\[ \sum_{i=1}^n x_i^2 \]
+ *
+ * <p>where \( n \) is the number of samples.
+ *
+ * <ul>
+ * <li>The result is zero if no values are observed.
+ * </ul>
+ *
+ * <p>The implementation uses an exact integer sum to compute the sum of squared values.
+ * It supports up to 2<sup>63</sup> values. The exact sum is
+ * returned using {@link #getAsBigInteger()}. Methods that return {@code int} or
+ * {@code long} primitives will raise an exception if the result overflows.
+ *
+ * <p>Note that the implementation does not use {@code BigInteger} arithmetic; for
+ * performance the sum is computed using primitives to create an unsigned 192-bit integer.
+ *
+ * <p>This class is designed to work with (though does not require)
+ * {@linkplain java.util.stream streams}.
+ *
+ * <p><strong>This implementation is not thread safe.</strong>
+ * If multiple threads access an instance of this class concurrently,
+ * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or
+ * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally.
+ *
+ * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept}
+ * and {@link StatisticAccumulator#combine(StatisticResult) combine}
+ * as {@code accumulator} and {@code combiner} functions of
+ * {@link java.util.stream.Collector Collector} on a parallel stream,
+ * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
+ * provides the necessary partitioning, isolation, and merging of results for
+ * safe and efficient parallel execution.
+ *
+ * @since 1.1
+ */
+public final class LongSumOfSquares implements LongStatistic, StatisticAccumulator<LongSumOfSquares> {
+
+ /** Sum of the squared values. */
+ private final UInt192 sumSq;
+
+ /**
+ * Create an instance.
+ */
+ private LongSumOfSquares() {
+ this(UInt192.create());
+ }
+
+ /**
+ * Create an instance.
+ *
+ * @param sumSq Sum of the squared values.
+ */
+ private LongSumOfSquares(UInt192 sumSq) {
+ this.sumSq = sumSq;
+ }
+
+ /**
+ * Creates an instance.
+ *
+ * <p>The initial result is zero.
+ *
+ * @return {@code LongSumOfSquares} instance.
+ */
+ public static LongSumOfSquares create() {
+ return new LongSumOfSquares();
+ }
+
+ /**
+ * Returns an instance populated using the input {@code values}.
+ *
+ * @param values Values.
+ * @return {@code LongSumOfSquares} instance.
+ */
+ public static LongSumOfSquares of(long... values) {
+ final UInt192 ss = UInt192.create();
+ for (final long x : values) {
+ ss.addSquare(x);
+ }
+ return new LongSumOfSquares(ss);
+ }
+
+ /**
+ * Updates the state of the statistic to reflect the addition of {@code value}.
+ *
+ * @param value Value.
+ */
+ @Override
+ public void accept(long value) {
+ sumSq.addSquare(value);
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Warning: This will raise an {@link ArithmeticException}
+ * if the result is not within the range {@code [0, 2^31)}.
+ *
+ * @return sum of all values.
+ * @throws ArithmeticException if the {@code result} overflows an {@code int}
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public int getAsInt() {
+ return sumSq.toIntExact();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Warning: This will raise an {@link ArithmeticException}
+ * if the result is not within the range {@code [0, 2^63)}.
+ *
+ * @return sum of all values.
+ * @throws ArithmeticException if the {@code result} overflows a {@code long}
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public long getAsLong() {
+ return sumSq.toLongExact();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * <p>Note that this conversion can lose information about the precision of the
+ * {@code BigInteger} value.
+ *
+ * @return sum of squares of all values.
+ * @see #getAsBigInteger()
+ */
+ @Override
+ public double getAsDouble() {
+ return sumSq.toDouble();
+ }
+
+ /**
+ * Gets the sum of squares of all input values.
+ *
+ * <p>When no values have been added, the result is zero.
+ *
+ * @return sum of squares of all values.
+ */
+ @Override
+ public BigInteger getAsBigInteger() {
+ return sumSq.toBigInteger();
+ }
+
+ @Override
+ public LongSumOfSquares combine(LongSumOfSquares other) {
+ sumSq.add(other.sumSq);
+ return this;
+ }
+}
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt128.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt128.java
index 1d12a1e..e613982 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt128.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt128.java
@@ -200,6 +200,31 @@ final class UInt128 {
return IntMath.uint128ToDouble(hi64(), lo64());
}
+ /**
+ * Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
+ *
+ * @return the value
+ * @throws ArithmeticException if the value overflows an {@code int}.
+ * @see Math#toIntExact(long)
+ */
+ int toIntExact() {
+ return Math.toIntExact(toLongExact());
+ }
+
+ /**
+ * Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
+ *
+ * @return the value
+ * @throws ArithmeticException if the value overflows a {@code long}.
+ */
+ long toLongExact() {
+ // Test if we have more than 63-bits
+ if (ab != 0 || c < 0) {
+ throw new ArithmeticException("long integer overflow");
+ }
+ return lo64();
+ }
+
/**
* Return the lower 64-bits as a {@code long} value.
*
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt192.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt192.java
index df46f84..e2bad8b 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt192.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/UInt192.java
@@ -218,6 +218,31 @@ final class UInt192 {
return IntMath.uint128ToDouble(h, m | ((l == 0) ? 0 : 1)) * 0x1.0p64;
}
+ /**
+ * Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
+ *
+ * @return the value
+ * @throws ArithmeticException if the value overflows an {@code int}.
+ * @see Math#toIntExact(long)
+ */
+ int toIntExact() {
+ return Math.toIntExact(toLongExact());
+ }
+
+ /**
+ * Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
+ *
+ * @return the value
+ * @throws ArithmeticException if the value overflows a {@code long}.
+ */
+ long toLongExact() {
+ // Test if we have more than 63-bits
+ if ((ab | c | d) != 0 || e < 0) {
+ throw new ArithmeticException("long integer overflow");
+ }
+ return lo64();
+ }
+
/**
* Return the lower 64-bits as a {@code long} value.
*
diff --git a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/IntSumOfSquaresTest.java b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/IntSumOfSquaresTest.java
new file mode 100644
index 0000000..ca96658
--- /dev/null
+++ b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/IntSumOfSquaresTest.java
@@ -0,0 +1,115 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.statistics.descriptive;
+
+import java.math.BigInteger;
+import java.util.Arrays;
+import java.util.stream.Stream;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.statistics.distribution.DoubleTolerance;
+import org.apache.commons.statistics.distribution.DoubleTolerances;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test for {@link IntSumOfSquares}.
+ */
+final class IntSumOfSquaresTest extends BaseIntStatisticTest<IntSumOfSquares> {
+
+ @Override
+ protected ResultType getResultType() {
+ return ResultType.BIG_INTEGER;
+ }
+
+ @Override
+ protected IntSumOfSquares create() {
+ return IntSumOfSquares.create();
+ }
+
+ @Override
+ protected IntSumOfSquares create(int... values) {
+ return IntSumOfSquares.of(values);
+ }
+
+ @Override
+ protected DoubleStatistic createAsDoubleStatistic(int... values) {
+ return SumOfSquares.of(Arrays.stream(values).asDoubleStream().toArray());
+ }
+
+ @Override
+ protected DoubleTolerance getToleranceAsDouble() {
+ // Floating-point sum may be inexact.
+ // Currently the double sum matches on the standard test data.
+ // It fails on large random data added in streamTestData().
+ return DoubleTolerances.ulps(5);
+ }
+
+ @Override
+ protected StatisticResult getEmptyValue() {
+ // It does not matter that this returns a IntStatisticResult
+ // rather than a BigIntegerStatisticResult
+ return createStatisticResult(0);
+ }
+
+ @Override
+ protected StatisticResult getExpectedValue(int[] values) {
+ final BigInteger x = Arrays.stream(values)
+ .mapToObj(i -> BigInteger.valueOf((long) i * i))
+ .reduce(BigInteger.ZERO, BigInteger::add);
+ return createStatisticResult(x);
+ }
+
+ @Override
+ protected Stream<StatisticTestData> streamTestData() {
+ // A null seed will create a different RNG each time
+ final UniformRandomProvider rng = TestHelper.createRNG(null);
+ return Stream.of(
+ addCase(Integer.MAX_VALUE, 1, 2, 3, 4, Integer.MAX_VALUE),
+ addCase(Integer.MIN_VALUE, -1, -2, -3, -4, Integer.MIN_VALUE),
+ addCase(rng.ints(5).toArray()),
+ addCase(rng.ints(10).toArray()),
+ addCase(rng.ints(20).toArray()),
+ addCase(rng.ints(40).toArray())
+ );
+ }
+
+ /**
+ * Test large integer sums that overflow a {@code long}.
+ * Overflow is created by repeat addition.
+ *
+ * <p>Note: Currently no check is made for overflow in the
+ * count of observations. If this overflows then the statistic
+ * will be incorrect so the test is limited to {@code n < 2^63}.
+ */
+ @ParameterizedTest
+ @CsvSource({
+ "-1628367811, -516725738, 60",
+ "627834682, 456456670, 61",
+ "2147483647, 2147483646, 61",
+ "-2147483648, -2147483647, 61",
+ })
+ void testLongOverflow(int x, int y, int exp) {
+ final IntSumOfSquares s = IntSumOfSquares.of(x, y);
+ BigInteger sum = BigInteger.valueOf((long) x * x).add(BigInteger.valueOf((long) y * y));
+ for (int i = 0; i < exp; i++) {
+ s.combine(s);
+ sum = sum.shiftLeft(1);
+ Assertions.assertEquals(sum, s.getAsBigInteger());
+ }
+ }
+}
diff --git a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/LongSumOfSquaresTest.java b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/LongSumOfSquaresTest.java
new file mode 100644
index 0000000..8691cf9
--- /dev/null
+++ b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/LongSumOfSquaresTest.java
@@ -0,0 +1,119 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.statistics.descriptive;
+
+import java.math.BigInteger;
+import java.util.Arrays;
+import java.util.stream.Stream;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.statistics.distribution.DoubleTolerance;
+import org.apache.commons.statistics.distribution.DoubleTolerances;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test for {@link LongSumOfSquares}.
+ */
+final class LongSumOfSquaresTest extends BaseLongStatisticTest<LongSumOfSquares> {
+
+ @Override
+ protected ResultType getResultType() {
+ return ResultType.BIG_INTEGER;
+ }
+
+ @Override
+ protected LongSumOfSquares create() {
+ return LongSumOfSquares.create();
+ }
+
+ @Override
+ protected LongSumOfSquares create(long... values) {
+ return LongSumOfSquares.of(values);
+ }
+
+ @Override
+ protected DoubleStatistic createAsDoubleStatistic(long... values) {
+ return SumOfSquares.of(Arrays.stream(values).asDoubleStream().toArray());
+ }
+
+ @Override
+ protected DoubleTolerance getToleranceAsDouble() {
+ // Floating-point sum may be inexact.
+ // Currently the double sum matches exactly on the standard test data.
+ // It fails on large random data added in streamTestData().
+ return DoubleTolerances.ulps(5);
+ }
+
+ @Override
+ protected StatisticResult getEmptyValue() {
+ // It does not matter that this returns a IntStatisticResult
+ // rather than a BigIntegerStatisticResult
+ return createStatisticResult(0);
+ }
+
+ @Override
+ protected StatisticResult getExpectedValue(long[] values) {
+ final BigInteger x = Arrays.stream(values)
+ .mapToObj(i -> BigInteger.valueOf(i).pow(2))
+ .reduce(BigInteger.ZERO, BigInteger::add);
+ return createStatisticResult(x);
+ }
+
+ @Override
+ protected Stream<StatisticTestData> streamTestData() {
+ // A null seed will create a different RNG each time
+ final UniformRandomProvider rng = TestHelper.createRNG(null);
+ return Stream.of(
+ addCase(Long.MAX_VALUE, 1, 2, 3, 4, Long.MAX_VALUE),
+ addCase(Long.MIN_VALUE, -1, -2, -3, -4, Long.MIN_VALUE),
+ // 2^128 - too big for a 128-bit unsigned number
+ addCase(Long.MIN_VALUE, Long.MIN_VALUE, Long.MIN_VALUE, Long.MIN_VALUE),
+ addCase(rng.longs(5).toArray()),
+ addCase(rng.longs(10).toArray()),
+ addCase(rng.longs(20).toArray()),
+ addCase(rng.longs(40).toArray())
+ );
+ }
+
+ /**
+ * Test large integer sums that overflow a {@code long}.
+ * Overflow is created by repeat addition.
+ *
+ * <p>Note: Currently no check is made for overflow in the
+ * count of observations. If this overflows then the statistic
+ * will be incorrect so the test is limited to {@code n < 2^63}.
+ */
+ @ParameterizedTest
+ @CsvSource({
+ "-1628367672438123811, -97927322516725738, 60",
+ "3279208082627834682, 4234564566706285432, 61",
+ "9223372036854775807, 9223372036854775806, 61",
+ "-9223372036854775808, -9223372036854775807, 61",
+ })
+ void testLongOverflow(long x, long y, int exp) {
+ final LongSumOfSquares s = LongSumOfSquares.of(x, y);
+ BigInteger sum = BigInteger.valueOf(x).pow(2)
+ .add(BigInteger.valueOf(y).pow(2));
+ for (int i = 0; i < exp; i++) {
+ // Assumes the sum as a long will overflow
+ s.combine(s);
+ sum = sum.shiftLeft(1);
+ Assertions.assertEquals(sum, s.getAsBigInteger());
+ }
+ }
+}
diff --git a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt128Test.java b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt128Test.java
index 22f3d5f..1209daf 100644
--- a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt128Test.java
+++ b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt128Test.java
@@ -236,4 +236,39 @@ class UInt128Test {
builder.accept(Arguments.of(-1L, -1L, -1L, -1L));
return builder.build();
}
+
+ @Test
+ void testToIntExact() {
+ final int x = Integer.MAX_VALUE;
+ final long y = 1L << 31;
+ final UInt128 v = new UInt128(0, x);
+ Assertions.assertEquals(x, v.toIntExact());
+ v.addPositive(1);
+ Assertions.assertThrows(ArithmeticException.class, () -> v.toIntExact());
+ Assertions.assertEquals(0x1.0p31, v.toDouble());
+ Assertions.assertEquals(y, v.toLongExact());
+ // 2^32 has no low bits - check the result is not returned as zero
+ final UInt128 v2 = new UInt128(0, 2 * y);
+ Assertions.assertThrows(ArithmeticException.class, () -> v2.toIntExact());
+ Assertions.assertEquals(0x1.0p32, v2.toDouble());
+ Assertions.assertEquals(2 * y, v2.toLongExact());
+ // 2^64 has no low bits - check the result is not returned as zero
+ final UInt128 v3 = new UInt128(1, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v3.toIntExact());
+ Assertions.assertEquals(0x1.0p64, v3.toDouble());
+ }
+
+ @Test
+ void testToLongExact() {
+ final long x = Long.MAX_VALUE;
+ final UInt128 v = new UInt128(0, x);
+ Assertions.assertEquals(x, v.toLongExact());
+ v.addPositive(1);
+ Assertions.assertThrows(ArithmeticException.class, () -> v.toLongExact());
+ Assertions.assertEquals(0x1.0p63, v.toDouble());
+ // 2^64 has no low bits - check the result is not returned as zero
+ final UInt128 v3 = new UInt128(1, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v3.toLongExact());
+ Assertions.assertEquals(0x1.0p64, v3.toDouble());
+ }
}
diff --git a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt192Test.java b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt192Test.java
index 8456855..c864b45 100644
--- a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt192Test.java
+++ b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/UInt192Test.java
@@ -205,4 +205,55 @@ class UInt192Test {
builder.accept(Arguments.of(-1L, -1L, -1L, -1L, -1L));
return builder.build();
}
+
+ @Test
+ void testToIntExact() {
+ final int x = Integer.MAX_VALUE;
+ final long y = 1L << 31;
+ final UInt192 v = new UInt192(0, 0, x);
+ Assertions.assertEquals(x, v.toIntExact());
+ v.addSquare(1);
+ Assertions.assertThrows(ArithmeticException.class, () -> v.toIntExact());
+ Assertions.assertEquals(0x1.0p31, v.toDouble());
+ Assertions.assertEquals(y, v.toLongExact());
+ // 2^32 has no low bits - check the result is not returned as zero
+ final UInt192 v2 = new UInt192(0, 0, 2 * y);
+ Assertions.assertThrows(ArithmeticException.class, () -> v2.toIntExact());
+ Assertions.assertEquals(0x1.0p32, v2.toDouble());
+ Assertions.assertEquals(2 * y, v2.toLongExact());
+ // 2^64 has no low bits - check the result is not returned as zero
+ final UInt192 v3 = new UInt192(0, 1, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v3.toIntExact());
+ Assertions.assertEquals(0x1.0p64, v3.toDouble());
+ // 2^96 has no low bits - check the result is not returned as zero
+ final UInt192 v4 = new UInt192(0, 1L << 32, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v4.toIntExact());
+ Assertions.assertEquals(0x1.0p96, v4.toDouble());
+ // 2^128 has no low bits - check the result is not returned as zero
+ final UInt192 v5 = new UInt192(1, 0, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v5.toIntExact());
+ Assertions.assertEquals(0x1.0p128, v5.toDouble());
+ }
+
+ @Test
+ void testToLongExact() {
+ final long x = Long.MAX_VALUE;
+ final UInt192 v = new UInt192(0, 0, x);
+ Assertions.assertEquals(x, v.toLongExact());
+ v.addSquare(1);
+ Assertions.assertThrows(ArithmeticException.class, () -> v.toLongExact());
+ Assertions.assertEquals(0x1.0p63, v.toDouble());
+ // 2^64 has no low bits - check the result is not returned as zero
+ final UInt192 v3 = new UInt192(0, 1, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v3.toLongExact());
+ Assertions.assertEquals(0x1.0p64, v3.toDouble());
+ // 2^96 has no low bits - check the result is not returned as zero
+ final UInt192 v4 = new UInt192(0, 1L << 32, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v4.toLongExact());
+ Assertions.assertEquals(0x1.0p96, v4.toDouble());
+ // 2^128 has no low bits - check the result is not returned as zero
+ final UInt192 v5 = new UInt192(1, 0, 0);
+ Assertions.assertThrows(ArithmeticException.class, () -> v5.toLongExact());
+ Assertions.assertEquals(0x1.0p128, v5.toDouble());
+ }
}