Package de.tilman_neumann.jml.gcd
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)
-