IntSumOfSquares.java

  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. import java.math.BigInteger;

  19. /**
  20.  * Returns the sum of the squares of the available values. Uses the following definition:
  21.  *
  22.  * <p>\[ \sum_{i=1}^n x_i^2 \]
  23.  *
  24.  * <p>where \( n \) is the number of samples.
  25.  *
  26.  * <ul>
  27.  *   <li>The result is zero if no values are observed.
  28.  * </ul>
  29.  *
  30.  * <p>The implementation uses an exact integer sum to compute the sum of squared values.
  31.  * The exact sum is returned using {@link #getAsBigInteger()}. Methods that return {@code int} or
  32.  * {@code long} primitives will raise an exception if the result overflows.
  33.  *
  34.  * <p>Note that the implementation does not use {@code BigInteger} arithmetic; for
  35.  * performance the sum is computed using primitives to create an unsigned 128-bit integer.
  36.  * Support is provided for at least 2<sup>63</sup> observations.
  37.  *
  38.  * <p>This class is designed to work with (though does not require)
  39.  * {@linkplain java.util.stream streams}.
  40.  *
  41.  * <p><strong>This implementation is not thread safe.</strong>
  42.  * If multiple threads access an instance of this class concurrently,
  43.  * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or
  44.  * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally.
  45.  *
  46.  * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept}
  47.  * and {@link StatisticAccumulator#combine(StatisticResult) combine}
  48.  * as {@code accumulator} and {@code combiner} functions of
  49.  * {@link java.util.stream.Collector Collector} on a parallel stream,
  50.  * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
  51.  * provides the necessary partitioning, isolation, and merging of results for
  52.  * safe and efficient parallel execution.
  53.  *
  54.  * @since 1.1
  55.  */
  56. public final class IntSumOfSquares implements IntStatistic, StatisticAccumulator<IntSumOfSquares> {
  57.     /** Small array sample size.
  58.      * Used to avoid computing with UInt96 then converting to UInt128. */
  59.     private static final int SMALL_SAMPLE = 10;

  60.     /** Sum of the squared values. */
  61.     private final UInt128 sumSq;

  62.     /**
  63.      * Create an instance.
  64.      */
  65.     private IntSumOfSquares() {
  66.         this(UInt128.create());
  67.     }

  68.     /**
  69.      * Create an instance.
  70.      *
  71.      * @param sumSq Sum of the squared values.
  72.      */
  73.     private IntSumOfSquares(UInt128 sumSq) {
  74.         this.sumSq = sumSq;
  75.     }

  76.     /**
  77.      * Creates an instance.
  78.      *
  79.      * <p>The initial result is zero.
  80.      *
  81.      * @return {@code IntSumOfSquares} instance.
  82.      */
  83.     public static IntSumOfSquares create() {
  84.         return new IntSumOfSquares();
  85.     }

  86.     /**
  87.      * Returns an instance populated using the input {@code values}.
  88.      *
  89.      * @param values Values.
  90.      * @return {@code IntSumOfSquares} instance.
  91.      */
  92.     public static IntSumOfSquares of(int... values) {
  93.         // Small arrays can be processed using the object
  94.         if (values.length < SMALL_SAMPLE) {
  95.             final IntSumOfSquares stat = new IntSumOfSquares();
  96.             for (final int x : values) {
  97.                 stat.accept(x);
  98.             }
  99.             return stat;
  100.         }

  101.         // Arrays can be processed using specialised counts knowing the maximum limit
  102.         // for an array is 2^31 values.
  103.         final UInt96 ss = UInt96.create();
  104.         // Process pairs as we know two maximum value int^2 will not overflow
  105.         // an unsigned long.
  106.         final int end = values.length & ~0x1;
  107.         for (int i = 0; i < end; i += 2) {
  108.             final long x = values[i];
  109.             final long y = values[i + 1];
  110.             ss.addPositive(x * x + y * y);
  111.         }
  112.         if (end < values.length) {
  113.             final long x = values[end];
  114.             ss.addPositive(x * x);
  115.         }

  116.         // Convert
  117.         return new IntSumOfSquares(UInt128.of(ss));
  118.     }

  119.     /**
  120.      * Gets the sum of squares.
  121.      *
  122.      * <p>This is package private for use in {@link IntStatistics}.
  123.      *
  124.      * @return the sum of squares
  125.      */
  126.     UInt128 getSumOfSquares() {
  127.         return sumSq;
  128.     }

  129.     /**
  130.      * Updates the state of the statistic to reflect the addition of {@code value}.
  131.      *
  132.      * @param value Value.
  133.      */
  134.     @Override
  135.     public void accept(int value) {
  136.         sumSq.addPositive((long) value * value);
  137.     }

  138.     /**
  139.      * Gets the sum of squares of all input values.
  140.      *
  141.      * <p>When no values have been added, the result is zero.
  142.      *
  143.      * <p>Warning: This will raise an {@link ArithmeticException}
  144.      * if the result is not within the range {@code [0, 2^31)}.
  145.      *
  146.      * @return sum of all values.
  147.      * @throws ArithmeticException if the {@code result} overflows an {@code int}
  148.      * @see #getAsBigInteger()
  149.      */
  150.     @Override
  151.     public int getAsInt() {
  152.         return sumSq.toIntExact();
  153.     }

  154.     /**
  155.      * Gets the sum of squares of all input values.
  156.      *
  157.      * <p>When no values have been added, the result is zero.
  158.      *
  159.      * <p>Warning: This will raise an {@link ArithmeticException}
  160.      * if the result is not within the range {@code [0, 2^63)}.
  161.      *
  162.      * @return sum of all values.
  163.      * @throws ArithmeticException if the {@code result} overflows a {@code long}
  164.      * @see #getAsBigInteger()
  165.      */
  166.     @Override
  167.     public long getAsLong() {
  168.         return sumSq.toLongExact();
  169.     }

  170.     /**
  171.      * Gets the sum of squares of all input values.
  172.      *
  173.      * <p>When no values have been added, the result is zero.
  174.      *
  175.      * <p>Note that this conversion can lose information about the precision of the
  176.      * {@code BigInteger} value.
  177.      *
  178.      * @return sum of squares of all values.
  179.      * @see #getAsBigInteger()
  180.      */
  181.     @Override
  182.     public double getAsDouble() {
  183.         return sumSq.toDouble();
  184.     }

  185.     /**
  186.      * Gets the sum of squares of all input values.
  187.      *
  188.      * <p>When no values have been added, the result is zero.
  189.      *
  190.      * @return sum of squares of all values.
  191.      */
  192.     @Override
  193.     public BigInteger getAsBigInteger() {
  194.         return sumSq.toBigInteger();
  195.     }

  196.     @Override
  197.     public IntSumOfSquares combine(IntSumOfSquares other) {
  198.         sumSq.add(other.sumSq);
  199.         return this;
  200.     }
  201. }