Bigint< L, Lhalf > Class Template Reference

Template for multiple-precision integer arithmetic. More...

#include <bigint.hh>

Public Types
enum	{ limb_bits = sizeof(limb_type) * 8 , half_limb_bits = sizeof(limb_type) * 4 }
enum	{ limb_high_bit = limb_type(1) << (limb_bits - 1) , limb_half = limb_type(1) << half_limb_bits , limb_low_mask = limb_half - 1 , limb_zero = limb_type(0) }
typedef L	limb_type
	Type of a limb, the unit of single arithmetic.
typedef Lhalf	half_limb_type
	Type of an arithmetic unit no smaller than one-half limb_type.

Static Public Member Functions
static half_limb_type	low (limb_type x)
	Return the less significant half of x.
static half_limb_type	high (limb_type x)
	Return the more significant half of x.
static void	add (limb_type &x1, limb_type &x0, limb_type a1, limb_type a0, limb_type b1, limb_type b0)
	Add two-limb integers [a1,a0] and [b1,b0], storing the result in [x1,x0].
static void	multiply (limb_type &x1, limb_type &x0, limb_type a, limb_type b)
	Multiply one-limb integers a and b, storing the result in [x1,x0].
static void	multiply_half (limb_type &x1, limb_type &x0, limb_type a, half_limb_type b)
	Multiply one-limb integer a by half-limb integer b, storing the result in [x1,x0].
static limb_type	inverse (limb_type x)
	Return the inverse of limb x.
static click_uintmax_t	set (limb_type *a, int n, click_uintmax_t b)
	Set n-limb integer a to the value b.
static limb_type	multiply_add (limb_type *x, const limb_type *a, int n, limb_type b)
	Multiply n-limb integer a by 1-limb integer b and add the result to n-limb integer x.
static limb_type	multiply (limb_type *x, const limb_type *a, int n, limb_type b, limb_type carry=0)
	Multiply n-limb integer a by 1-limb integer b, add 1-limb integer carry, and store the result in n-limb integer x.
static limb_type	multiply_half (limb_type *x, const limb_type *a, int n, half_limb_type b, limb_type carry=0)
	Multiply n-limb integer a by 1/2-limb integer b, add 1-limb integer carry, and store the result in n-limb integer x.
static limb_type	divide (limb_type *x, const limb_type *a, int n, limb_type b)
	Divide n-limb integer a by 1-limb integer b and store the result in n-limb integer x.
static String	unparse_clear (limb_type *x, int n, int base=10, bool uppercase=false)
	Return a string representation of n-limb integer x and set x to 0.

Detailed Description

template<typename L, typename Lhalf = L>
class Bigint< L, Lhalf >

Template for multiple-precision integer arithmetic.

The Bigint template provides a couple simple, but useful, functions for multiple-precision integer arithmetic. It is a port of a very limited subset of the GNU Multiple Precision Arithmetic library's mpn functionality (architecture-generic functions that work on unsigned integers of known size).

A multiple-precision integer is an array of "limbs," or machine integers. The multiply_add() and divide() functions take arrays of limbs as arguments. In such arrays, the least significant limb is stored at array index 0.

For example, here's Bigint speak for "x = 0x123_4567_89AB_CDEF * 0x45":

// Initialize result
uint32_t x[2] = { 0, 0 };
// Define multiplicand; note that least significant comes first
uint32_t a[2] = { 0x89ABCDEF, 0x1234567 };
Bigint<uint32_t>::multiply_add(x, a, 2, 0x45);

Bigint is not optimized for speed.

Bigint's template parameter is the type of a limb. Most users will use bigint, which is equivalent to Bigint<uint32_t>.

Member Typedef Documentation

limb_type

template<typename L , typename Lhalf = L>

typedef L Bigint< L, Lhalf >::limb_type

Type of a limb, the unit of single arithmetic.

half_limb_type

template<typename L , typename Lhalf = L>

typedef Lhalf Bigint< L, Lhalf >::half_limb_type

Type of an arithmetic unit no smaller than one-half limb_type.

Member Function Documentation

low()

template<typename L , typename Lhalf = L>

static half_limb_type Bigint< L, Lhalf >::low ( limb_type  x )

inlinestatic

Return the less significant half of x.

Invariant

low(x) + ((limb_type) high(x) << half_limb_bits) == x

high()

template<typename L , typename Lhalf = L>

static half_limb_type Bigint< L, Lhalf >::high ( limb_type  x )

inlinestatic

Return the more significant half of x.

add()

template<typename L , typename Lhalf = L>

static void Bigint< L, Lhalf >::add ( limb_type &  x1, limb_type &  x0, limb_type  a1, limb_type  a0, limb_type  b1, limb_type  b0  )

inlinestatic

Add two-limb integers [a1,a0] and [b1,b0], storing the result in [x1,x0].

Parameters

