1 /*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.math;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.math.MathPreconditions.checkNoOverflow;
20 import static com.google.common.math.MathPreconditions.checkNonNegative;
21 import static com.google.common.math.MathPreconditions.checkPositive;
22 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
23 import static java.lang.Math.abs;
24 import static java.lang.Math.min;
25 import static java.math.RoundingMode.HALF_EVEN;
26 import static java.math.RoundingMode.HALF_UP;
27
28 import com.google.common.annotations.Beta;
29 import com.google.common.annotations.GwtCompatible;
30 import com.google.common.annotations.GwtIncompatible;
31 import com.google.common.annotations.VisibleForTesting;
32 import com.google.common.primitives.Longs;
33 import com.google.common.primitives.UnsignedLongs;
34 import java.math.BigInteger;
35 import java.math.RoundingMode;
36
37 /**
38 * A class for arithmetic on values of type {@code long}. Where possible, methods are defined and
39 * named analogously to their {@code BigInteger} counterparts.
40 *
41 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
42 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
43 *
44 * <p>Similar functionality for {@code int} and for {@link BigInteger} can be found in {@link
45 * IntMath} and {@link BigIntegerMath} respectively. For other common operations on {@code long}
46 * values, see {@link com.google.common.primitives.Longs}.
47 *
48 * @author Louis Wasserman
49 * @since 11.0
50 */
51 @GwtCompatible(emulated = true)
52 @ElementTypesAreNonnullByDefault
53 public final class LongMath {
54 // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
55
56 @VisibleForTesting static final long MAX_SIGNED_POWER_OF_TWO = 1L << (Long.SIZE - 2);
57
58 /**
59 * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to
60 * {@code checkedPow(2, log2(x, CEILING))}.
61 *
62 * @throws IllegalArgumentException if {@code x <= 0}
63 * @throws ArithmeticException of the next-higher power of two is not representable as a {@code
64 * long}, i.e. when {@code x > 2^62}
65 * @since 20.0
66 */
67 @Beta
68 public static long ceilingPowerOfTwo(long x) {
69 checkPositive("x", x);
70 if (x > MAX_SIGNED_POWER_OF_TWO) {
71 throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") is not representable as a long");
72 }
73 return 1L << -Long.numberOfLeadingZeros(x - 1);
74 }
75
76 /**
77 * Returns the largest power of two less than or equal to {@code x}. This is equivalent to {@code
78 * checkedPow(2, log2(x, FLOOR))}.
79 *
80 * @throws IllegalArgumentException if {@code x <= 0}
81 * @since 20.0
82 */
83 @Beta
84 public static long floorPowerOfTwo(long x) {
85 checkPositive("x", x);
86
87 // Long.highestOneBit was buggy on GWT. We've fixed it, but I'm not certain when the fix will
88 // be released.
89 return 1L << ((Long.SIZE - 1) - Long.numberOfLeadingZeros(x));
90 }
91
92 /**
93 * Returns {@code true} if {@code x} represents a power of two.
94 *
95 * <p>This differs from {@code Long.bitCount(x) == 1}, because {@code
96 * Long.bitCount(Long.MIN_VALUE) == 1}, but {@link Long#MIN_VALUE} is not a power of two.
97 */
98 public static boolean isPowerOfTwo(long x) {
99 return x > 0 & (x & (x - 1)) == 0;
100 }
101
102 /**
103 * Returns 1 if {@code x < y} as unsigned longs, and 0 otherwise. Assumes that x - y fits into a
104 * signed long. The implementation is branch-free, and benchmarks suggest it is measurably faster
105 * than the straightforward ternary expression.
106 */
107 @VisibleForTesting
108 static int lessThanBranchFree(long x, long y) {
109 // Returns the sign bit of x - y.
110 return (int) (~~(x - y) >>> (Long.SIZE - 1));
111 }
112
113 /**
114 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
115 *
116 * @throws IllegalArgumentException if {@code x <= 0}
117 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
118 * is not a power of two
119 */
120 @SuppressWarnings("fallthrough")
121 // TODO(kevinb): remove after this warning is disabled globally
122 public static int log2(long x, RoundingMode mode) {
123 checkPositive("x", x);
124 switch (mode) {
125 case UNNECESSARY:
126 checkRoundingUnnecessary(isPowerOfTwo(x));
127 // fall through
128 case DOWN:
129 case FLOOR:
130 return (Long.SIZE - 1) - Long.numberOfLeadingZeros(x);
131
132 case UP:
133 case CEILING:
134 return Long.SIZE - Long.numberOfLeadingZeros(x - 1);
135
136 case HALF_DOWN:
137 case HALF_UP:
138 case HALF_EVEN:
139 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
140 int leadingZeros = Long.numberOfLeadingZeros(x);
141 long cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
142 // floor(2^(logFloor + 0.5))
143 int logFloor = (Long.SIZE - 1) - leadingZeros;
144 return logFloor + lessThanBranchFree(cmp, x);
145
146 default:
147 throw new AssertionError("impossible");
148 }
149 }
150
151 /** The biggest half power of two that fits into an unsigned long */
152 @VisibleForTesting static final long MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333F9DE6484L;
153
154 /**
155 * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
156 *
157 * @throws IllegalArgumentException if {@code x <= 0}
158 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
159 * is not a power of ten
160 */
161 @GwtIncompatible // TODO
162 @SuppressWarnings("fallthrough")
163 // TODO(kevinb): remove after this warning is disabled globally
164 public static int log10(long x, RoundingMode mode) {
165 checkPositive("x", x);
166 int logFloor = log10Floor(x);
167 long floorPow = powersOf10[logFloor];
168 switch (mode) {
169 case UNNECESSARY:
170 checkRoundingUnnecessary(x == floorPow);
171 // fall through
172 case FLOOR:
173 case DOWN:
174 return logFloor;
175 case CEILING:
176 case UP:
177 return logFloor + lessThanBranchFree(floorPow, x);
178 case HALF_DOWN:
179 case HALF_UP:
180 case HALF_EVEN:
181 // sqrt(10) is irrational, so log10(x)-logFloor is never exactly 0.5
182 return logFloor + lessThanBranchFree(halfPowersOf10[logFloor], x);
183 default:
184 throw new AssertionError();
185 }
186 }
187
188 @GwtIncompatible // TODO
189 static int log10Floor(long x) {
190 /*
191 * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation.
192 *
193 * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))), we
194 * can narrow the possible floor(log10(x)) values to two. For example, if floor(log2(x)) is 6,
195 * then 64 <= x < 128, so floor(log10(x)) is either 1 or 2.
196 */
197 int y = maxLog10ForLeadingZeros[Long.numberOfLeadingZeros(x)];
198 /*
199 * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the
200 * lower of the two possible values, or y - 1, otherwise, we want y.
201 */
202 return y - lessThanBranchFree(x, powersOf10[y]);
203 }
204
205 // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i)))
206 @VisibleForTesting
207 static final byte[] maxLog10ForLeadingZeros = {
208 19, 18, 18, 18, 18, 17, 17, 17, 16, 16, 16, 15, 15, 15, 15, 14, 14, 14, 13, 13, 13, 12, 12, 12,
209 12, 11, 11, 11, 10, 10, 10, 9, 9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3,
210 3, 2, 2, 2, 1, 1, 1, 0, 0, 0
211 };
212
213 @GwtIncompatible // TODO
214 @VisibleForTesting
215 static final long[] powersOf10 = {
216 1L,
217 10L,
218 100L,
219 1000L,
220 10000L,
221 100000L,
222 1000000L,
223 10000000L,
224 100000000L,
225 1000000000L,
226 10000000000L,
227 100000000000L,
228 1000000000000L,
229 10000000000000L,
230 100000000000000L,
231 1000000000000000L,
232 10000000000000000L,
233 100000000000000000L,
234 1000000000000000000L
235 };
236
237 // halfPowersOf10[i] = largest long less than 10^(i + 0.5)
238 @GwtIncompatible // TODO
239 @VisibleForTesting
240 static final long[] halfPowersOf10 = {
241 3L,
242 31L,
243 316L,
244 3162L,
245 31622L,
246 316227L,
247 3162277L,
248 31622776L,
249 316227766L,
250 3162277660L,
251 31622776601L,
252 316227766016L,
253 3162277660168L,
254 31622776601683L,
255 316227766016837L,
256 3162277660168379L,
257 31622776601683793L,
258 316227766016837933L,
259 3162277660168379331L
260 };
261
262 /**
263 * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
264 * {@code BigInteger.valueOf(b).pow(k).longValue()}. This implementation runs in {@code O(log k)}
265 * time.
266 *
267 * @throws IllegalArgumentException if {@code k < 0}
268 */
269 @GwtIncompatible // TODO
270 public static long pow(long b, int k) {
271 checkNonNegative("exponent", k);
272 if (-2 <= b && b <= 2) {
273 switch ((int) b) {
274 case 0:
275 return (k == 0) ? 1 : 0;
276 case 1:
277 return 1;
278 case (-1):
279 return ((k & 1) == 0) ? 1 : -1;
280 case 2:
281 return (k < Long.SIZE) ? 1L << k : 0;
282 case (-2):
283 if (k < Long.SIZE) {
284 return ((k & 1) == 0) ? 1L << k : -(1L << k);
285 } else {
286 return 0;
287 }
288 default:
289 throw new AssertionError();
290 }
291 }
292 for (long accum = 1; ; k >>= 1) {
293 switch (k) {
294 case 0:
295 return accum;
296 case 1:
297 return accum * b;
298 default:
299 accum *= ((k & 1) == 0) ? 1 : b;
300 b *= b;
301 }
302 }
303 }
304
305 /**
306 * Returns the square root of {@code x}, rounded with the specified rounding mode.
307 *
308 * @throws IllegalArgumentException if {@code x < 0}
309 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code
310 * sqrt(x)} is not an integer
311 */
312 @GwtIncompatible // TODO
313 @SuppressWarnings("fallthrough")
314 public static long sqrt(long x, RoundingMode mode) {
315 checkNonNegative("x", x);
316 if (fitsInInt(x)) {
317 return IntMath.sqrt((int) x, mode);
318 }
319 /*
320 * Let k be the true value of floor(sqrt(x)), so that
321 *
322 * k * k <= x < (k + 1) * (k + 1)
323 * (double) (k * k) <= (double) x <= (double) ((k + 1) * (k + 1))
324 * since casting to double is nondecreasing.
325 * Note that the right-hand inequality is no longer strict.
326 * Math.sqrt(k * k) <= Math.sqrt(x) <= Math.sqrt((k + 1) * (k + 1))
327 * since Math.sqrt is monotonic.
328 * (long) Math.sqrt(k * k) <= (long) Math.sqrt(x) <= (long) Math.sqrt((k + 1) * (k + 1))
329 * since casting to long is monotonic
330 * k <= (long) Math.sqrt(x) <= k + 1
331 * since (long) Math.sqrt(k * k) == k, as checked exhaustively in
332 * {@link LongMathTest#testSqrtOfPerfectSquareAsDoubleIsPerfect}
333 */
334 long guess = (long) Math.sqrt(x);
335 // Note: guess is always <= FLOOR_SQRT_MAX_LONG.
336 long guessSquared = guess * guess;
337 // Note (2013-2-26): benchmarks indicate that, inscrutably enough, using if statements is
338 // faster here than using lessThanBranchFree.
339 switch (mode) {
340 case UNNECESSARY:
341 checkRoundingUnnecessary(guessSquared == x);
342 return guess;
343 case FLOOR:
344 case DOWN:
345 if (x < guessSquared) {
346 return guess - 1;
347 }
348 return guess;
349 case CEILING:
350 case UP:
351 if (x > guessSquared) {
352 return guess + 1;
353 }
354 return guess;
355 case HALF_DOWN:
356 case HALF_UP:
357 case HALF_EVEN:
358 long sqrtFloor = guess - ((x < guessSquared) ? 1 : 0);
359 long halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
360 /*
361 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x
362 * and halfSquare are integers, this is equivalent to testing whether or not x <=
363 * halfSquare. (We have to deal with overflow, though.)
364 *
365 * If we treat halfSquare as an unsigned long, we know that
366 * sqrtFloor^2 <= x < (sqrtFloor + 1)^2
367 * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1
368 * so |x - halfSquare| <= sqrtFloor. Therefore, it's safe to treat x - halfSquare as a
369 * signed long, so lessThanBranchFree is safe for use.
370 */
371 return sqrtFloor + lessThanBranchFree(halfSquare, x);
372 default:
373 throw new AssertionError();
374 }
375 }
376
377 /**
378 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code
379 * RoundingMode}.
380 *
381 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
382 * is not an integer multiple of {@code b}
383 */
384 @GwtIncompatible // TODO
385 @SuppressWarnings("fallthrough")
386 public static long divide(long p, long q, RoundingMode mode) {
387 checkNotNull(mode);
388 long div = p / q; // throws if q == 0
389 long rem = p - q * div; // equals p % q
390
391 if (rem == 0) {
392 return div;
393 }
394
395 /*
396 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
397 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
398 * p / q.
399 *
400 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
401 */
402 int signum = 1 | (int) ((p ^ q) >> (Long.SIZE - 1));
403 boolean increment;
404 switch (mode) {
405 case UNNECESSARY:
406 checkRoundingUnnecessary(rem == 0);
407 // fall through
408 case DOWN:
409 increment = false;
410 break;
411 case UP:
412 increment = true;
413 break;
414 case CEILING:
415 increment = signum > 0;
416 break;
417 case FLOOR:
418 increment = signum < 0;
419 break;
420 case HALF_EVEN:
421 case HALF_DOWN:
422 case HALF_UP:
423 long absRem = abs(rem);
424 long cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
425 // subtracting two nonnegative longs can't overflow
426 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
427 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
428 increment = (mode == HALF_UP | (mode == HALF_EVEN & (div & 1) != 0));
429 } else {
430 increment = cmpRemToHalfDivisor > 0; // closer to the UP value
431 }
432 break;
433 default:
434 throw new AssertionError();
435 }
436 return increment ? div + signum : div;
437 }
438
439 /**
440 * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
441 * m}, which might be negative.
442 *
443 * <p>For example:
444 *
445 * <pre>{@code
446 * mod(7, 4) == 3
447 * mod(-7, 4) == 1
448 * mod(-1, 4) == 3
449 * mod(-8, 4) == 0
450 * mod(8, 4) == 0
451 * }</pre>
452 *
453 * @throws ArithmeticException if {@code m <= 0}
454 * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
455 * Remainder Operator</a>
456 */
457 @GwtIncompatible // TODO
458 public static int mod(long x, int m) {
459 // Cast is safe because the result is guaranteed in the range [0, m)
460 return (int) mod(x, (long) m);
461 }
462
463 /**
464 * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
465 * m}, which might be negative.
466 *
467 * <p>For example:
468 *
469 * <pre>{@code
470 * mod(7, 4) == 3
471 * mod(-7, 4) == 1
472 * mod(-1, 4) == 3
473 * mod(-8, 4) == 0
474 * mod(8, 4) == 0
475 * }</pre>
476 *
477 * @throws ArithmeticException if {@code m <= 0}
478 * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
479 * Remainder Operator</a>
480 */
481 @GwtIncompatible // TODO
482 public static long mod(long x, long m) {
483 if (m <= 0) {
484 throw new ArithmeticException("Modulus must be positive");
485 }
486 long result = x % m;
487 return (result >= 0) ? result : result + m;
488 }
489
490 /**
491 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b ==
492 * 0}.
493 *
494 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
495 */
496 public static long gcd(long a, long b) {
497 /*
498 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
499 * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't an
500 * int.
501 */
502 checkNonNegative("a", a);
503 checkNonNegative("b", b);
504 if (a == 0) {
505 // 0 % b == 0, so b divides a, but the converse doesn't hold.
506 // BigInteger.gcd is consistent with this decision.
507 return b;
508 } else if (b == 0) {
509 return a; // similar logic
510 }
511 /*
512 * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
513 * >60% faster than the Euclidean algorithm in benchmarks.
514 */
515 int aTwos = Long.numberOfTrailingZeros(a);
516 a >>= aTwos; // divide out all 2s
517 int bTwos = Long.numberOfTrailingZeros(b);
518 b >>= bTwos; // divide out all 2s
519 while (a != b) { // both a, b are odd
520 // The key to the binary GCD algorithm is as follows:
521 // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
522 // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
523
524 // We bend over backwards to avoid branching, adapting a technique from
525 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
526
527 long delta = a - b; // can't overflow, since a and b are nonnegative
528
529 long minDeltaOrZero = delta & (delta >> (Long.SIZE - 1));
530 // equivalent to Math.min(delta, 0)
531
532 a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
533 // a is now nonnegative and even
534
535 b += minDeltaOrZero; // sets b to min(old a, b)
536 a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
537 }
538 return a << min(aTwos, bTwos);
539 }
540
541 /**
542 * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
543 *
544 * @throws ArithmeticException if {@code a + b} overflows in signed {@code long} arithmetic
545 */
546 @GwtIncompatible // TODO
547 public static long checkedAdd(long a, long b) {
548 long result = a + b;
549 checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0, "checkedAdd", a, b);
550 return result;
551 }
552
553 /**
554 * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
555 *
556 * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic
557 */
558 @GwtIncompatible // TODO
559 public static long checkedSubtract(long a, long b) {
560 long result = a - b;
561 checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0, "checkedSubtract", a, b);
562 return result;
563 }
564
565 /**
566 * Returns the product of {@code a} and {@code b}, provided it does not overflow.
567 *
568 * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic
569 */
570 public static long checkedMultiply(long a, long b) {
571 // Hacker's Delight, Section 2-12
572 int leadingZeros =
573 Long.numberOfLeadingZeros(a)
574 + Long.numberOfLeadingZeros(~a)
575 + Long.numberOfLeadingZeros(b)
576 + Long.numberOfLeadingZeros(~b);
577 /*
578 * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely
579 * bad. We do the leadingZeros check to avoid the division below if at all possible.
580 *
581 * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take
582 * care of all a < 0 with their own check, because in particular, the case a == -1 will
583 * incorrectly pass the division check below.
584 *
585 * In all other cases, we check that either a is 0 or the result is consistent with division.
586 */
587 if (leadingZeros > Long.SIZE + 1) {
588 return a * b;
589 }
590 checkNoOverflow(leadingZeros >= Long.SIZE, "checkedMultiply", a, b);
591 checkNoOverflow(a >= 0 | b != Long.MIN_VALUE, "checkedMultiply", a, b);
592 long result = a * b;
593 checkNoOverflow(a == 0 || result / a == b, "checkedMultiply", a, b);
594 return result;
595 }
596
597 /**
598 * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
599 *
600 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code
601 * long} arithmetic
602 */
603 @GwtIncompatible // TODO
604 public static long checkedPow(long b, int k) {
605 checkNonNegative("exponent", k);
606 if (b >= -2 & b <= 2) {
607 switch ((int) b) {
608 case 0:
609 return (k == 0) ? 1 : 0;
610 case 1:
611 return 1;
612 case (-1):
613 return ((k & 1) == 0) ? 1 : -1;
614 case 2:
615 checkNoOverflow(k < Long.SIZE - 1, "checkedPow", b, k);
616 return 1L << k;
617 case (-2):
618 checkNoOverflow(k < Long.SIZE, "checkedPow", b, k);
619 return ((k & 1) == 0) ? (1L << k) : (-1L << k);
620 default:
621 throw new AssertionError();
622 }
623 }
624 long accum = 1;
625 while (true) {
626 switch (k) {
627 case 0:
628 return accum;
629 case 1:
630 return checkedMultiply(accum, b);
631 default:
632 if ((k & 1) != 0) {
633 accum = checkedMultiply(accum, b);
634 }
635 k >>= 1;
636 if (k > 0) {
637 checkNoOverflow(
638 -FLOOR_SQRT_MAX_LONG <= b && b <= FLOOR_SQRT_MAX_LONG, "checkedPow", b, k);
639 b *= b;
640 }
641 }
642 }
643 }
644
645 /**
646 * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
647 * {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
648 *
649 * @since 20.0
650 */
651 @Beta
652 public static long saturatedAdd(long a, long b) {
653 long naiveSum = a + b;
654 if ((a ^ b) < 0 | (a ^ naiveSum) >= 0) {
655 // If a and b have different signs or a has the same sign as the result then there was no
656 // overflow, return.
657 return naiveSum;
658 }
659 // we did over/under flow, if the sign is negative we should return MAX otherwise MIN
660 return Long.MAX_VALUE + ((naiveSum >>> (Long.SIZE - 1)) ^ 1);
661 }
662
663 /**
664 * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
665 * which case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
666 *
667 * @since 20.0
668 */
669 @Beta
670 public static long saturatedSubtract(long a, long b) {
671 long naiveDifference = a - b;
672 if ((a ^ b) >= 0 | (a ^ naiveDifference) >= 0) {
673 // If a and b have the same signs or a has the same sign as the result then there was no
674 // overflow, return.
675 return naiveDifference;
676 }
677 // we did over/under flow
678 return Long.MAX_VALUE + ((naiveDifference >>> (Long.SIZE - 1)) ^ 1);
679 }
680
681 /**
682 * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
683 * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
684 *
685 * @since 20.0
686 */
687 @Beta
688 public static long saturatedMultiply(long a, long b) {
689 // see checkedMultiply for explanation
690 int leadingZeros =
691 Long.numberOfLeadingZeros(a)
692 + Long.numberOfLeadingZeros(~a)
693 + Long.numberOfLeadingZeros(b)
694 + Long.numberOfLeadingZeros(~b);
695 if (leadingZeros > Long.SIZE + 1) {
696 return a * b;
697 }
698 // the return value if we will overflow (which we calculate by overflowing a long :) )
699 long limit = Long.MAX_VALUE + ((a ^ b) >>> (Long.SIZE - 1));
700 if (leadingZeros < Long.SIZE | (a < 0 & b == Long.MIN_VALUE)) {
701 // overflow
702 return limit;
703 }
704 long result = a * b;
705 if (a == 0 || result / a == b) {
706 return result;
707 }
708 return limit;
709 }
710
711 /**
712 * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which
713 * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
714 *
715 * @since 20.0
716 */
717 @Beta
718 public static long saturatedPow(long b, int k) {
719 checkNonNegative("exponent", k);
720 if (b >= -2 & b <= 2) {
721 switch ((int) b) {
722 case 0:
723 return (k == 0) ? 1 : 0;
724 case 1:
725 return 1;
726 case (-1):
727 return ((k & 1) == 0) ? 1 : -1;
728 case 2:
729 if (k >= Long.SIZE - 1) {
730 return Long.MAX_VALUE;
731 }
732 return 1L << k;
733 case (-2):
734 if (k >= Long.SIZE) {
735 return Long.MAX_VALUE + (k & 1);
736 }
737 return ((k & 1) == 0) ? (1L << k) : (-1L << k);
738 default:
739 throw new AssertionError();
740 }
741 }
742 long accum = 1;
743 // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX
744 long limit = Long.MAX_VALUE + ((b >>> Long.SIZE - 1) & (k & 1));
745 while (true) {
746 switch (k) {
747 case 0:
748 return accum;
749 case 1:
750 return saturatedMultiply(accum, b);
751 default:
752 if ((k & 1) != 0) {
753 accum = saturatedMultiply(accum, b);
754 }
755 k >>= 1;
756 if (k > 0) {
757 if (-FLOOR_SQRT_MAX_LONG > b | b > FLOOR_SQRT_MAX_LONG) {
758 return limit;
759 }
760 b *= b;
761 }
762 }
763 }
764 }
765
766 @VisibleForTesting static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
767
768 /**
769 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
770 * {@code n == 0}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
771 *
772 * @throws IllegalArgumentException if {@code n < 0}
773 */
774 @GwtIncompatible // TODO
775 public static long factorial(int n) {
776 checkNonNegative("n", n);
777 return (n < factorials.length) ? factorials[n] : Long.MAX_VALUE;
778 }
779
780 static final long[] factorials = {
781 1L,
782 1L,
783 1L * 2,
784 1L * 2 * 3,
785 1L * 2 * 3 * 4,
786 1L * 2 * 3 * 4 * 5,
787 1L * 2 * 3 * 4 * 5 * 6,
788 1L * 2 * 3 * 4 * 5 * 6 * 7,
789 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8,
790 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
791 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
792 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
793 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
794 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
795 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
796 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15,
797 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16,
798 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17,
799 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18,
800 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19,
801 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
802 };
803
804 /**
805 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
806 * {@code k}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
807 *
808 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
809 */
810 public static long binomial(int n, int k) {
811 checkNonNegative("n", n);
812 checkNonNegative("k", k);
813 checkArgument(k <= n, "k (%s) > n (%s)", k, n);
814 if (k > (n >> 1)) {
815 k = n - k;
816 }
817 switch (k) {
818 case 0:
819 return 1;
820 case 1:
821 return n;
822 default:
823 if (n < factorials.length) {
824 return factorials[n] / (factorials[k] * factorials[n - k]);
825 } else if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
826 return Long.MAX_VALUE;
827 } else if (k < biggestSimpleBinomials.length && n <= biggestSimpleBinomials[k]) {
828 // guaranteed not to overflow
829 long result = n--;
830 for (int i = 2; i <= k; n--, i++) {
831 result *= n;
832 result /= i;
833 }
834 return result;
835 } else {
836 int nBits = LongMath.log2(n, RoundingMode.CEILING);
837
838 long result = 1;
839 long numerator = n--;
840 long denominator = 1;
841
842 int numeratorBits = nBits;
843 // This is an upper bound on log2(numerator, ceiling).
844
845 /*
846 * We want to do this in long math for speed, but want to avoid overflow. We adapt the
847 * technique previously used by BigIntegerMath: maintain separate numerator and
848 * denominator accumulators, multiplying the fraction into result when near overflow.
849 */
850 for (int i = 2; i <= k; i++, n--) {
851 if (numeratorBits + nBits < Long.SIZE - 1) {
852 // It's definitely safe to multiply into numerator and denominator.
853 numerator *= n;
854 denominator *= i;
855 numeratorBits += nBits;
856 } else {
857 // It might not be safe to multiply into numerator and denominator,
858 // so multiply (numerator / denominator) into result.
859 result = multiplyFraction(result, numerator, denominator);
860 numerator = n;
861 denominator = i;
862 numeratorBits = nBits;
863 }
864 }
865 return multiplyFraction(result, numerator, denominator);
866 }
867 }
868 }
869
870 /** Returns (x * numerator / denominator), which is assumed to come out to an integral value. */
871 static long multiplyFraction(long x, long numerator, long denominator) {
872 if (x == 1) {
873 return numerator / denominator;
874 }
875 long commonDivisor = gcd(x, denominator);
876 x /= commonDivisor;
877 denominator /= commonDivisor;
878 // We know gcd(x, denominator) = 1, and x * numerator / denominator is exact,
879 // so denominator must be a divisor of numerator.
880 return x * (numerator / denominator);
881 }
882
883 /*
884 * binomial(biggestBinomials[k], k) fits in a long, but not binomial(biggestBinomials[k] + 1, k).
885 */
886 static final int[] biggestBinomials = {
887 Integer.MAX_VALUE,
888 Integer.MAX_VALUE,
889 Integer.MAX_VALUE,
890 3810779,
891 121977,
892 16175,
893 4337,
894 1733,
895 887,
896 534,
897 361,
898 265,
899 206,
900 169,
901 143,
902 125,
903 111,
904 101,
905 94,
906 88,
907 83,
908 79,
909 76,
910 74,
911 72,
912 70,
913 69,
914 68,
915 67,
916 67,
917 66,
918 66,
919 66,
920 66
921 };
922
923 /*
924 * binomial(biggestSimpleBinomials[k], k) doesn't need to use the slower GCD-based impl, but
925 * binomial(biggestSimpleBinomials[k] + 1, k) does.
926 */
927 @VisibleForTesting
928 static final int[] biggestSimpleBinomials = {
929 Integer.MAX_VALUE,
930 Integer.MAX_VALUE,
931 Integer.MAX_VALUE,
932 2642246,
933 86251,
934 11724,
935 3218,
936 1313,
937 684,
938 419,
939 287,
940 214,
941 169,
942 139,
943 119,
944 105,
945 95,
946 87,
947 81,
948 76,
949 73,
950 70,
951 68,
952 66,
953 64,
954 63,
955 62,
956 62,
957 61,
958 61,
959 61
960 };
961 // These values were generated by using checkedMultiply to see when the simple multiply/divide
962 // algorithm would lead to an overflow.
963
964 static boolean fitsInInt(long x) {
965 return (int) x == x;
966 }
967
968 /**
969 * Returns the arithmetic mean of {@code x} and {@code y}, rounded toward negative infinity. This
970 * method is resilient to overflow.
971 *
972 * @since 14.0
973 */
974 public static long mean(long x, long y) {
975 // Efficient method for computing the arithmetic mean.
976 // The alternative (x + y) / 2 fails for large values.
977 // The alternative (x + y) >>> 1 fails for negative values.
978 return (x & y) + ((x ^ y) >> 1);
979 }
980
981 /*
982 * This bitmask is used as an optimization for cheaply testing for divisiblity by 2, 3, or 5.
983 * Each bit is set to 1 for all remainders that indicate divisibility by 2, 3, or 5, so
984 * 1, 7, 11, 13, 17, 19, 23, 29 are set to 0. 30 and up don't matter because they won't be hit.
985 */
986 private static final int SIEVE_30 =
987 ~((1 << 1) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23)
988 | (1 << 29));
989
990 /**
991 * Returns {@code true} if {@code n} is a <a
992 * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
993 * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
994 * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be
995 * factored into smaller positive integers).
996 *
997 * <p>To test larger numbers, use {@link BigInteger#isProbablePrime}.
998 *
999 * @throws IllegalArgumentException if {@code n} is negative
1000 * @since 20.0
1001 */
1002 @GwtIncompatible // TODO
1003 @Beta
1004 public static boolean isPrime(long n) {
1005 if (n < 2) {
1006 checkNonNegative("n", n);
1007 return false;
1008 }
1009 if (n < 66) {
1010 // Encode all primes less than 66 into mask without 0 and 1.
1011 long mask =
1012 (1L << (2 - 2))
1013 | (1L << (3 - 2))
1014 | (1L << (5 - 2))
1015 | (1L << (7 - 2))
1016 | (1L << (11 - 2))
1017 | (1L << (13 - 2))
1018 | (1L << (17 - 2))
1019 | (1L << (19 - 2))
1020 | (1L << (23 - 2))
1021 | (1L << (29 - 2))
1022 | (1L << (31 - 2))
1023 | (1L << (37 - 2))
1024 | (1L << (41 - 2))
1025 | (1L << (43 - 2))
1026 | (1L << (47 - 2))
1027 | (1L << (53 - 2))
1028 | (1L << (59 - 2))
1029 | (1L << (61 - 2));
1030 // Look up n within the mask.
1031 return ((mask >> ((int) n - 2)) & 1) != 0;
1032 }
1033
1034 if ((SIEVE_30 & (1 << (n % 30))) != 0) {
1035 return false;
1036 }
1037 if (n % 7 == 0 || n % 11 == 0 || n % 13 == 0) {
1038 return false;
1039 }
1040 if (n < 17 * 17) {
1041 return true;
1042 }
1043
1044 for (long[] baseSet : millerRabinBaseSets) {
1045 if (n <= baseSet[0]) {
1046 for (int i = 1; i < baseSet.length; i++) {
1047 if (!MillerRabinTester.test(baseSet[i], n)) {
1048 return false;
1049 }
1050 }
1051 return true;
1052 }
1053 }
1054 throw new AssertionError();
1055 }
1056
1057 /*
1058 * If n <= millerRabinBases[i][0], then testing n against bases millerRabinBases[i][1..] suffices
1059 * to prove its primality. Values from miller-rabin.appspot.com.
1060 *
1061 * NOTE: We could get slightly better bases that would be treated as unsigned, but benchmarks
1062 * showed negligible performance improvements.
1063 */
1064 private static final long[][] millerRabinBaseSets = {
1065 {291830, 126401071349994536L},
1066 {885594168, 725270293939359937L, 3569819667048198375L},
1067 {273919523040L, 15, 7363882082L, 992620450144556L},
1068 {47636622961200L, 2, 2570940, 211991001, 3749873356L},
1069 {
1070 7999252175582850L,
1071 2,
1072 4130806001517L,
1073 149795463772692060L,
1074 186635894390467037L,
1075 3967304179347715805L
1076 },
1077 {
1078 585226005592931976L,
1079 2,
1080 123635709730000L,
1081 9233062284813009L,
1082 43835965440333360L,
1083 761179012939631437L,
1084 1263739024124850375L
1085 },
1086 {Long.MAX_VALUE, 2, 325, 9375, 28178, 450775, 9780504, 1795265022}
1087 };
1088
1089 private enum MillerRabinTester {
1090 /** Works for inputs ? FLOOR_SQRT_MAX_LONG. */
1091 SMALL {
1092 @Override
1093 long mulMod(long a, long b, long m) {
1094 /*
1095 * lowasser, 2015-Feb-12: Benchmarks suggest that changing this to UnsignedLongs.remainder
1096 * and increasing the threshold to 2^32 doesn't pay for itself, and adding another enum
1097 * constant hurts performance further -- I suspect because bimorphic implementation is a
1098 * sweet spot for the JVM.
1099 */
1100 return (a * b) % m;
1101 }
1102
1103 @Override
1104 long squareMod(long a, long m) {
1105 return (a * a) % m;
1106 }
1107 },
1108 /** Works for all nonnegative signed longs. */
1109 LARGE {
1110 /** Returns (a + b) mod m. Precondition: {@code 0 <= a}, {@code b < m < 2^63}. */
1111 private long plusMod(long a, long b, long m) {
1112 return (a >= m - b) ? (a + b - m) : (a + b);
1113 }
1114
1115 /** Returns (a * 2^32) mod m. a may be any unsigned long. */
1116 private long times2ToThe32Mod(long a, long m) {
1117 int remainingPowersOf2 = 32;
1118 do {
1119 int shift = Math.min(remainingPowersOf2, Long.numberOfLeadingZeros(a));
1120 // shift is either the number of powers of 2 left to multiply a by, or the biggest shift
1121 // possible while keeping a in an unsigned long.
1122 a = UnsignedLongs.remainder(a << shift, m);
1123 remainingPowersOf2 -= shift;
1124 } while (remainingPowersOf2 > 0);
1125 return a;
1126 }
1127
1128 @Override
1129 long mulMod(long a, long b, long m) {
1130 long aHi = a >>> 32; // < 2^31
1131 long bHi = b >>> 32; // < 2^31
1132 long aLo = a & 0xFFFFFFFFL; // < 2^32
1133 long bLo = b & 0xFFFFFFFFL; // < 2^32
1134
1135 /*
1136 * a * b == aHi * bHi * 2^64 + (aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo.
1137 * == (aHi * bHi * 2^32 + aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo
1138 *
1139 * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
1140 * unsigned long, we don't have to do a mod on every operation, only when intermediate
1141 * results can exceed 2^63.
1142 */
1143 long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
1144 result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
1145 if (result < 0) {
1146 result = UnsignedLongs.remainder(result, m);
1147 }
1148 // result < 2^63 again
1149 result += aLo * bHi; // aLo * bHi < 2^63, result < 2^64
1150 result = times2ToThe32Mod(result, m); // result < m < 2^63
1151 return plusMod(result, UnsignedLongs.remainder(aLo * bLo /* < 2^64 */, m), m);
1152 }
1153
1154 @Override
1155 long squareMod(long a, long m) {
1156 long aHi = a >>> 32; // < 2^31
1157 long aLo = a & 0xFFFFFFFFL; // < 2^32
1158
1159 /*
1160 * a^2 == aHi^2 * 2^64 + aHi * aLo * 2^33 + aLo^2
1161 * == (aHi^2 * 2^32 + aHi * aLo * 2) * 2^32 + aLo^2
1162 * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
1163 * unsigned long, we don't have to do a mod on every operation, only when intermediate
1164 * results can exceed 2^63.
1165 */
1166 long result = times2ToThe32Mod(aHi * aHi /* < 2^62 */, m); // < m < 2^63
1167 long hiLo = aHi * aLo * 2;
1168 if (hiLo < 0) {
1169 hiLo = UnsignedLongs.remainder(hiLo, m);
1170 }
1171 // hiLo < 2^63
1172 result += hiLo; // result < 2^64
1173 result = times2ToThe32Mod(result, m); // result < m < 2^63
1174 return plusMod(result, UnsignedLongs.remainder(aLo * aLo /* < 2^64 */, m), m);
1175 }
1176 };
1177
1178 static boolean test(long base, long n) {
1179 // Since base will be considered % n, it's okay if base > FLOOR_SQRT_MAX_LONG,
1180 // so long as n <= FLOOR_SQRT_MAX_LONG.
1181 return ((n <= FLOOR_SQRT_MAX_LONG) ? SMALL : LARGE).testWitness(base, n);
1182 }
1183
1184 /** Returns a * b mod m. */
1185 abstract long mulMod(long a, long b, long m);
1186
1187 /** Returns a^2 mod m. */
1188 abstract long squareMod(long a, long m);
1189
1190 /** Returns a^p mod m. */
1191 private long powMod(long a, long p, long m) {
1192 long res = 1;
1193 for (; p != 0; p >>= 1) {
1194 if ((p & 1) != 0) {
1195 res = mulMod(res, a, m);
1196 }
1197 a = squareMod(a, m);
1198 }
1199 return res;
1200 }
1201
1202 /** Returns true if n is a strong probable prime relative to the specified base. */
1203 private boolean testWitness(long base, long n) {
1204 int r = Long.numberOfTrailingZeros(n - 1);
1205 long d = (n - 1) >> r;
1206 base %= n;
1207 if (base == 0) {
1208 return true;
1209 }
1210 // Calculate a := base^d mod n.
1211 long a = powMod(base, d, n);
1212 // n passes this test if
1213 // base^d = 1 (mod n)
1214 // or base^(2^j * d) = -1 (mod n) for some 0 <= j < r.
1215 if (a == 1) {
1216 return true;
1217 }
1218 int j = 0;
1219 while (a != n - 1) {
1220 if (++j == r) {
1221 return false;
1222 }
1223 a = squareMod(a, n);
1224 }
1225 return true;
1226 }
1227 }
1228
1229 /**
1230 * Returns {@code x}, rounded to a {@code double} with the specified rounding mode. If {@code x}
1231 * is precisely representable as a {@code double}, its {@code double} value will be returned;
1232 * otherwise, the rounding will choose between the two nearest representable values with {@code
1233 * mode}.
1234 *
1235 * <p>For the case of {@link RoundingMode#HALF_EVEN}, this implementation uses the IEEE 754
1236 * default rounding mode: if the two nearest representable values are equally near, the one with
1237 * the least significant bit zero is chosen. (In such cases, both of the nearest representable
1238 * values are even integers; this method returns the one that is a multiple of a greater power of
1239 * two.)
1240 *
1241 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
1242 * is not precisely representable as a {@code double}
1243 * @since 30.0
1244 */
1245 @SuppressWarnings("deprecation")
1246 @GwtIncompatible
1247 public static double roundToDouble(long x, RoundingMode mode) {
1248 // Logic adapted from ToDoubleRounder.
1249 double roundArbitrarily = (double) x;
1250 long roundArbitrarilyAsLong = (long) roundArbitrarily;
1251 int cmpXToRoundArbitrarily;
1252
1253 if (roundArbitrarilyAsLong == Long.MAX_VALUE) {
1254 /*
1255 * For most values, the conversion from roundArbitrarily to roundArbitrarilyAsLong is
1256 * lossless. In that case we can compare x to roundArbitrarily using Longs.compare(x,
1257 * roundArbitrarilyAsLong). The exception is for values where the conversion to double rounds
1258 * up to give roundArbitrarily equal to 2^63, so the conversion back to long overflows and
1259 * roundArbitrarilyAsLong is Long.MAX_VALUE. (This is the only way this condition can occur as
1260 * otherwise the conversion back to long pads with zero bits.) In this case we know that
1261 * roundArbitrarily > x. (This is important when x == Long.MAX_VALUE ==
1262 * roundArbitrarilyAsLong.)
1263 */
1264 cmpXToRoundArbitrarily = -1;
1265 } else {
1266 cmpXToRoundArbitrarily = Longs.compare(x, roundArbitrarilyAsLong);
1267 }
1268
1269 switch (mode) {
1270 case UNNECESSARY:
1271 checkRoundingUnnecessary(cmpXToRoundArbitrarily == 0);
1272 return roundArbitrarily;
1273 case FLOOR:
1274 return (cmpXToRoundArbitrarily >= 0)
1275 ? roundArbitrarily
1276 : DoubleUtils.nextDown(roundArbitrarily);
1277 case CEILING:
1278 return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1279 case DOWN:
1280 if (x >= 0) {
1281 return (cmpXToRoundArbitrarily >= 0)
1282 ? roundArbitrarily
1283 : DoubleUtils.nextDown(roundArbitrarily);
1284 } else {
1285 return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1286 }
1287 case UP:
1288 if (x >= 0) {
1289 return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1290 } else {
1291 return (cmpXToRoundArbitrarily >= 0)
1292 ? roundArbitrarily
1293 : DoubleUtils.nextDown(roundArbitrarily);
1294 }
1295 case HALF_DOWN:
1296 case HALF_UP:
1297 case HALF_EVEN:
1298 {
1299 long roundFloor;
1300 double roundFloorAsDouble;
1301 long roundCeiling;
1302 double roundCeilingAsDouble;
1303
1304 if (cmpXToRoundArbitrarily >= 0) {
1305 roundFloorAsDouble = roundArbitrarily;
1306 roundFloor = roundArbitrarilyAsLong;
1307 roundCeilingAsDouble = Math.nextUp(roundArbitrarily);
1308 roundCeiling = (long) Math.ceil(roundCeilingAsDouble);
1309 } else {
1310 roundCeilingAsDouble = roundArbitrarily;
1311 roundCeiling = roundArbitrarilyAsLong;
1312 roundFloorAsDouble = DoubleUtils.nextDown(roundArbitrarily);
1313 roundFloor = (long) Math.floor(roundFloorAsDouble);
1314 }
1315
1316 long deltaToFloor = x - roundFloor;
1317 long deltaToCeiling = roundCeiling - x;
1318
1319 if (roundCeiling == Long.MAX_VALUE) {
1320 // correct for Long.MAX_VALUE as discussed above: roundCeilingAsDouble must be 2^63, but
1321 // roundCeiling is 2^63-1.
1322 deltaToCeiling++;
1323 }
1324
1325 int diff = Longs.compare(deltaToFloor, deltaToCeiling);
1326 if (diff < 0) { // closer to floor
1327 return roundFloorAsDouble;
1328 } else if (diff > 0) { // closer to ceiling
1329 return roundCeilingAsDouble;
1330 }
1331 // halfway between the representable values; do the half-whatever logic
1332 switch (mode) {
1333 case HALF_EVEN:
1334 return ((DoubleUtils.getSignificand(roundFloorAsDouble) & 1L) == 0)
1335 ? roundFloorAsDouble
1336 : roundCeilingAsDouble;
1337 case HALF_DOWN:
1338 return (x >= 0) ? roundFloorAsDouble : roundCeilingAsDouble;
1339 case HALF_UP:
1340 return (x >= 0) ? roundCeilingAsDouble : roundFloorAsDouble;
1341 default:
1342 throw new AssertionError("impossible");
1343 }
1344 }
1345 }
1346 throw new AssertionError("impossible");
1347 }
1348
1349 private LongMath() {}
1350 }