Top Description Inners Fields Constructors Methods
com.google.common.math

public final Class LongMath

extends Object
Class Inheritance
Annotations
@GwtCompatible
emulated:true
@ElementTypesAreNonnullByDefault
Static Imports
com.google.common.base.Preconditions.checkArgument, .Preconditions.checkNotNull, com.google.common.math.MathPreconditions.checkNoOverflow, .MathPreconditions.checkNonNegative, .MathPreconditions.checkPositive, .MathPreconditions.checkRoundingUnnecessary, java.lang.Math.abs, .Math.min, java.math.RoundingMode.HALF_EVEN, .RoundingMode.HALF_UP

A class for arithmetic on values of type long. Where possible, methods are defined and named analogously to their BigInteger counterparts.

The implementations of many methods in this class are based on material from Henry S. Warren, Jr.'s Hacker's Delight, (Addison Wesley, 2002).

Similar functionality for int and for BigInteger can be found in IntMath and BigIntegerMath respectively. For other common operations on long values, see com.google.common.primitives.Longs.

Author
Louis Wasserman
Since
11.0

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static enum

Field Summary

Modifier and TypeField and Description
pack-priv static final int[]
pack-priv static final int[]
pack-priv static final long[]
pack-priv static final long
pack-priv static final long[]
pack-priv static final long
MAX_POWER_OF_SQRT2_UNSIGNED

The biggest half power of two that fits into an unsigned long

pack-priv static final long
pack-priv static final byte[]
private static final long[][]
pack-priv static final long[]
private static final int

Constructor Summary

AccessConstructor and Description
private

Method Summary

Modifier and TypeMethod and Description
public static long
binomial(int n, int k)

Returns n choose k, also known as the binomial coefficient of n and k, or Long#MAX_VALUE if the result does not fit in a long.

public static long
ceilingPowerOfTwo(long x)

Returns the smallest power of two greater than or equal to x.

public static long
checkedAdd(long a, long b)

Returns the sum of a and b, provided it does not overflow.

public static long
checkedMultiply(long a, long b)

Returns the product of a and b, provided it does not overflow.

public static long
checkedPow(long b, int k)

Returns the b to the kth power, provided it does not overflow.

public static long
checkedSubtract(long a, long b)

Returns the difference of a and b, provided it does not overflow.

public static long
divide(long p, long q, RoundingMode mode)

Returns the result of dividing p by q, rounding using the specified RoundingMode.

public static long
factorial(int n)

Returns n!

pack-priv static boolean
fitsInInt(long x)

public static long
floorPowerOfTwo(long x)

Returns the largest power of two less than or equal to x.

public static long
gcd(long a, long b)

Returns the greatest common divisor of a, b.

public static boolean
isPowerOfTwo(long x)

Returns true if x represents a power of two.

public static boolean
isPrime(long n)

Returns true if n is a prime number: an integer greater than one that cannot be factored into a product of smaller positive integers.

pack-priv static int
lessThanBranchFree(long x, long y)

Returns 1 if x < y as unsigned longs, and 0 otherwise.

public static int
log10(long x, RoundingMode mode)

Returns the base-10 logarithm of x, rounded according to the specified rounding mode.

pack-priv static int
log10Floor(long x)

public static int
log2(long x, RoundingMode mode)

Returns the base-2 logarithm of x, rounded according to the specified rounding mode.

public static long
mean(long x, long y)

Returns the arithmetic mean of x and y, rounded toward negative infinity.

public static int
mod(long x, int m)

Returns x mod m, a non-negative value less than m.

public static long
mod(long x, long m)

Returns x mod m, a non-negative value less than m.

pack-priv static long
multiplyFraction(long x, long numerator, long denominator)

Returns (x * numerator / denominator), which is assumed to come out to an integral value.

public static long
pow(long b, int k)

Returns b to the kth power.

public static double
roundToDouble(long x, RoundingMode mode)

Returns x, rounded to a double with the specified rounding mode.

public static long
saturatedAdd(long a, long b)

Returns the sum of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

