1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.statistics.descriptive;
18
19 import java.math.BigInteger;
20
21 /**
22 * Returns the sum of the squares of the available values. Uses the following definition:
23 *
24 * <p>\[ \sum_{i=1}^n x_i^2 \]
25 *
26 * <p>where \( n \) is the number of samples.
27 *
28 * <ul>
29 * <li>The result is zero if no values are observed.
30 * </ul>
31 *
32 * <p>The implementation uses an exact integer sum to compute the sum of squared values.
33 * The exact sum is returned using {@link #getAsBigInteger()}. Methods that return {@code int} or
34 * {@code long} primitives will raise an exception if the result overflows.
35 *
36 * <p>Note that the implementation does not use {@code BigInteger} arithmetic; for
37 * performance the sum is computed using primitives to create an unsigned 128-bit integer.
38 * Support is provided for at least 2<sup>63</sup> observations.
39 *
40 * <p>This class is designed to work with (though does not require)
41 * {@linkplain java.util.stream streams}.
42 *
43 * <p><strong>This implementation is not thread safe.</strong>
44 * If multiple threads access an instance of this class concurrently,
45 * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or
46 * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally.
47 *
48 * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept}
49 * and {@link StatisticAccumulator#combine(StatisticResult) combine}
50 * as {@code accumulator} and {@code combiner} functions of
51 * {@link java.util.stream.Collector Collector} on a parallel stream,
52 * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
53 * provides the necessary partitioning, isolation, and merging of results for
54 * safe and efficient parallel execution.
55 *
56 * @since 1.1
57 */
58 public final class IntSumOfSquares implements IntStatistic, StatisticAccumulator<IntSumOfSquares> {
59 /** Small array sample size.
60 * Used to avoid computing with UInt96 then converting to UInt128. */
61 private static final int SMALL_SAMPLE = 10;
62
63 /** Sum of the squared values. */
64 private final UInt128 sumSq;
65
66 /**
67 * Create an instance.
68 */
69 private IntSumOfSquares() {
70 this(UInt128.create());
71 }
72
73 /**
74 * Create an instance.
75 *
76 * @param sumSq Sum of the squared values.
77 */
78 private IntSumOfSquares(UInt128 sumSq) {
79 this.sumSq = sumSq;
80 }
81
82 /**
83 * Creates an instance.
84 *
85 * <p>The initial result is zero.
86 *
87 * @return {@code IntSumOfSquares} instance.
88 */
89 public static IntSumOfSquares create() {
90 return new IntSumOfSquares();
91 }
92
93 /**
94 * Returns an instance populated using the input {@code values}.
95 *
96 * <p>When the input is an empty array, the result is zero.
97 *
98 * @param values Values.
99 * @return {@code IntSumOfSquares} instance.
100 */
101 public static IntSumOfSquares of(int... values) {
102 return createFromRange(values, 0, values.length);
103 }
104
105 /**
106 * Returns an instance populated using the specified range of {@code values}.
107 *
108 * <p>When the range is empty, the result is zero.
109 *
110 * @param values Values.
111 * @param from Inclusive start of the range.
112 * @param to Exclusive end of the range.
113 * @return {@code IntSumOfSquares} instance.
114 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
115 * @since 1.2
116 */
117 public static IntSumOfSquares ofRange(int[] values, int from, int to) {
118 Statistics.checkFromToIndex(from, to, values.length);
119 return createFromRange(values, from, to);
120 }
121
122 /**
123 * Create an instance using the specified range of {@code values}.
124 *
125 * <p>Warning: No range checks are performed.
126 *
127 * @param values Values.
128 * @param from Inclusive start of the range.
129 * @param to Exclusive end of the range.
130 * @return {@code IntSumOfSquares} instance.
131 */
132 static IntSumOfSquares createFromRange(int[] values, int from, int to) {
133 // Small arrays can be processed using the object
134 final int length = to - from;
135 if (length < SMALL_SAMPLE) {
136 final IntSumOfSquares stat = new IntSumOfSquares();
137 for (int i = from; i < to; i++) {
138 stat.accept(values[i]);
139 }
140 return stat;
141 }
142
143 // Arrays can be processed using specialised counts knowing the maximum limit
144 // for an array is 2^31 values.
145 final UInt96 ss = UInt96.create();
146 // Process pairs as we know two maximum value int^2 will not overflow
147 // an unsigned long.
148 final int end = from + (length & ~0x1);
149 for (int i = from; i < end; i += 2) {
150 final long x = values[i];
151 final long y = values[i + 1];
152 ss.addPositive(x * x + y * y);
153 }
154 if (end < to) {
155 final long x = values[end];
156 ss.addPositive(x * x);
157 }
158
159 // Convert
160 return new IntSumOfSquares(UInt128.of(ss));
161 }
162
163 /**
164 * Gets the sum of squares.
165 *
166 * <p>This is package private for use in {@link IntStatistics}.
167 *
168 * @return the sum of squares
169 */
170 UInt128 getSumOfSquares() {
171 return sumSq;
172 }
173
174 /**
175 * Updates the state of the statistic to reflect the addition of {@code value}.
176 *
177 * @param value Value.
178 */
179 @Override
180 public void accept(int value) {
181 sumSq.addPositive((long) value * value);
182 }
183
184 /**
185 * Gets the sum of squares of all input values.
186 *
187 * <p>When no values have been added, the result is zero.
188 *
189 * <p>Warning: This will raise an {@link ArithmeticException}
190 * if the result is not within the range {@code [0, 2^31)}.
191 *
192 * @return sum of all values.
193 * @throws ArithmeticException if the {@code result} overflows an {@code int}
194 * @see #getAsBigInteger()
195 */
196 @Override
197 public int getAsInt() {
198 return sumSq.toIntExact();
199 }
200
201 /**
202 * Gets the sum of squares of all input values.
203 *
204 * <p>When no values have been added, the result is zero.
205 *
206 * <p>Warning: This will raise an {@link ArithmeticException}
207 * if the result is not within the range {@code [0, 2^63)}.
208 *
209 * @return sum of all values.
210 * @throws ArithmeticException if the {@code result} overflows a {@code long}
211 * @see #getAsBigInteger()
212 */
213 @Override
214 public long getAsLong() {
215 return sumSq.toLongExact();
216 }
217
218 /**
219 * Gets the sum of squares of all input values.
220 *
221 * <p>When no values have been added, the result is zero.
222 *
223 * <p>Note that this conversion can lose information about the precision of the
224 * {@code BigInteger} value.
225 *
226 * @return sum of squares of all values.
227 * @see #getAsBigInteger()
228 */
229 @Override
230 public double getAsDouble() {
231 return sumSq.toDouble();
232 }
233
234 /**
235 * Gets the sum of squares of all input values.
236 *
237 * <p>When no values have been added, the result is zero.
238 *
239 * @return sum of squares of all values.
240 */
241 @Override
242 public BigInteger getAsBigInteger() {
243 return sumSq.toBigInteger();
244 }
245
246 @Override
247 public IntSumOfSquares combine(IntSumOfSquares other) {
248 sumSq.add(other.sumSq);
249 return this;
250 }
251 }