001 /*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.math;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.math.MathPreconditions.checkNoOverflow;
022 import static com.google.common.math.MathPreconditions.checkNonNegative;
023 import static com.google.common.math.MathPreconditions.checkPositive;
024 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
025 import static java.lang.Math.abs;
026 import static java.lang.Math.min;
027 import static java.math.RoundingMode.HALF_EVEN;
028 import static java.math.RoundingMode.HALF_UP;
029
030 import com.google.common.annotations.Beta;
031 import com.google.common.annotations.GwtCompatible;
032 import com.google.common.annotations.GwtIncompatible;
033 import com.google.common.annotations.VisibleForTesting;
034
035 import java.math.BigInteger;
036 import java.math.RoundingMode;
037
038 /**
039 * A class for arithmetic on values of type {@code long}. Where possible, methods are defined and
040 * named analogously to their {@code BigInteger} counterparts.
041 *
042 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
043 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
044 *
045 * <p>Similar functionality for {@code int} and for {@link BigInteger} can be found in
046 * {@link IntMath} and {@link BigIntegerMath} respectively. For other common operations on
047 * {@code long} values, see {@link com.google.common.primitives.Longs}.
048 *
049 * @author Louis Wasserman
050 * @since 11.0
051 */
052 @Beta
053 @GwtCompatible(emulated = true)
054 public final class LongMath {
055 // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
056
057 /**
058 * Returns {@code true} if {@code x} represents a power of two.
059 *
060 * <p>This differs from {@code Long.bitCount(x) == 1}, because
061 * {@code Long.bitCount(Long.MIN_VALUE) == 1}, but {@link Long#MIN_VALUE} is not a power of two.
062 */
063 public static boolean isPowerOfTwo(long x) {
064 return x > 0 & (x & (x - 1)) == 0;
065 }
066
067 /**
068 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
069 *
070 * @throws IllegalArgumentException if {@code x <= 0}
071 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
072 * is not a power of two
073 */
074 @SuppressWarnings("fallthrough")
075 public static int log2(long x, RoundingMode mode) {
076 checkPositive("x", x);
077 switch (mode) {
078 case UNNECESSARY:
079 checkRoundingUnnecessary(isPowerOfTwo(x));
080 // fall through
081 case DOWN:
082 case FLOOR:
083 return (Long.SIZE - 1) - Long.numberOfLeadingZeros(x);
084
085 case UP:
086 case CEILING:
087 return Long.SIZE - Long.numberOfLeadingZeros(x - 1);
088
089 case HALF_DOWN:
090 case HALF_UP:
091 case HALF_EVEN:
092 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
093 int leadingZeros = Long.numberOfLeadingZeros(x);
094 long cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
095 // floor(2^(logFloor + 0.5))
096 int logFloor = (Long.SIZE - 1) - leadingZeros;
097 return (x <= cmp) ? logFloor : logFloor + 1;
098
099 default:
100 throw new AssertionError("impossible");
101 }
102 }
103
104 /** The biggest half power of two that fits into an unsigned long */
105 @VisibleForTesting static final long MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333F9DE6484L;
106
107 /**
108 * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
109 *
110 * @throws IllegalArgumentException if {@code x <= 0}
111 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
112 * is not a power of ten
113 */
114 @GwtIncompatible("TODO")
115 @SuppressWarnings("fallthrough")
116 public static int log10(long x, RoundingMode mode) {
117 checkPositive("x", x);
118 if (fitsInInt(x)) {
119 return IntMath.log10((int) x, mode);
120 }
121 int logFloor = log10Floor(x);
122 long floorPow = POWERS_OF_10[logFloor];
123 switch (mode) {
124 case UNNECESSARY:
125 checkRoundingUnnecessary(x == floorPow);
126 // fall through
127 case FLOOR:
128 case DOWN:
129 return logFloor;
130 case CEILING:
131 case UP:
132 return (x == floorPow) ? logFloor : logFloor + 1;
133 case HALF_DOWN:
134 case HALF_UP:
135 case HALF_EVEN:
136 // sqrt(10) is irrational, so log10(x)-logFloor is never exactly 0.5
137 return (x <= HALF_POWERS_OF_10[logFloor]) ? logFloor : logFloor + 1;
138 default:
139 throw new AssertionError();
140 }
141 }
142
143 @GwtIncompatible("TODO")
144 static int log10Floor(long x) {
145 for (int i = 1; i < POWERS_OF_10.length; i++) {
146 if (x < POWERS_OF_10[i]) {
147 return i - 1;
148 }
149 }
150 return POWERS_OF_10.length - 1;
151 }
152
153 @GwtIncompatible("TODO")
154 @VisibleForTesting
155 static final long[] POWERS_OF_10 = {
156 1L,
157 10L,
158 100L,
159 1000L,
160 10000L,
161 100000L,
162 1000000L,
163 10000000L,
164 100000000L,
165 1000000000L,
166 10000000000L,
167 100000000000L,
168 1000000000000L,
169 10000000000000L,
170 100000000000000L,
171 1000000000000000L,
172 10000000000000000L,
173 100000000000000000L,
174 1000000000000000000L
175 };
176
177 // HALF_POWERS_OF_10[i] = largest long less than 10^(i + 0.5)
178 @GwtIncompatible("TODO")
179 @VisibleForTesting
180 static final long[] HALF_POWERS_OF_10 = {
181 3L,
182 31L,
183 316L,
184 3162L,
185 31622L,
186 316227L,
187 3162277L,
188 31622776L,
189 316227766L,
190 3162277660L,
191 31622776601L,
192 316227766016L,
193 3162277660168L,
194 31622776601683L,
195 316227766016837L,
196 3162277660168379L,
197 31622776601683793L,
198 316227766016837933L,
199 3162277660168379331L
200 };
201
202 /**
203 * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
204 * {@code BigInteger.valueOf(b).pow(k).longValue()}. This implementation runs in {@code O(log k)}
205 * time.
206 *
207 * @throws IllegalArgumentException if {@code k < 0}
208 */
209 @GwtIncompatible("TODO")
210 public static long pow(long b, int k) {
211 checkNonNegative("exponent", k);
212 if (-2 <= b && b <= 2) {
213 switch ((int) b) {
214 case 0:
215 return (k == 0) ? 1 : 0;
216 case 1:
217 return 1;
218 case (-1):
219 return ((k & 1) == 0) ? 1 : -1;
220 case 2:
221 return (k < Long.SIZE) ? 1L << k : 0;
222 case (-2):
223 if (k < Long.SIZE) {
224 return ((k & 1) == 0) ? 1L << k : -(1L << k);
225 } else {
226 return 0;
227 }
228 }
229 }
230 for (long accum = 1;; k >>= 1) {
231 switch (k) {
232 case 0:
233 return accum;
234 case 1:
235 return accum * b;
236 default:
237 accum *= ((k & 1) == 0) ? 1 : b;
238 b *= b;
239 }
240 }
241 }
242
243 /**
244 * Returns the square root of {@code x}, rounded with the specified rounding mode.
245 *
246 * @throws IllegalArgumentException if {@code x < 0}
247 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and
248 * {@code sqrt(x)} is not an integer
249 */
250 @GwtIncompatible("TODO")
251 @SuppressWarnings("fallthrough")
252 public static long sqrt(long x, RoundingMode mode) {
253 checkNonNegative("x", x);
254 if (fitsInInt(x)) {
255 return IntMath.sqrt((int) x, mode);
256 }
257 long sqrtFloor = sqrtFloor(x);
258 switch (mode) {
259 case UNNECESSARY:
260 checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through
261 case FLOOR:
262 case DOWN:
263 return sqrtFloor;
264 case CEILING:
265 case UP:
266 return (sqrtFloor * sqrtFloor == x) ? sqrtFloor : sqrtFloor + 1;
267 case HALF_DOWN:
268 case HALF_UP:
269 case HALF_EVEN:
270 long halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
271 /*
272 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both
273 * x and halfSquare are integers, this is equivalent to testing whether or not x <=
274 * halfSquare. (We have to deal with overflow, though.)
275 */
276 return (halfSquare >= x | halfSquare < 0) ? sqrtFloor : sqrtFloor + 1;
277 default:
278 throw new AssertionError();
279 }
280 }
281
282 @GwtIncompatible("TODO")
283 private static long sqrtFloor(long x) {
284 // Hackers's Delight, Figure 11-1
285 long sqrt0 = (long) Math.sqrt(x);
286 // Precision can be lost in the cast to double, so we use this as a starting estimate.
287 long sqrt1 = (sqrt0 + (x / sqrt0)) >> 1;
288 if (sqrt1 == sqrt0) {
289 return sqrt0;
290 }
291 do {
292 sqrt0 = sqrt1;
293 sqrt1 = (sqrt0 + (x / sqrt0)) >> 1;
294 } while (sqrt1 < sqrt0);
295 return sqrt0;
296 }
297
298 /**
299 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified
300 * {@code RoundingMode}.
301 *
302 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
303 * is not an integer multiple of {@code b}
304 */
305 @GwtIncompatible("TODO")
306 @SuppressWarnings("fallthrough")
307 public static long divide(long p, long q, RoundingMode mode) {
308 checkNotNull(mode);
309 long div = p / q; // throws if q == 0
310 long rem = p - q * div; // equals p % q
311
312 if (rem == 0) {
313 return div;
314 }
315
316 /*
317 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
318 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
319 * p / q.
320 *
321 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
322 */
323 int signum = 1 | (int) ((p ^ q) >> (Long.SIZE - 1));
324 boolean increment;
325 switch (mode) {
326 case UNNECESSARY:
327 checkRoundingUnnecessary(rem == 0);
328 // fall through
329 case DOWN:
330 increment = false;
331 break;
332 case UP:
333 increment = true;
334 break;
335 case CEILING:
336 increment = signum > 0;
337 break;
338 case FLOOR:
339 increment = signum < 0;
340 break;
341 case HALF_EVEN:
342 case HALF_DOWN:
343 case HALF_UP:
344 long absRem = abs(rem);
345 long cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
346 // subtracting two nonnegative longs can't overflow
347 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
348 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
349 increment = (mode == HALF_UP | (mode == HALF_EVEN & (div & 1) != 0));
350 } else {
351 increment = cmpRemToHalfDivisor > 0; // closer to the UP value
352 }
353 break;
354 default:
355 throw new AssertionError();
356 }
357 return increment ? div + signum : div;
358 }
359
360 /**
361 * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a
362 * non-negative result.
363 *
364 * <p>For example:
365 *
366 * <pre> {@code
367 *
368 * mod(7, 4) == 3
369 * mod(-7, 4) == 1
370 * mod(-1, 4) == 3
371 * mod(-8, 4) == 0
372 * mod(8, 4) == 0}</pre>
373 *
374 * @throws ArithmeticException if {@code m <= 0}
375 */
376 @GwtIncompatible("TODO")
377 public static int mod(long x, int m) {
378 // Cast is safe because the result is guaranteed in the range [0, m)
379 return (int) mod(x, (long) m);
380 }
381
382 /**
383 * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a
384 * non-negative result.
385 *
386 * <p>For example:
387 *
388 * <pre> {@code
389 *
390 * mod(7, 4) == 3
391 * mod(-7, 4) == 1
392 * mod(-1, 4) == 3
393 * mod(-8, 4) == 0
394 * mod(8, 4) == 0}</pre>
395 *
396 * @throws ArithmeticException if {@code m <= 0}
397 */
398 @GwtIncompatible("TODO")
399 public static long mod(long x, long m) {
400 if (m <= 0) {
401 throw new ArithmeticException("Modulus " + m + " must be > 0");
402 }
403 long result = x % m;
404 return (result >= 0) ? result : result + m;
405 }
406
407 /**
408 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if
409 * {@code a == 0 && b == 0}.
410 *
411 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
412 */
413 @GwtIncompatible("TODO")
414 public static long gcd(long a, long b) {
415 /*
416 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
417 * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't
418 * an int.
419 */
420 checkNonNegative("a", a);
421 checkNonNegative("b", b);
422 if (a == 0 | b == 0) {
423 return a | b;
424 }
425 /*
426 * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm.
427 * This is over 40% faster than the Euclidean algorithm in benchmarks.
428 */
429 int aTwos = Long.numberOfTrailingZeros(a);
430 a >>= aTwos; // divide out all 2s
431 int bTwos = Long.numberOfTrailingZeros(b);
432 b >>= bTwos; // divide out all 2s
433 while (a != b) { // both a, b are odd
434 if (a < b) { // swap a, b
435 long t = b;
436 b = a;
437 a = t;
438 }
439 a -= b; // a is now positive and even
440 a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
441 }
442 return a << min(aTwos, bTwos);
443 }
444
445 /**
446 * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
447 *
448 * @throws ArithmeticException if {@code a + b} overflows in signed {@code long} arithmetic
449 */
450 @GwtIncompatible("TODO")
451 public static long checkedAdd(long a, long b) {
452 long result = a + b;
453 checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0);
454 return result;
455 }
456
457 /**
458 * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
459 *
460 * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic
461 */
462 @GwtIncompatible("TODO")
463 public static long checkedSubtract(long a, long b) {
464 long result = a - b;
465 checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0);
466 return result;
467 }
468
469 /**
470 * Returns the product of {@code a} and {@code b}, provided it does not overflow.
471 *
472 * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic
473 */
474 @GwtIncompatible("TODO")
475 public static long checkedMultiply(long a, long b) {
476 // Hacker's Delight, Section 2-12
477 int leadingZeros = Long.numberOfLeadingZeros(a) + Long.numberOfLeadingZeros(~a)
478 + Long.numberOfLeadingZeros(b) + Long.numberOfLeadingZeros(~b);
479 /*
480 * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely
481 * bad. We do the leadingZeros check to avoid the division below if at all possible.
482 *
483 * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take
484 * care of all a < 0 with their own check, because in particular, the case a == -1 will
485 * incorrectly pass the division check below.
486 *
487 * In all other cases, we check that either a is 0 or the result is consistent with division.
488 */
489 if (leadingZeros > Long.SIZE + 1) {
490 return a * b;
491 }
492 checkNoOverflow(leadingZeros >= Long.SIZE);
493 checkNoOverflow(a >= 0 | b != Long.MIN_VALUE);
494 long result = a * b;
495 checkNoOverflow(a == 0 || result / a == b);
496 return result;
497 }
498
499 /**
500 * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
501 *
502 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed
503 * {@code long} arithmetic
504 */
505 @GwtIncompatible("TODO")
506 public static long checkedPow(long b, int k) {
507 checkNonNegative("exponent", k);
508 if (b >= -2 & b <= 2) {
509 switch ((int) b) {
510 case 0:
511 return (k == 0) ? 1 : 0;
512 case 1:
513 return 1;
514 case (-1):
515 return ((k & 1) == 0) ? 1 : -1;
516 case 2:
517 checkNoOverflow(k < Long.SIZE - 1);
518 return 1L << k;
519 case (-2):
520 checkNoOverflow(k < Long.SIZE);
521 return ((k & 1) == 0) ? (1L << k) : (-1L << k);
522 }
523 }
524 long accum = 1;
525 while (true) {
526 switch (k) {
527 case 0:
528 return accum;
529 case 1:
530 return checkedMultiply(accum, b);
531 default:
532 if ((k & 1) != 0) {
533 accum = checkedMultiply(accum, b);
534 }
535 k >>= 1;
536 if (k > 0) {
537 checkNoOverflow(b <= FLOOR_SQRT_MAX_LONG);
538 b *= b;
539 }
540 }
541 }
542 }
543
544 @GwtIncompatible("TODO")
545 @VisibleForTesting static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
546
547 /**
548 * Returns {@code n!}, that is, the product of the first {@code n} positive
549 * integers, {@code 1} if {@code n == 0}, or {@link Long#MAX_VALUE} if the
550 * result does not fit in a {@code long}.
551 *
552 * @throws IllegalArgumentException if {@code n < 0}
553 */
554 @GwtIncompatible("TODO")
555 public static long factorial(int n) {
556 checkNonNegative("n", n);
557 return (n < FACTORIALS.length) ? FACTORIALS[n] : Long.MAX_VALUE;
558 }
559
560 static final long[] FACTORIALS = {
561 1L,
562 1L,
563 1L * 2,
564 1L * 2 * 3,
565 1L * 2 * 3 * 4,
566 1L * 2 * 3 * 4 * 5,
567 1L * 2 * 3 * 4 * 5 * 6,
568 1L * 2 * 3 * 4 * 5 * 6 * 7,
569 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8,
570 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
571 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
572 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
573 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
574 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
575 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
576 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15,
577 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16,
578 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17,
579 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18,
580 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19,
581 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
582 };
583
584 /**
585 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
586 * {@code k}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
587 *
588 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
589 */
590 public static long binomial(int n, int k) {
591 checkNonNegative("n", n);
592 checkNonNegative("k", k);
593 checkArgument(k <= n, "k (%s) > n (%s)", k, n);
594 if (k > (n >> 1)) {
595 k = n - k;
596 }
597 if (k >= BIGGEST_BINOMIALS.length || n > BIGGEST_BINOMIALS[k]) {
598 return Long.MAX_VALUE;
599 }
600 long result = 1;
601 if (k < BIGGEST_SIMPLE_BINOMIALS.length && n <= BIGGEST_SIMPLE_BINOMIALS[k]) {
602 // guaranteed not to overflow
603 for (int i = 0; i < k; i++) {
604 result *= n - i;
605 result /= i + 1;
606 }
607 } else {
608 // We want to do this in long math for speed, but want to avoid overflow.
609 // Dividing by the GCD suffices to avoid overflow in all the remaining cases.
610 for (int i = 1; i <= k; i++, n--) {
611 int d = IntMath.gcd(n, i);
612 result /= i / d; // (i/d) is guaranteed to divide result
613 result *= n / d;
614 }
615 }
616 return result;
617 }
618
619 /*
620 * binomial(BIGGEST_BINOMIALS[k], k) fits in a long, but not
621 * binomial(BIGGEST_BINOMIALS[k] + 1, k).
622 */
623 static final int[] BIGGEST_BINOMIALS =
624 {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3810779, 121977, 16175, 4337, 1733,
625 887, 534, 361, 265, 206, 169, 143, 125, 111, 101, 94, 88, 83, 79, 76, 74, 72, 70, 69, 68,
626 67, 67, 66, 66, 66, 66};
627
628 /*
629 * binomial(BIGGEST_SIMPLE_BINOMIALS[k], k) doesn't need to use the slower GCD-based impl,
630 * but binomial(BIGGEST_SIMPLE_BINOMIALS[k] + 1, k) does.
631 */
632 @VisibleForTesting static final int[] BIGGEST_SIMPLE_BINOMIALS =
633 {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 2642246, 86251, 11724, 3218, 1313,
634 684, 419, 287, 214, 169, 139, 119, 105, 95, 87, 81, 76, 73, 70, 68, 66, 64, 63, 62, 62,
635 61, 61, 61};
636 // These values were generated by using checkedMultiply to see when the simple multiply/divide
637 // algorithm would lead to an overflow.
638
639 @GwtIncompatible("TODO")
640 static boolean fitsInInt(long x) {
641 return (int) x == x;
642 }
643
644 private LongMath() {}
645 }