guava-tests/test/com/google/common/math/MathBenchmarking.java

/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed 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 com.google.common.math;

import java.math.BigInteger;
import java.util.Random;

/**
 * Utilities for benchmarks.
 *
 * In many cases, we wish to vary the order of magnitude of the input as much as we
 * want to vary the input itself, so most methods which generate values use
 * an exponential distribution varying the order of magnitude of the generated values
 * uniformly at random.
 *
 * @author Louis Wasserman
 */
final class MathBenchmarking {
  static final int ARRAY_SIZE = 0x10000;
  static final int ARRAY_MASK = 0x0ffff;
  static final Random RANDOM_SOURCE = new Random(314159265358979L);
  static final int MAX_EXPONENT = 100;

  /*
   * Duplicated from LongMath.
   * binomial(biggestBinomials[k], k) fits in a long, but not
   * binomial(biggestBinomials[k] + 1, k).
   */
  static final int[] biggestBinomials =
      {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3810779, 121977, 16175, 4337, 1733,
          887, 534, 361, 265, 206, 169, 143, 125, 111, 101, 94, 88, 83, 79, 76, 74, 72, 70, 69, 68,
          67, 67, 66, 66, 66, 66};

  /**
   * Generates values in a distribution equivalent to randomNonNegativeBigInteger
   * but omitting zero.
   */
  static BigInteger randomPositiveBigInteger(int numBits) {
    BigInteger result;
    do {
      result = randomNonNegativeBigInteger(numBits);
    } while (result.signum() == 0);
    return result;
  }

  /**
   * Generates a number in [0, 2^numBits) with an exponential distribution.
   * The floor of the log2 of the result is chosen uniformly at random in
   * [0, numBits), and then the result is chosen in that range uniformly at random.
   * Zero is treated as having log2 == 0.
   */
  static BigInteger randomNonNegativeBigInteger(int numBits) {
    int digits = RANDOM_SOURCE.nextInt(numBits);
    if (digits == 0) {
      return new BigInteger(1, RANDOM_SOURCE);
    } else {
      return new BigInteger(digits, RANDOM_SOURCE)
          .setBit(digits);
    }
  }

  /**
   * Equivalent to calling randomPositiveBigInteger(numBits) and then flipping
   * the sign with 50% probability.
   */
  static BigInteger randomNonZeroBigInteger(int numBits) {
    BigInteger result = randomPositiveBigInteger(numBits);
    return RANDOM_SOURCE.nextBoolean() ? result : result.negate();
  }

  /**
   * Chooses a number in (-2^numBits, 2^numBits) at random, with density
   * concentrated in numbers of lower magnitude.
   */
  static BigInteger randomBigInteger(int numBits) {
    while (true) {
      if (RANDOM_SOURCE.nextBoolean()) {
        return randomNonNegativeBigInteger(numBits);
      }
      BigInteger neg = randomNonNegativeBigInteger(numBits).negate();
      if (neg.signum() != 0) {
        return neg;
      }
    }
  }

  /**
   * Generates a number in [0, 2^numBits) with an exponential distribution.
   * The floor of the log2 of the absolute value of the result is chosen uniformly
   * at random in [0, numBits), and then the result is chosen from those possibilities
   * uniformly at random.
   *
   * Zero is treated as having log2 == 0.
   */
  static double randomDouble(int maxExponent) {
    double result = RANDOM_SOURCE.nextDouble();
    result = Math.scalb(result, RANDOM_SOURCE.nextInt(maxExponent + 1));
    return RANDOM_SOURCE.nextBoolean() ? result : -result;
  }

  /**
   * Returns a random integer between zero and {@code MAX_EXPONENT}.
   */
  static int randomExponent() {
    return RANDOM_SOURCE.nextInt(MAX_EXPONENT + 1);
  }

  static double randomPositiveDouble() {
    return Math.exp(randomDouble(6));
  }
}