public static long
saturatedMultiply(long a, long b)

Returns the product of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

public static long
saturatedPow(long b, int k)

Returns the b to the kth power, unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

public static long
saturatedSubtract(long a, long b)

Returns the difference of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

public static long
sqrt(long x, RoundingMode mode)

Returns the square root of x, rounded with the specified rounding mode.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

biggestBinomialsback to summary
pack-priv static final int[] biggestBinomials
biggestSimpleBinomialsback to summary
pack-priv static final int[] biggestSimpleBinomials
Annotations
@VisibleForTesting
factorialsback to summary
pack-priv static final long[] factorials
FLOOR_SQRT_MAX_LONGback to summary
pack-priv static final long FLOOR_SQRT_MAX_LONG
Annotations
@VisibleForTesting
halfPowersOf10back to summary
pack-priv static final long[] halfPowersOf10
Annotations
@J2ktIncompatible
@GwtIncompatible
@VisibleForTesting
MAX_POWER_OF_SQRT2_UNSIGNEDback to summary
pack-priv static final long MAX_POWER_OF_SQRT2_UNSIGNED

The biggest half power of two that fits into an unsigned long

Annotations
@VisibleForTesting
MAX_SIGNED_POWER_OF_TWOback to summary
pack-priv static final long MAX_SIGNED_POWER_OF_TWO
Annotations
@VisibleForTesting
maxLog10ForLeadingZerosback to summary
pack-priv static final byte[] maxLog10ForLeadingZeros
Annotations
@VisibleForTesting
millerRabinBaseSetsback to summary
private static final long[][] millerRabinBaseSets
powersOf10back to summary
pack-priv static final long[] powersOf10
Annotations
@J2ktIncompatible
@GwtIncompatible
@VisibleForTesting
SIEVE_30back to summary
private static final int SIEVE_30

Constructor Detail

LongMathback to summary
private LongMath()

Method Detail

binomialback to summary
public static long binomial(int n, int k)

Returns n choose k, also known as the binomial coefficient of n and k, or Long#MAX_VALUE if the result does not fit in a long.

Exceptions
IllegalArgumentException:
if n < 0, k < 0, or k > n
ceilingPowerOfTwoback to summary
public static long ceilingPowerOfTwo(long x)

Returns the smallest power of two greater than or equal to x. This is equivalent to checkedPow(2, log2(x, CEILING)).

Exceptions
IllegalArgumentException:
if x <= 0
ArithmeticException:
of the next-higher power of two is not representable as a long, i.e. when x > 2^62
Since
20.0
checkedAddback to summary
public static long checkedAdd(long a, long b)

Returns the sum of a and b, provided it does not overflow.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Exceptions
ArithmeticException:
if a + b overflows in signed long arithmetic
checkedMultiplyback to summary
public static long checkedMultiply(long a, long b)

Returns the product of a and b, provided it does not overflow.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Exceptions
ArithmeticException:
if a * b overflows in signed long arithmetic
checkedPowback to summary
public static long checkedPow(long b, int k)

Returns the b to the kth power, provided it does not overflow.

Annotations
@J2ktIncompatible
@GwtIncompatible
@SuppressWarnings:ShortCircuitBoolean
Exceptions
ArithmeticException:
if b to the kth power overflows in signed long arithmetic
checkedSubtractback to summary
public static long checkedSubtract(long a, long b)

Returns the difference of a and b, provided it does not overflow.

Annotations
@J2ktIncompatible
@GwtIncompatible
@SuppressWarnings:ShortCircuitBoolean
Exceptions
ArithmeticException:
if a - b overflows in signed long arithmetic
divideback to summary
public static long divide(long p, long q, RoundingMode mode)

Returns the result of dividing p by q, rounding using the specified RoundingMode.

Annotations
@J2ktIncompatible
@GwtIncompatible
@SuppressWarnings:fallthrough
Exceptions
ArithmeticException:
if q == 0, or if mode == UNNECESSARY and a is not an integer multiple of b
factorialback to summary
public static long factorial(int n)

