ch.javasoft.util.numeric
Class IntegerUtil

java.lang.Object
  ch.javasoft.util.numeric.IntegerUtil

public class IntegerUtil
extends Object

The IntegerUtil contains static utility methods concerning integers (int and long).

Method Summary

static int	bitCount(int value) count 1 bits in this int value
static int	bitCount(long value) count 1 bits in this long value
static int[]	extendedEuclidean(int a, int b) The extended euclidean algorithm solves the equation a*x + b*y = gcd(a,b).
static long[]	extendedEuclidean(long a, long b) The extended euclidean algorithm solves the equation a*x + b*y = gcd(a,b).
static int	gcd(int... values) Calculates the greatest common divisor of the specified integer numbers.
static int	gcd(Integer... values) Calculates the greatest common divisor of the specified integer numbers.
static int	gcd(int iA, int iB) Returns the greatest common divisor of iA and iB using standard euclidian algorithm
static long	gcd(long... values) Calculates the greatest common divisor of the specified long numbers.
static long	gcd(Long... values) Calculates the greatest common divisor of the specified long numbers.
static long	gcd(long iA, long iB) Returns the greatest common divisor of iA and iB using standard euclidian algorithm
static int	modularReciprocal(int a, int mod) Computes the reciprocal or multiplicative inverse of a (modulo mod).
static long	modularReciprocal(long a, long mod) Computes the reciprocal or multiplicative inverse of a (modulo mod).
static int	modularReciprocal2pow32(int a) Computes the reciprocal or multiplicative inverse of a (modulo 2^32).
static long	modularReciprocal2pow64(long a) Computes the reciprocal or multiplicative inverse of a (modulo 2^64).
static int	signum(int value) Returns the signum of the int value, i.e.
static int	signum(long value) Returns the signum of the long value, i.e.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

signum

public static int signum(long value)

Returns the signum of the long value, i.e. 1/-1/0 for a positive, negative or zero value

See Also:

Math.signum(double)

signum

public static int signum(int value)

Returns the signum of the int value, i.e. 1/-1/0 for a positive, negative or zero value

See Also:

Math.signum(double)

gcd

public static int gcd(Integer... values)

Calculates the greatest common divisor of the specified integer numbers. This method might be useful to scale down a vector of integer numbers.

If all numbers are negative, the resulting gcd is also negative. If all numbers are zero, the result is zero. Otherwise, the result is positive.

Parameters:

values - values for which the gcd is to be computed

Returns:

gcd of all values, negative if all values negative, zero if all values zero, positive otherwise

gcd

public static int gcd(int... values)

Calculates the greatest common divisor of the specified integer numbers. This method might be useful to scale down a vector of integer numbers.

If all numbers are negative, the resulting gcd is also negative. If all numbers are zero, the result is zero. Otherwise, the result is positive.

Parameters:

values - values for which the gcd is to be computed

Returns:

gcd of all values, negative if all values negative, zero if all values zero, positive otherwise

gcd

public static long gcd(Long... values)

Calculates the greatest common divisor of the specified long numbers. This method might be useful to scale down a vector of long numbers.

If all numbers are negative, the resulting gcd is also negative. If all numbers are zero, the result is zero. Otherwise, the result is positive.

Parameters:

values - values for which the gcd is to be computed

Returns:

gcd of all values, negative if all values negative, zero if all values zero, positive otherwise

gcd

public static long gcd(long... values)

Calculates the greatest common divisor of the specified long numbers. This method might be useful to scale down a vector of long numbers.

If all numbers are negative, the resulting gcd is also negative. If all numbers are zero, the result is zero. Otherwise, the result is positive.

Parameters:

values - values for which the gcd is to be computed

Returns:

gcd of all values, negative if all values negative, zero if all values zero, positive otherwise

gcd

public static int gcd(int iA,
                      int iB)

Returns the greatest common divisor of iA and iB using standard euclidian algorithm

extendedEuclidean

public static int[] extendedEuclidean(int a,
                                      int b)

The extended euclidean algorithm solves the equation a*x + b*y = gcd(a,b).

Returns an int array containing 3 elements {x, y, gcd(a, b)}.

modularReciprocal

public static int modularReciprocal(int a,
                                    int mod)

Computes the reciprocal or multiplicative inverse of a (modulo mod). Note that a is only invertible if a and mod are coprime. If this is not the case, an ArithmeticException is thrown.

The returned value inv(a) meets the following equality: inv(a) * a = 1 (modulo mod).

Returns:

the multiplicative inverse of a (modulo mod), if it exists, and throws an exception otherwise.

Throws:

ArithmeticException - if a is not invertible (modulo mod)

gcd

public static long gcd(long iA,
                       long iB)

Returns the greatest common divisor of iA and iB using standard euclidian algorithm

extendedEuclidean

public static long[] extendedEuclidean(long a,
                                       long b)

The extended euclidean algorithm solves the equation a*x + b*y = gcd(a,b).

Returns a long array containing 3 elements {x, y, gcd(a, b)}.

modularReciprocal

public static long modularReciprocal(long a,
                                     long mod)

Computes the reciprocal or multiplicative inverse of a (modulo mod). Note that a is only invertible if a and mod are coprime. If this is not the case, an ArithmeticException is thrown.

The returned value inv(a) meets the following equality: inv(a) * a = 1 (modulo mod).

Returns:

the multiplicative inverse of a (modulo mod), if it exists, and throws an exception otherwise.

Throws:

ArithmeticException - if a is not invertible (modulo mod)

modularReciprocal2pow32

public static int modularReciprocal2pow32(int a)

Computes the reciprocal or multiplicative inverse of a (modulo 2^32). Note that a is only invertible if a and 2^32 are coprime, that is, if a is odd. If this is not the case, an ArithmeticException is thrown.

The returned value inv(a) meets the following equality: inv(a) * a = 1 (modulo 2^32).

Returns:

the multiplicative inverse of a (modulo 2^32), if it exists (if a is odd), and throws an exception otherwise.

Throws:

ArithmeticException - if a is not invertible (modulo 2^32), that is, iv a is even

modularReciprocal2pow64

public static long modularReciprocal2pow64(long a)

Computes the reciprocal or multiplicative inverse of a (modulo 2^64). Note that a is only invertible if a and 2^64 are coprime, that is, if a is odd. If this is not the case, an ArithmeticException is thrown.

The returned value inv(a) meets the following equality: inv(a) * a = 1 (modulo 2^64).

Returns:

the multiplicative inverse of a (modulo 2^64), if it exists (if a is odd), and throws an exception otherwise.

Throws:

ArithmeticException - if a is not invertible (modulo 2^64), that is, iv a is even

bitCount

public static int bitCount(int value)

count 1 bits in this int value

bitCount

public static int bitCount(long value)

count 1 bits in this long value