Package de.tilman_neumann.jml.gcd

Class Gcd

java.lang.Object

de.tilman_neumann.jml.gcd.Gcd

public class Gcd
extends 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.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
Gcd()

Method Summary

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

Gcd

public Gcd()

Method Detail

gcd_euclid_withDivision

public BigInteger gcd_euclid_withDivision(BigInteger m,
                                          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 BigInteger gcd_euclid_withoutDivision(BigInteger m,
                                             BigInteger n)

gcd_binary1

public BigInteger gcd_binary1(BigInteger m,
                              BigInteger n)

Binary gcd implementation.

Parameters:

m -

n -

Returns:

gcd(m, n)

gcd

public BigInteger gcd(BigInteger a,
                      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 BigInteger gcd(Collection<BigInteger> arguments)

GCD of k arguments n1, n2, ..., nk.

Parameters:

arguments - Collection of arguments

Returns:

GCD(n1, n2, ..., nk)

gcd

public static BigInteger gcd(BigInteger[] arguments)

GCD of k arguments n1, n2, ..., nk.

Parameters:

arguments - array of arguments

Returns:

GCD(n1, n2, ..., nk)

lcm

public static BigInteger lcm(BigInteger a,
                             BigInteger b)

Least common multiple of two arguments.

Parameters:

a -

b -

Returns:

LCM(a, b)

lcm

public static BigInteger lcm(Collection<BigInteger> arguments)

Least common multiple of k arguments n1, n2, ..., nk.

Parameters:

arguments - Collection of arguments

Returns:

LCM(n1, n2, ..., nk)

lcm

public static BigInteger lcm(BigInteger[] arguments)

Least common multiple of k arguments n1, n2, ..., nk.

Parameters:

arguments - array of arguments

Returns:

LCM(n1, n2, ..., nk)