Returns n!, that is, the product of the first n positive integers, 1 if n == 0, or Long#MAX_VALUE if the result does not fit in a long.

Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
IllegalArgumentException:
if n < 0
fitsInIntback to summary
pack-priv static boolean fitsInInt(long x)
floorPowerOfTwoback to summary
public static long floorPowerOfTwo(long x)

Returns the largest power of two less than or equal to x. This is equivalent to checkedPow(2, log2(x, FLOOR)).

Exceptions
IllegalArgumentException:
if x <= 0
Since
20.0
gcdback to summary
public static long gcd(long a, long b)

Returns the greatest common divisor of a, b. Returns 0 if a == 0 && b == 0.

Exceptions
IllegalArgumentException:
if a < 0 or b < 0
isPowerOfTwoback to summary
public static boolean isPowerOfTwo(long x)

Returns true if x represents a power of two.

This differs from Long.bitCount(x) == 1, because Long.bitCount(Long.MIN_VALUE) == 1, but Long#MIN_VALUE is not a power of two.

Annotations
@SuppressWarnings:ShortCircuitBoolean
isPrimeback to summary
public static boolean isPrime(long n)

Returns true if n is a prime number: an integer greater than one that cannot be factored into a product of smaller positive integers. Returns false if n is zero, one, or a composite number (one which can be factored into smaller positive integers).

To test larger numbers, use BigInteger#isProbablePrime.

Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
IllegalArgumentException:
if n is negative
Since
20.0
lessThanBranchFreeback to summary
pack-priv static int lessThanBranchFree(long x, long y)

Returns 1 if x < y as unsigned longs, and 0 otherwise. Assumes that x - y fits into a signed long. The implementation is branch-free, and benchmarks suggest it is measurably faster than the straightforward ternary expression.

Annotations
@VisibleForTesting
log10back to summary
public static int log10(long x, RoundingMode mode)

Returns the base-10 logarithm of x, rounded according to the specified rounding mode.

Annotations
@J2ktIncompatible
@GwtIncompatible
@SuppressWarnings:fallthrough
Exceptions
IllegalArgumentException:
if x <= 0
ArithmeticException:
if mode is RoundingMode#UNNECESSARY and x is not a power of ten
log10Floorback to summary
pack-priv static int log10Floor(long x)
Annotations
@J2ktIncompatible
@GwtIncompatible
log2back to summary
public static int log2(long x, RoundingMode mode)

Returns the base-2 logarithm of x, rounded according to the specified rounding mode.

Annotations
@SuppressWarnings:fallthrough
Exceptions
IllegalArgumentException:
if x <= 0
ArithmeticException:
if mode is RoundingMode#UNNECESSARY and x is not a power of two
meanback to summary
public static long mean(long x, long y)

Returns the arithmetic mean of x and y, rounded toward negative infinity. This method is resilient to overflow.

Since
14.0
modback to summary
public static int mod(long x, int m)

Returns x mod m, a non-negative value less than m. This differs from x % m, which might be negative.

For example:

mod(7, 4) == 3
mod(-7, 4) == 1
mod(-1, 4) == 3
mod(-8, 4) == 0
mod(8, 4) == 0
Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
ArithmeticException:
if m <= 0
See Also
Remainder Operator
modback to summary
public static long mod(long x, long m)

Returns x mod m, a non-negative value less than m. This differs from x % m, which might be negative.

For example:

mod(7, 4) == 3
mod(-7, 4) == 1
mod(-1, 4) == 3
mod(-8, 4) == 0
mod(8, 4) == 0
Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
ArithmeticException:
if m <= 0
See Also
Remainder Operator
multiplyFractionback to summary
pack-priv static long multiplyFraction(long x, long numerator, long denominator)

Returns (x * numerator / denominator), which is assumed to come out to an integral value.

powback to summary
public static long pow(long b, int k)

Returns b to the kth power. Even if the result overflows, it will be equal to BigInteger.valueOf(b).pow(k).longValue(). This implementation runs in O(log k) time.

Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
IllegalArgumentException:
if k < 0
roundToDoubleback to summary
public static double roundToDouble(long x, RoundingMode mode)

