001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.statistics.descriptive; 018 019import java.math.BigInteger; 020 021/** 022 * Returns the sum of the squares of the available values. Uses the following definition: 023 * 024 * <p>\[ \sum_{i=1}^n x_i^2 \] 025 * 026 * <p>where \( n \) is the number of samples. 027 * 028 * <ul> 029 * <li>The result is zero if no values are observed. 030 * </ul> 031 * 032 * <p>The implementation uses an exact integer sum to compute the sum of squared values. 033 * The exact sum is returned using {@link #getAsBigInteger()}. Methods that return {@code int} or 034 * {@code long} primitives will raise an exception if the result overflows. 035 * 036 * <p>Note that the implementation does not use {@code BigInteger} arithmetic; for 037 * performance the sum is computed using primitives to create an unsigned 128-bit integer. 038 * Support is provided for at least 2<sup>63</sup> observations. 039 * 040 * <p>This class is designed to work with (though does not require) 041 * {@linkplain java.util.stream streams}. 042 * 043 * <p><strong>This implementation is not thread safe.</strong> 044 * If multiple threads access an instance of this class concurrently, 045 * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or 046 * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally. 047 * 048 * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept} 049 * and {@link StatisticAccumulator#combine(StatisticResult) combine} 050 * as {@code accumulator} and {@code combiner} functions of 051 * {@link java.util.stream.Collector Collector} on a parallel stream, 052 * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()} 053 * provides the necessary partitioning, isolation, and merging of results for 054 * safe and efficient parallel execution. 055 * 056 * @since 1.1 057 */ 058public final class IntSumOfSquares implements IntStatistic, StatisticAccumulator<IntSumOfSquares> { 059 /** Small array sample size. 060 * Used to avoid computing with UInt96 then converting to UInt128. */ 061 private static final int SMALL_SAMPLE = 10; 062 063 /** Sum of the squared values. */ 064 private final UInt128 sumSq; 065 066 /** 067 * Create an instance. 068 */ 069 private IntSumOfSquares() { 070 this(UInt128.create()); 071 } 072 073 /** 074 * Create an instance. 075 * 076 * @param sumSq Sum of the squared values. 077 */ 078 private IntSumOfSquares(UInt128 sumSq) { 079 this.sumSq = sumSq; 080 } 081 082 /** 083 * Creates an instance. 084 * 085 * <p>The initial result is zero. 086 * 087 * @return {@code IntSumOfSquares} instance. 088 */ 089 public static IntSumOfSquares create() { 090 return new IntSumOfSquares(); 091 } 092 093 /** 094 * Returns an instance populated using the input {@code values}. 095 * 096 * <p>When the input is an empty array, the result is zero. 097 * 098 * @param values Values. 099 * @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}