ArithmeticUtils { public static int gcd(int p, int q) throws MathArithmeticException { int a = p; int b = q; if (a == 0 || b == 0) { if (a == Integer.MIN_VALUE || b == Integer.MIN_VALUE) { throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); } return FastMath.abs(a + b); } long al = a; long bl = b; boolean useLong = false; if (a < 0) { if(Integer.MIN_VALUE == a) { useLong = true; } else { a = -a; } al = -al; } if (b < 0) { if (Integer.MIN_VALUE == b) { useLong = true; } else { b = -b; } bl = -bl; } if (useLong) { if(al == bl) { throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); } long blbu = bl; bl = al; al = blbu % al; if (al == 0) { if (bl > Integer.MAX_VALUE) { throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); } return (int) bl; } blbu = bl; b = (int) al; a = (int) (blbu % al); } return gcdPositive(a, b); } private  ArithmeticUtils(); static int addAndCheck(int x, int y); static long addAndCheck(long a, long b); @Deprecated static long binomialCoefficient(final int n, final int k); @Deprecated static double binomialCoefficientDouble(final int n, final int k); @Deprecated static double binomialCoefficientLog(final int n, final int k); @Deprecated static long factorial(final int n); @Deprecated static double factorialDouble(final int n); @Deprecated static double factorialLog(final int n); static int gcd(int p, int q); static long gcd(final long p, final long q); static int lcm(int a, int b); static long lcm(long a, long b); static int mulAndCheck(int x, int y); static long mulAndCheck(long a, long b); static int subAndCheck(int x, int y); static long subAndCheck(long a, long b); static int pow(final int k,
                          final int e); @Deprecated static int pow(final int k, long e); static long pow(final long k,
                           final int e); @Deprecated static long pow(final long k, long e); static BigInteger pow(final BigInteger k, int e); static BigInteger pow(final BigInteger k, long e); static BigInteger pow(final BigInteger k, BigInteger e); @Deprecated static long stirlingS2(final int n, final int k); static boolean isPowerOfTwo(long n);  }
@Test public void testGcd() { int a = 30; int b = 50; int c = 77; Assert.assertEquals(0, ArithmeticUtils.gcd(0, 0)); Assert.assertEquals(b, ArithmeticUtils.gcd(0, b)); Assert.assertEquals(a, ArithmeticUtils.gcd(a, 0)); Assert.assertEquals(b, ArithmeticUtils.gcd(0, -b)); Assert.assertEquals(a, ArithmeticUtils.gcd(-a, 0)); Assert.assertEquals(10, ArithmeticUtils.gcd(a, b)); Assert.assertEquals(10, ArithmeticUtils.gcd(-a, b)); Assert.assertEquals(10, ArithmeticUtils.gcd(a, -b)); Assert.assertEquals(10, ArithmeticUtils.gcd(-a, -b)); Assert.assertEquals(1, ArithmeticUtils.gcd(a, c)); Assert.assertEquals(1, ArithmeticUtils.gcd(-a, c)); Assert.assertEquals(1, ArithmeticUtils.gcd(a, -c)); Assert.assertEquals(1, ArithmeticUtils.gcd(-a, -c)); Assert.assertEquals(3 * (1<<15), ArithmeticUtils.gcd(3 * (1<<20), 9 * (1<<15))); Assert.assertEquals(Integer.MAX_VALUE, ArithmeticUtils.gcd(Integer.MAX_VALUE, 0)); Assert.assertEquals(Integer.MAX_VALUE, ArithmeticUtils.gcd(-Integer.MAX_VALUE, 0)); Assert.assertEquals(1<<30, ArithmeticUtils.gcd(1<<30, -Integer.MIN_VALUE)); try { ArithmeticUtils.gcd(Integer.MIN_VALUE, 0); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } try { ArithmeticUtils.gcd(0, Integer.MIN_VALUE); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } try { ArithmeticUtils.gcd(Integer.MIN_VALUE, Integer.MIN_VALUE); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } }
@Test public void testGcdConsistency() { int[] primeList = {19, 23, 53, 67, 73, 79, 101, 103, 111, 131}; ArrayList<Integer> primes = new ArrayList<Integer>(); for (int i = 0; i < primeList.length; i++) { primes.add(Integer.valueOf(primeList[i])); } RandomDataGenerator randomData = new RandomDataGenerator(); for (int i = 0; i < 20; i++) { Object[] sample = randomData.nextSample(primes, 4); int p1 = ((Integer) sample[0]).intValue(); int p2 = ((Integer) sample[1]).intValue(); int p3 = ((Integer) sample[2]).intValue(); int p4 = ((Integer) sample[3]).intValue(); int i1 = p1 * p2 * p3; int i2 = p1 * p2 * p4; int gcd = p1 * p2; Assert.assertEquals(gcd, ArithmeticUtils.gcd(i1, i2)); long l1 = i1; long l2 = i2; Assert.assertEquals(gcd, ArithmeticUtils.gcd(l1, l2)); } }
@Test public void testGcdLong(){ long a = 30; long b = 50; long c = 77; Assert.assertEquals(0, ArithmeticUtils.gcd(0L, 0)); Assert.assertEquals(b, ArithmeticUtils.gcd(0, b)); Assert.assertEquals(a, ArithmeticUtils.gcd(a, 0)); Assert.assertEquals(b, ArithmeticUtils.gcd(0, -b)); Assert.assertEquals(a, ArithmeticUtils.gcd(-a, 0)); Assert.assertEquals(10, ArithmeticUtils.gcd(a, b)); Assert.assertEquals(10, ArithmeticUtils.gcd(-a, b)); Assert.assertEquals(10, ArithmeticUtils.gcd(a, -b)); Assert.assertEquals(10, ArithmeticUtils.gcd(-a, -b)); Assert.assertEquals(1, ArithmeticUtils.gcd(a, c)); Assert.assertEquals(1, ArithmeticUtils.gcd(-a, c)); Assert.assertEquals(1, ArithmeticUtils.gcd(a, -c)); Assert.assertEquals(1, ArithmeticUtils.gcd(-a, -c)); Assert.assertEquals(3L * (1L<<45), ArithmeticUtils.gcd(3L * (1L<<50), 9L * (1L<<45))); Assert.assertEquals(1L<<45, ArithmeticUtils.gcd(1L<<45, Long.MIN_VALUE)); Assert.assertEquals(Long.MAX_VALUE, ArithmeticUtils.gcd(Long.MAX_VALUE, 0L)); Assert.assertEquals(Long.MAX_VALUE, ArithmeticUtils.gcd(-Long.MAX_VALUE, 0L)); Assert.assertEquals(1, ArithmeticUtils.gcd(60247241209L, 153092023L)); try { ArithmeticUtils.gcd(Long.MIN_VALUE, 0); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } try { ArithmeticUtils.gcd(0, Long.MIN_VALUE); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } try { ArithmeticUtils.gcd(Long.MIN_VALUE, Long.MIN_VALUE); Assert.fail("expecting MathArithmeticException"); } catch (MathArithmeticException expected) { } }