Package de.tilman_neumann.jml.base

Class UnsignedBigInt

java.lang.Object

de.tilman_neumann.jml.base.UnsignedBigInt

public class UnsignedBigInt
extends Object

A very limited unsigned big integer implementation. Currently the only implemented arithmetic methods are division and modulus of big integers by small integers. These methods are notably faster than using BigInteger.divide(BigInteger), like factor 2.5 for BigIntegers with 100 bit, factor 1.8 at 200 bit, factor 1.6 at 300 bit.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
UnsignedBigInt(int[] buffer)	Constructor using the given buffer.
UnsignedBigInt(UnsignedBigInt N)	Copy constructor
UnsignedBigInt(BigInteger N)	Shortcut constructor for new UnsignedBigInt(); set(N);

Method Summary

Modifier and Type	Method	Description
int	bitLength()
int	divideAndRemainder(int divisor, UnsignedBigInt quotient)	Divide this by the given divisor, store the quotient in quotient and return the remainder.
int	divideAndRemainder_v1(int divisor, UnsignedBigInt quotient)	Deprecated.
boolean	equals(Object o)
int	hashCode()
int	intLength()
int	intValue()
boolean	isOne()	Test for 1.
boolean	isZero()	Test for 0.
long	longValue()
int	mod(int divisor)	Compute the remainder of this modulo divisor.
void	set(BigInteger N)	Sets this to the given BigInteger N.
BigInteger	toBigInteger()
String	toBinaryString()
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

UnsignedBigInt

public UnsignedBigInt(UnsignedBigInt N)

Copy constructor

Parameters:

N - original unsigned big int

UnsignedBigInt

public UnsignedBigInt(BigInteger N)

Shortcut constructor for new UnsignedBigInt(); set(N);

Parameters:

N -

UnsignedBigInt

public UnsignedBigInt(int[] buffer)

Constructor using the given buffer. The numbers to work on must be set using the set(BigInteger) method.

Parameters:

buffer - a buffer big enough to represent all numbers that will be set using set(BigInteger).

Method Detail

set

public void set(BigInteger N)

Sets this to the given BigInteger N. This method must be called before any arithmetic operation. If a buffer has been passed to the constructor then it should be big enough to represent N.

Parameters:

N -

isZero

public boolean isZero()

Test for 0. The caller must make sure that set(BigInteger) has been invoked before.

Returns:

true if this==0, false else

isOne

public boolean isOne()

Test for 1. The caller must make sure that set(BigInteger) has been invoked before.

Returns:

true if this==1, false else

intLength

public int intLength()

bitLength

public int bitLength()

divideAndRemainder_v1

@Deprecated
public int divideAndRemainder_v1(int divisor,
                                 UnsignedBigInt quotient)

Deprecated.

Divide this by the given divisor, store the quotient in quotient and return the remainder. The caller must make sure that set(BigInteger) has been invoked before.

Parameters:

divisor -

quotient - output

Returns:

remainder

divideAndRemainder

public int divideAndRemainder(int divisor,
                              UnsignedBigInt quotient)

Divide this by the given divisor, store the quotient in quotient and return the remainder. The caller must make sure that set(BigInteger) has been invoked before.

Parameters:

divisor -

quotient - output

Returns:

remainder

mod

public int mod(int divisor)

Compute the remainder of this modulo divisor. The caller must make sure that set(BigInteger) has been invoked before. This simple implementation seems to be amazingly fast, like 100 times faster than BigInteger.mod(d), where BigInteger d = BigInteger.valueOf(divisor) has been created before the performance test loop. Here, Barrett reduction has no chance to shine...

Parameters:

divisor -

Returns:

remainder

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

intValue

public int intValue()

longValue

public long longValue()

toBigInteger

public BigInteger toBigInteger()

toString

public String toString()

Overrides:

toString in class Object

toBinaryString

public String toBinaryString()