Class Gcd

java.lang.Object
de.tilman_neumann.jml.gcd.Gcd

public class Gcd
extends java.lang.Object
GCD implementations for BigIntegers. By far the fastest implementation is BigInteger's gcd(), which uses a hybrid gcd with a very fast binary gcd implementation.
  • Constructor Summary

    Constructors
    Constructor Description
    Gcd()  
  • Method Summary

    Modifier and Type Method Description
    static java.math.BigInteger gcd​(java.math.BigInteger[] arguments)
    GCD of k arguments n1, n2, ..., nk.
    java.math.BigInteger gcd​(java.math.BigInteger a, java.math.BigInteger b)
    Slightly faster binary gcd adapted from OpenJdk's MutableBigInteger.binaryGcd(int, int).
    static java.math.BigInteger gcd​(java.util.Collection<java.math.BigInteger> arguments)
    GCD of k arguments n1, n2, ..., nk.
    java.math.BigInteger gcd_binary1​(java.math.BigInteger m, java.math.BigInteger n)
    Binary gcd implementation.
    java.math.BigInteger gcd_euclid_withDivision​(java.math.BigInteger m, java.math.BigInteger n)
    Greatest common divisor of the given two arguments.
    java.math.BigInteger gcd_euclid_withoutDivision​(java.math.BigInteger m, java.math.BigInteger n)  
    static java.math.BigInteger lcm​(java.math.BigInteger[] arguments)
    Least common multiple of k arguments n1, n2, ..., nk.
    static java.math.BigInteger lcm​(java.math.BigInteger a, java.math.BigInteger b)
    Least common multiple of two arguments.
    static java.math.BigInteger lcm​(java.util.Collection<java.math.BigInteger> arguments)
    Least common multiple of k arguments n1, n2, ..., nk.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • Gcd

      public Gcd()
  • Method Details

    • gcd_euclid_withDivision

      public java.math.BigInteger gcd_euclid_withDivision​(java.math.BigInteger m, java.math.BigInteger n)
      Greatest common divisor of the given two arguments. Euclid's algorithm implementation with division.
      Parameters:
      m -
      n -
      Returns:
      gcd(m, n)
    • gcd_euclid_withoutDivision

      public java.math.BigInteger gcd_euclid_withoutDivision​(java.math.BigInteger m, java.math.BigInteger n)
    • gcd_binary1

      public java.math.BigInteger gcd_binary1​(java.math.BigInteger m, java.math.BigInteger n)
      Binary gcd implementation.
      Parameters:
      m -
      n -
      Returns:
      gcd(m, n)
    • gcd

      public java.math.BigInteger gcd​(java.math.BigInteger a, java.math.BigInteger b)
      Slightly faster binary gcd adapted from OpenJdk's MutableBigInteger.binaryGcd(int, int). The BigInteger.gcd() implementation is still much faster.
      Parameters:
      a -
      b -
      Returns:
      gcd(a, b)
    • gcd

      public static java.math.BigInteger gcd​(java.util.Collection<java.math.BigInteger> arguments)
      GCD of k arguments n1, n2, ..., nk.
      Parameters:
      arguments - Collection of arguments
      Returns:
      GCD(n1, n2, ..., nk)
    • gcd

      public static java.math.BigInteger gcd​(java.math.BigInteger[] arguments)
      GCD of k arguments n1, n2, ..., nk.
      Parameters:
      arguments - array of arguments
      Returns:
      GCD(n1, n2, ..., nk)
    • lcm

      public static java.math.BigInteger lcm​(java.math.BigInteger a, java.math.BigInteger b)
      Least common multiple of two arguments.
      Parameters:
      a -
      b -
      Returns:
      LCM(a, b)
    • lcm

      public static java.math.BigInteger lcm​(java.util.Collection<java.math.BigInteger> arguments)
      Least common multiple of k arguments n1, n2, ..., nk.
      Parameters:
      arguments - Collection of arguments
      Returns:
      LCM(n1, n2, ..., nk)
    • lcm

      public static java.math.BigInteger lcm​(java.math.BigInteger[] arguments)
      Least common multiple of k arguments n1, n2, ..., nk.
      Parameters:
      arguments - array of arguments
      Returns:
      LCM(n1, n2, ..., nk)