public final class LongMath
extends java.lang.Object
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 Longs.
| Modifier and Type | Class and Description |
|---|---|
private static class |
LongMath.MillerRabinTester |
| Modifier and Type | Field and Description |
|---|---|
(package private) static int[] |
biggestBinomials |
(package private) static int[] |
biggestSimpleBinomials |
(package private) static long[] |
factorials |
(package private) static long |
FLOOR_SQRT_MAX_LONG |
(package private) static long[] |
halfPowersOf10 |
(package private) static long |
MAX_POWER_OF_SQRT2_UNSIGNED
The biggest half power of two that fits into an unsigned long
|
(package private) static long |
MAX_SIGNED_POWER_OF_TWO |
(package private) static byte[] |
maxLog10ForLeadingZeros |
private static long[][] |
millerRabinBaseSets |
(package private) static long[] |
powersOf10 |
private static int |
SIEVE_30 |
| Modifier | Constructor and Description |
|---|---|
private |
LongMath() |
| Modifier and Type | Method and Description |
|---|---|
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. |
static long |
ceilingPowerOfTwo(long x)
Returns the smallest power of two greater than or equal to
x. |
static long |
checkedAdd(long a,
long b)
Returns the sum of
a and b, provided it does not overflow. |
static long |
checkedMultiply(long a,
long b)
Returns the product of
a and b, provided it does not overflow. |
static long |
checkedPow(long b,
int k)
Returns the
b to the kth power, provided it does not overflow. |
static long |
checkedSubtract(long a,
long b)
Returns the difference of
a and b, provided it does not overflow. |
static long |
divide(long p,
long q,
java.math.RoundingMode mode)
Returns the result of dividing
p by q, rounding using the specified RoundingMode. |
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. |
(package private) static boolean |
fitsInInt(long x) |
static long |
floorPowerOfTwo(long x)
Returns the largest power of two less than or equal to
x. |
static long |
gcd(long a,
long b)
Returns the greatest common divisor of
a, b. |
static boolean |
isPowerOfTwo(long x)
Returns
true if x represents a power of two. |
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. |
(package private) static int |
lessThanBranchFree(long x,
long y)
Returns 1 if
x < y as unsigned longs, and 0 otherwise. |
static int |
log10(long x,
java.math.RoundingMode mode)
Returns the base-10 logarithm of
x, rounded according to the specified rounding mode. |
(package private) static int |
log10Floor(long x) |
static int |
log2(long x,
java.math.RoundingMode mode)
Returns the base-2 logarithm of
x, rounded according to the specified rounding mode. |
static long |
mean(long x,
long y)
Returns the arithmetic mean of
x and y, rounded toward negative infinity. |
static int |
mod(long x,
int m)
Returns
x mod m, a non-negative value less than m. |
static long |
mod(long x,
long m)
Returns
x mod m, a non-negative value less than m. |
(package private) static long |
multiplyFraction(long x,
long numerator,
long denominator)
Returns (x * numerator / denominator), which is assumed to come out to an integral value.
|
static long |
pow(long b,
int k)
Returns
b to the kth power. |
static double |
roundToDouble(long x,
java.math.RoundingMode mode)
Returns
x, rounded to a double with the specified rounding mode. |
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. |
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. |
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. |
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. |
static long |
sqrt(long x,
java.math.RoundingMode mode)
Returns the square root of
x, rounded with the specified rounding mode. |
static final long MAX_SIGNED_POWER_OF_TWO
static final long MAX_POWER_OF_SQRT2_UNSIGNED
static final byte[] maxLog10ForLeadingZeros
static final long[] powersOf10
static final long[] halfPowersOf10
static final long FLOOR_SQRT_MAX_LONG
static final long[] factorials
static final int[] biggestBinomials
static final int[] biggestSimpleBinomials
private static final int SIEVE_30
private static final long[][] millerRabinBaseSets
public static long ceilingPowerOfTwo(long x)
x. This is equivalent to
checkedPow(2, log2(x, CEILING)).java.lang.IllegalArgumentException - if x <= 0java.lang.ArithmeticException - of the next-higher power of two is not representable as a long, i.e. when x > 2^62public static long floorPowerOfTwo(long x)
x. This is equivalent to checkedPow(2, log2(x, FLOOR)).java.lang.IllegalArgumentException - if x <= 0public static boolean isPowerOfTwo(long x)
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.
static int lessThanBranchFree(long x,
long y)
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.public static int log2(long x,
java.math.RoundingMode mode)
x, rounded according to the specified rounding mode.java.lang.IllegalArgumentException - if x <= 0java.lang.ArithmeticException - if mode is RoundingMode.UNNECESSARY and x
is not a power of twopublic static int log10(long x,
java.math.RoundingMode mode)
x, rounded according to the specified rounding mode.java.lang.IllegalArgumentException - if x <= 0java.lang.ArithmeticException - if mode is RoundingMode.UNNECESSARY and x
is not a power of tenstatic int log10Floor(long x)
public static long pow(long b,
int k)
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.java.lang.IllegalArgumentException - if k < 0public static long sqrt(long x,
java.math.RoundingMode mode)
x, rounded with the specified rounding mode.java.lang.IllegalArgumentException - if x < 0java.lang.ArithmeticException - if mode is RoundingMode.UNNECESSARY and sqrt(x) is not an integerpublic static long divide(long p,
long q,
java.math.RoundingMode mode)
p by q, rounding using the specified RoundingMode.java.lang.ArithmeticException - if q == 0, or if mode == UNNECESSARY and a
is not an integer multiple of bpublic static int mod(long x,
int m)
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
java.lang.ArithmeticException - if m <= 0public static long mod(long x,
long m)
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
java.lang.ArithmeticException - if m <= 0public static long gcd(long a,
long b)
a, b. Returns 0 if a == 0 && b ==
0.java.lang.IllegalArgumentException - if a < 0 or b < 0public static long checkedAdd(long a,
long b)
a and b, provided it does not overflow.java.lang.ArithmeticException - if a + b overflows in signed long arithmeticpublic static long checkedSubtract(long a,
long b)
a and b, provided it does not overflow.java.lang.ArithmeticException - if a - b overflows in signed long arithmeticpublic static long checkedMultiply(long a,
long b)
a and b, provided it does not overflow.java.lang.ArithmeticException - if a * b overflows in signed long arithmeticpublic static long checkedPow(long b,
int k)
b to the kth power, provided it does not overflow.java.lang.ArithmeticException - if b to the kth power overflows in signed long arithmeticpublic static long saturatedAdd(long a,
long b)
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 saturatedSubtract(long a,
long b)
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)
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)
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 factorial(int n)
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.java.lang.IllegalArgumentException - if n < 0public static long binomial(int n,
int k)
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.java.lang.IllegalArgumentException - if n < 0, k < 0, or k > nstatic long multiplyFraction(long x,
long numerator,
long denominator)
static boolean fitsInInt(long x)
public static long mean(long x,
long y)
x and y, rounded toward negative infinity. This
method is resilient to overflow.public static boolean isPrime(long n)
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(int).
java.lang.IllegalArgumentException - if n is negativepublic static double roundToDouble(long x,
java.math.RoundingMode mode)
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.)
java.lang.ArithmeticException - if mode is RoundingMode.UNNECESSARY and x
is not precisely representable as a double