Returns x, rounded to a double with the specified rounding mode. If x is precisely representable as a double, its double value will be returned; otherwise, the rounding will choose between the two nearest representable values with mode.

For the case of RoundingMode#HALF_EVEN, this implementation uses the IEEE 754 default rounding mode: if the two nearest representable values are equally near, the one with the least significant bit zero is chosen. (In such cases, both of the nearest representable values are even integers; this method returns the one that is a multiple of a greater power of two.)

Annotations
@SuppressWarnings:deprecation
@J2ktIncompatible
@GwtIncompatible
Exceptions
ArithmeticException:
if mode is RoundingMode#UNNECESSARY and x is not precisely representable as a double
Since
30.0
saturatedAddback to summary
public static long saturatedAdd(long a, long b)

Returns the sum of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Since
20.0
saturatedMultiplyback to summary
public static long saturatedMultiply(long a, long b)

Returns the product of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Since
20.0
saturatedPowback to summary
public static long saturatedPow(long b, int k)

Returns the b to the kth power, unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Since
20.0
saturatedSubtractback to summary
public static long saturatedSubtract(long a, long b)

Returns the difference of a and b unless it would overflow or underflow in which case Long.MAX_VALUE or Long.MIN_VALUE is returned, respectively.

Annotations
@SuppressWarnings:ShortCircuitBoolean
Since
20.0
sqrtback to summary
public static long sqrt(long x, RoundingMode mode)

Returns the square root of x, rounded with the specified rounding mode.

Annotations
@J2ktIncompatible
@GwtIncompatible
Exceptions
IllegalArgumentException:
if x < 0
ArithmeticException:
if mode is RoundingMode#UNNECESSARY and sqrt(x) is not an integer
com.google.common.math back to summary

private sealed Enum LongMath.MillerRabinTester

extends Enum<LongMath.MillerRabinTester>
Class Inheritance

Field Summary

Modifier and TypeField and Description
public static final LongMath.MillerRabinTester
LARGE

Works for all nonnegative signed longs.

public static final LongMath.MillerRabinTester
SMALL

Works for inputs ≤ FLOOR_SQRT_MAX_LONG.

Constructor Summary

AccessConstructor and Description
private

Method Summary

Modifier and TypeMethod and Description
pack-priv abstract long
mulMod(long a, long b, long m)

Returns a * b mod m.

private long
powMod(long a, long p, long m)

Returns a^p mod m.

pack-priv abstract long
squareMod(long a, long m)

Returns a^2 mod m.

pack-priv static boolean
test(long base, long n)

private boolean
testWitness(long base, long n)

Returns true if n is a strong probable prime relative to the specified base.

public static LongMath.MillerRabinTester
public static LongMath.MillerRabinTester[]
Inherited from java.lang.Enum:
clonecompareTodescribeConstableequalsfinalizegetDeclaringClasshashCodenameordinaltoStringvalueOf

Field Detail

LARGEback to summary
public static final LongMath.MillerRabinTester LARGE

Works for all nonnegative signed longs.

SMALLback to summary
public static final LongMath.MillerRabinTester SMALL

Works for inputs ≤ FLOOR_SQRT_MAX_LONG.

Constructor Detail

MillerRabinTesterback to summary
private MillerRabinTester()

Method Detail

mulModback to summary
pack-priv abstract long mulMod(long a, long b, long m)

Returns a * b mod m.

powModback to summary
private long powMod(long a, long p, long m)

Returns a^p mod m.

squareModback to summary
pack-priv abstract long squareMod(long a, long m)

Returns a^2 mod m.

testback to summary
pack-priv static boolean test(long base, long n)
testWitnessback to summary
private boolean testWitness(long base, long n)

Returns true if n is a strong probable prime relative to the specified base.

valueOfback to summary
public static LongMath.MillerRabinTester valueOf(String name)
valuesback to summary
public static LongMath.MillerRabinTester[] values()