ewe.math
Class MPN

java.lang.Object
  ewe.math.MPN

All Implemented Interfaces:

ByteEncodable

public class MPN

extends Object

implements ByteEncodable

This contains various low-level routines for unsigned bigints. The interfaces match the mpn interfaces in gmp, so it should be easy to replace them with fast native functions that are trivial wrappers around the mpn_ functions in gmp (at least on platforms that use 32-bit "limbs").

Field Summary

int	length
int[]	words

Constructor Summary

MPN()

MPN(byte[] encodedBytes, int offset, int length)

MPN(int numWords)

Method Summary

static int	add_1(int[] dest, int[] x, int size, int y) Add x[0:size-1] and y, and write the size least significant words of the result to dest.
static int	add_n(int[] dest, int[] x, int[] y, int len) Add x[0:len-1] and y[0:len-1] and write the len least significant words of the result to dest[0:len-1].
static int	chars_per_word(int radix) Number of digits in the conversion base that always fits in a word.
static int	cmp(int[] x, int[] y, int size) Compare x[0:size-1] with y[0:size-1], treating them as unsigned integers.
static int	cmp(int[] x, int xlen, int[] y, int ylen) Compare x[0:xlen-1] with y[0:ylen-1], treating them as unsigned integers.
int	compareTo(int value)
int	compareTo(long value)
int	compareTo(MPN other)
static int	count_leading_zeros(int i) Count the number of leading zero bits in an int.
static void	divide(int[] zds, int nx, int[] y, int ny) Divide zds[0:nx] by y[0:ny-1].
void	divide(MPN denominator, MPN quotient, MPN remainder) Divide two integers, yielding quotient and remainder.
static int	divmod_1(int[] quotient, int[] dividend, int len, int divisor) Divide dividend[0:len-1] by (unsigned int)divisor.
int	encodeBytes(ByteArray dest) This requests the Object to encode itself as a stream of bytes which is appended to the destination ByteArray.
boolean	equals(int value)
boolean	equals(long value)
static int	findLowestBit(int word) Return least i such that word&(1<
static int	findLowestBit(int[] words) Return least i such that words & (1<
MPN	fromBigInteger(BigInteger bi)
static int	gcd(int[] x, int[] y, int len) Calculate Greatest Common Divisior of x[0:len-1] and y[0:len-1].
int	getInt()
long	getLong()
boolean	hasInt()
boolean	hasLong()
static int	intLength(int i)
static int	intLength(int[] words, int len) Calcaulte the Common Lisp "integer-length" function.
boolean	isOdd()
static int	lshift(int[] dest, int d_offset, int[] x, int len, int count)
static void	main(String[] args)
MPN	minimize()
MPN	mod(MPN m)
MPN	modPowPositive(MPN exponent, MPN m)
static int	mul_1(int[] dest, int[] x, int len, int y) Multiply x[0:len-1] by y, and write the len least significant words of the product to dest[0:len-1].
static void	mul(int[] dest, int[] x, int xlen, int[] y, int ylen) Multiply x[0:xlen-1] and y[0:ylen-1], and write the result to dest[0:xlen+ylen-1].
MPN	multiply(MPN y) Destructively multiply this number with y.
static long	rshift_long(int[] x, int len, int count) Return the long-truncated value of right shifting.
static int	rshift(int[] dest, int[] x, int x_start, int len, int count)
static void	rshift0(int[] dest, int[] x, int x_start, int len, int count)
static int	set_str(int[] dest, byte[] str, int str_len, int base)
MPN	set(BigInteger other)
MPN	set(int value)
MPN	set(int[] data, int offset, int length)
MPN	set(long value)
MPN	set(MPN other)
static MPN	set(MPN source, MPN dest)
MPN	shiftLeft(int count) Destructively shift this MPN to the left by count bits.
MPN	shiftRight(int count) Destructively shift this MPN to the right by count bits.
int	signum() This returns -1 if the value is negative, +1 if it is positive, 0 if it is zero.
static int	sub_n(int[] dest, int[] X, int[] Y, int size) Subtract Y[0:size-1] from X[0:size-1], and write the size least significant words of the result to dest[0:size-1].
static int	submul_1(int[] dest, int offset, int[] x, int len, int y)
BigInteger	toBigInteger()
MPN	toNegative() Multiply this MPN by -1 and return this.
String	toString() Return a String representation of this object.
String	toString(int radix)
static long	udiv_qrnnd(long N, int D)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode

Field Detail

words

public int[] words

length

public int length

Constructor Detail

MPN

public MPN(byte[] encodedBytes,
           int offset,
           int length)
    throws StreamCorruptedException

MPN

public MPN()

MPN

public MPN(int numWords)

Method Detail

encodeBytes

public int encodeBytes(ByteArray dest)

Description copied from interface: ByteEncodable

This requests the Object to encode itself as a stream of bytes which is appended to the destination ByteArray. If the destination ByteArray is null, then the object should report how many bytes would be used if the object was encoded.

Specified by:

encodeBytes in interface ByteEncodable

Parameters:

dest - The destination ByteArray, or null to determine the number of bytes needed to encode.

Returns:

The number of bytes appended to the ByteArray or the number of bytes needed to encode.

fromBigInteger

public MPN fromBigInteger(BigInteger bi)

toBigInteger

public BigInteger toBigInteger()

minimize

public MPN minimize()

toString

public String toString(int radix)

toString

public String toString()

Description copied from class: Object

Return a String representation of this object.

Overrides:

toString in class Object

Returns:

a String representing this object.

signum

public int signum()

This returns -1 if the value is negative, +1 if it is positive, 0 if it is zero.

isOdd

public boolean isOdd()

set

public MPN set(int[] data,
               int offset,
               int length)

set

public static MPN set(MPN source,
                      MPN dest)

set

public MPN set(BigInteger other)

set

public MPN set(MPN other)

set

public MPN set(int value)

set

public MPN set(long value)

shiftRight

public MPN shiftRight(int count)

Destructively shift this MPN to the right by count bits.

Parameters:

count - the number of bits to shift.

Returns:

itself after being shifted.

shiftLeft

public MPN shiftLeft(int count)

Destructively shift this MPN to the left by count bits.

Parameters:

count - the number of bits to shift.

Returns:

itself after being shifted.

multiply

public MPN multiply(MPN y)

Destructively multiply this number with y.

Parameters:

y - the number to multiply by.

Returns:

this number, holding the result of the multiplication.

divide

public void divide(MPN denominator,
                   MPN quotient,
                   MPN remainder)

Divide two integers, yielding quotient and remainder.

Parameters:

quotient - is set to the quotient of the result (iff quotient!=null)

remainder - is set to the remainder of the result (iff remainder!=null)

mod

public MPN mod(MPN m)

modPowPositive

public MPN modPowPositive(MPN exponent,
                          MPN m)

equals

public boolean equals(int value)

equals

public boolean equals(long value)

compareTo

public int compareTo(int value)

compareTo

public int compareTo(long value)

compareTo

public int compareTo(MPN other)

hasInt

public boolean hasInt()

hasLong

public boolean hasLong()

getInt

public int getInt()
           throws IllegalStateException

Throws:

IllegalStateException

getLong

public long getLong()
             throws IllegalStateException

Throws:

IllegalStateException

toNegative

public MPN toNegative()

Multiply this MPN by -1 and return this.

add_1

public static int add_1(int[] dest,
                        int[] x,
                        int size,
                        int y)

Add x[0:size-1] and y, and write the size least significant words of the result to dest. Return carry, either 0 or 1. All values are unsigned. This is basically the same as gmp's mpn_add_1.

add_n

public static int add_n(int[] dest,
                        int[] x,
                        int[] y,
                        int len)

Add x[0:len-1] and y[0:len-1] and write the len least significant words of the result to dest[0:len-1]. All words are treated as unsigned.

Returns:

the carry, either 0 or 1 This function is basically the same as gmp's mpn_add_n.

sub_n

public static int sub_n(int[] dest,
                        int[] X,
                        int[] Y,
                        int size)

Subtract Y[0:size-1] from X[0:size-1], and write the size least significant words of the result to dest[0:size-1]. Return borrow, either 0 or 1. This is basically the same as gmp's mpn_sub_n function.

mul_1

public static int mul_1(int[] dest,
                        int[] x,
                        int len,
                        int y)

Multiply x[0:len-1] by y, and write the len least significant words of the product to dest[0:len-1]. Return the most significant word of the product. All values are treated as if they were unsigned (i.e. masked with 0xffffffffL). OK if dest==x (not sure if this is guaranteed for mpn_mul_1). This function is basically the same as gmp's mpn_mul_1.

mul

public static void mul(int[] dest,
                       int[] x,
                       int xlen,
                       int[] y,
                       int ylen)

Multiply x[0:xlen-1] and y[0:ylen-1], and write the result to dest[0:xlen+ylen-1]. The destination has to have space for xlen+ylen words, even if the result might be one limb smaller. This function requires that xlen >= ylen. The destination must be distinct from either input operands. All operands are unsigned. This function is basically the same gmp's mpn_mul.

udiv_qrnnd

public static long udiv_qrnnd(long N,
                              int D)

divmod_1

public static int divmod_1(int[] quotient,
                           int[] dividend,
                           int len,
                           int divisor)

Divide dividend[0:len-1] by (unsigned int)divisor. Write result into quotient[0:len-1. Return the one-word (unsigned) remainder. OK for quotient==dividend.

submul_1

public static int submul_1(int[] dest,
                           int offset,
                           int[] x,
                           int len,
                           int y)

divide

public static void divide(int[] zds,
                          int nx,
                          int[] y,
                          int ny)

Divide zds[0:nx] by y[0:ny-1]. The remainder ends up in zds[0:ny-1]. The quotient ends up in zds[ny:nx]. Assumes: nx>ny. (int)y[ny-1] < 0 (i.e. most significant bit set)

chars_per_word

public static int chars_per_word(int radix)

Number of digits in the conversion base that always fits in a word. For example, for base 10 this is 9, since 10**9 is the largest number that fits into a words (assuming 32-bit words). This is the same as gmp's __mp_bases[radix].chars_per_limb.

Parameters:

radix - the base

Returns:

number of digits

count_leading_zeros

public static int count_leading_zeros(int i)

Count the number of leading zero bits in an int.

set_str

public static int set_str(int[] dest,
                          byte[] str,
                          int str_len,
                          int base)

cmp

public static int cmp(int[] x,
                      int[] y,
                      int size)

Compare x[0:size-1] with y[0:size-1], treating them as unsigned integers.

cmp

public static int cmp(int[] x,
                      int xlen,
                      int[] y,
                      int ylen)

Compare x[0:xlen-1] with y[0:ylen-1], treating them as unsigned integers.

rshift

public static int rshift(int[] dest,
                         int[] x,
                         int x_start,
                         int len,
                         int count)

rshift0

public static void rshift0(int[] dest,
                           int[] x,
                           int x_start,
                           int len,
                           int count)

rshift_long

public static long rshift_long(int[] x,
                               int len,
                               int count)

Return the long-truncated value of right shifting.

Parameters:

x - a two's-complement "bignum"

len - the number of significant words in x

count - the shift count

Returns:

(long)(x[0..len-1] >> count).

lshift

public static int lshift(int[] dest,
                         int d_offset,
                         int[] x,
                         int len,
                         int count)

findLowestBit

public static int findLowestBit(int word)

Return least i such that word&(1<

findLowestBit

public static int findLowestBit(int[] words)

Return least i such that words & (1<

gcd

public static int gcd(int[] x,
                      int[] y,
                      int len)

Calculate Greatest Common Divisior of x[0:len-1] and y[0:len-1]. Assumes both arguments are non-zero. Leaves result in x, and returns len of result. Also destroys y (actually sets it to a copy of the result).

intLength

public static int intLength(int i)

intLength

public static int intLength(int[] words,
                            int len)

Calcaulte the Common Lisp "integer-length" function. Assumes input is canonicalized: len==BigInteger.wordsNeeded(words,len)

main

public static void main(String[] args)