[out]	x1	most significant limb of result
[out]	x0	least significant limb of result
	a1	most significant limb of addend
	a0	least significant limb of addend
	b1	most significant limb of addend
	b0	least significant limb of addend

Handles carry in the low order limbs.

multiply() [1/2]

template<typename L , typename Lhalf = L>

static void Bigint< L, Lhalf >::multiply ( limb_type &  x1, limb_type &  x0, limb_type  a, limb_type  b  )

inlinestatic

Multiply one-limb integers a and b, storing the result in [x1,x0].

Parameters

[out]	x1	most significant limb of result
[out]	x0	least significant limb of result
	a	multiplicand
	b	multiplicand

multiply_half() [1/2]

template<typename L , typename Lhalf = L>

static void Bigint< L, Lhalf >::multiply_half ( limb_type &  x1, limb_type &  x0, limb_type  a, half_limb_type  b  )

inlinestatic

Multiply one-limb integer a by half-limb integer b, storing the result in [x1,x0].

Parameters

[out]	x1	most significant limb of result
[out]	x0	least significant limb of result
	a	multiplicand
	b	multiplicand

inverse()

template<typename L , typename Lhalf = L>

static limb_type Bigint< L, Lhalf >::inverse ( limb_type  x )

inlinestatic

Return the inverse of limb x.

Returns the limb y that is the largest limb not larger than (2**(2*limb_bits))/x - (2**limb_bits). If this would yield overflow, y is the largest possible number (i.e., only ones).

set()

template<typename L , typename Lhalf = L>

static click_uintmax_t Bigint< L, Lhalf >::set ( limb_type *  a, int  n, click_uintmax_t  b  )

inlinestatic

Set n-limb integer a to the value b.

Parameters

[out]	a	points to n-limb result
	n	number of limbs in a
	b	input value

Returns

carry

multiply_add()

template<typename L , typename Lhalf = L>

static limb_type Bigint< L, Lhalf >::multiply_add ( limb_type *  x, const limb_type *  a, int  n, limb_type  b  )

inlinestatic

Multiply n-limb integer a by 1-limb integer b and add the result to n-limb integer x.

Parameters

[in,out]	x	points to n-limb addend and result
	a	points to n-limb multiplicand
	n	number of limbs in x and a
	b	1-limb multiplicand

Returns

overflow

Like x += a * b. Both x and a must have n limbs. It is safe for x and a to point to exactly the same memory, but they must not otherwise overlap.

multiply() [2/2]

template<typename L , typename Lhalf = L>

static limb_type Bigint< L, Lhalf >::multiply ( limb_type *  x, const limb_type *  a, int  n, limb_type  b, limb_type  carry = 0  )

inlinestatic

Multiply n-limb integer a by 1-limb integer b, add 1-limb integer carry, and store the result in n-limb integer x.

Parameters

[in,out]	x	points to n-limb result
	a	points to n-limb multiplicand
	n	number of limbs in x and a
	b	1-limb multiplicand
	carry	1-limb initial carry

Returns

overflow

Like x = (a * b) + carry. Both x and a must have n limbs. It is safe for x and a to point to exactly the same memory, but they must not otherwise overlap.

multiply_half() [2/2]

template<typename L , typename Lhalf = L>

static limb_type Bigint< L, Lhalf >::multiply_half ( limb_type *  x, const limb_type *  a, int  n, half_limb_type  b, limb_type  carry = 0  )

inlinestatic

Multiply n-limb integer a by 1/2-limb integer b, add 1-limb integer carry, and store the result in n-limb integer x.

Parameters

[in,out]	x	points to n-limb result
	a	points to n-limb multiplicand
	n	number of limbs in x and a
	b	1/2-limb multiplicand
	carry	1-limb initial carry

Returns

overflow

Like x = (a * b) + carry. Both x and a must have n limbs. It is safe for x and a to point to exactly the same memory, but they must not otherwise overlap.

divide()

template<typename L , typename Lhalf = L>

static limb_type Bigint< L, Lhalf >::divide ( limb_type *  x, const limb_type *  a, int  n, limb_type  b  )

inlinestatic

Divide n-limb integer a by 1-limb integer b and store the result in n-limb integer x.

Parameters

[out]	x	points to n-limb result
	a	points to n-limb dividend
	n	number of limbs in x and a
	b	1-limb divisor

Returns

the remainder

Like x = a / b. Both x and a must have n limbs. It is safe for x and a to point to exactly the same memory, but they must not otherwise overlap.

unparse_clear()

template<typename L , typename Lhalf = L>

static String Bigint< L, Lhalf >::unparse_clear ( limb_type *  x, int  n, int  base = 10, bool  uppercase = false  )

inlinestatic

Return a string representation of n-limb integer x and set x to 0.

Parameters

[in,out]	x	n-limb input, set to zero on output
	n	number of limbs in x
	base	base (between 2 and 36)
	uppercase	if true, use uppercase letters for digits >= 10

---

The documentation for this class was generated from the following file:

• include/click/bigint.hh