c4e_mpvec.h File Reference

(Version 579)

Multi-precision arithmetic on digit vectors. More...

#include "c4e_sys.h"

Include dependency graph for c4e_mpvec.h:

Defines
#define	C4E_MPVEC_DIGIT_MAC(a, b, y, carry)
	Multiplication of two digits `a` and `b`, followed by addition to `y` (multiply-accumulate). The result in `y` is modulo C4E_SYS_DIGIT_MAX + 1, the overflow bits are returned in `carry`.
Functions
C4eArchDigit	c4e_mpvec_add (C4E_CONST C4eArchDigit pa, C4E_CONST C4eArchDigit pb, C4eArchIdx len, C4eArchDigit *py)
	Addition of two vectors `pa`[], `pb`[] of digits, with carry propagation.
C4eArchDigit	c4e_mpvec_cyadd (C4eArchDigit carry, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Carry propagation (by addition) on a source vector of digits, with result copied to a destination vector.
C4eArchDigit	c4e_mpvec_cyacc (C4eArchDigit carry, C4eArchIdx len, C4eArchDigit *pxy)
	In-place carry propagation (accumulator mode) on a vector of digits.
C4eArchDigit	c4e_mpvec_sub (C4E_CONST C4eArchDigit pa, C4E_CONST C4eArchDigit pb, C4eArchIdx len, C4eArchDigit *py)
	Subtraction of two vectors `pa`[], `pb`[] of digits, with borrow propagation.
C4eArchDigit	c4e_mpvec_cysub (C4eArchDigit borrow, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Borrow propagation (by subtraction) on a source vector of digits, with result copied to a destination vector.
C4eArchDigit	c4e_mpvec_cpl (C4eArchDigit borrow, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Two's complement conversion of a source vector of digits, with result copied to a destination vector.
C4eArchDigit	c4e_mpvec_muladd (C4eArchDigit digit, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Multiplication of a source vector `px`[] of digits with a single digit (inclusive carry propagation), with result added to a destination vector `py`[].
C4eArchDigit	c4e_mpvec_dblmuladd (C4eArchDigit digit, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Multiplication of a source vector `px`[] of digits by another digit, multiplied by two (incl. carry propagation), with result added to a destination vector `py`[].
C4eArchDigit	c4e_mpvec_mulsub (C4eArchDigit digit, C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Multiplication of a source vector `px`[] of digits with a single digit (inclusive borrow propagation), with result subtracted from a destination vector `py`[].
C4eArchDigit	c4e_mpvec_sqr (C4E_CONST C4eArchDigit px, C4eArchIdx len, C4eArchDigit py)
	Squaring each digit in a source vector `px`[] (inclusive carry propagation), with result added to a destination vector `py`[], means: $y := y + \sum_{i=0}^{n-1} x_i^2 B^{2 i}$ .

Detailed Description

Multi-precision arithmetic on digit vectors.

Author:: Copyright (C) 2007-2015 Ralf Hoppe <ralf.hoppe@ieee.org>

Version:

Id: c4e_mpvec.h 579 2015-05-24 18:00:40Z ralf

Definition in file c4e_mpvec.h.

Define Documentation

#define C4E_MPVEC_DIGIT_MAC	(	a,
		b,
		y,
		carry	)

Multiplication of two digits a and b, followed by addition to y (multiply-accumulate). The result in y is modulo C4E_SYS_DIGIT_MAX + 1, the overflow bits are returned in carry.

Parameters:

`[in]`	a	First factor of type C4eArchDigit.
`[in]`	b	Second factor of type C4eArchDigit.
`[out]`	carry	Return carry (overflow digit).
`[in,out]`	y	Result digit `y` += `a` * `b` mod C4E_SYS_DIGIT_MAX + 1, of type C4eArchDigit.

Definition at line 50 of file c4e_mpvec.h.

Function Documentation

C4eArchDigit c4e_mpvec_add	(	C4E_CONST C4eArchDigit *	pa,
		C4E_CONST C4eArchDigit *	pb,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Addition of two vectors pa[], pb[] of digits, with carry propagation.

Note:: It is allowed to set py pointing to pa or pb (accumulator mode).

Precondition:: py must point to pre-allocated memory of size len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	pa	Pointer to first vector of digits.
`[in]`	pb	Pointer to second vector of digits.
`[in]`	len	Number of elements in vectors `pa`[], `pb`[] and `py`[].
`[out]`	py	Result of `py`[] = `pa`[] + `pb`[], with the last carry returned by this function.

Returns:: Carry of last addition.

C4eArchDigit c4e_mpvec_cyadd	(	C4eArchDigit	carry,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Carry propagation (by addition) on a source vector of digits, with result copied to a destination vector.

Note:: It is allowed to set py pointing to px (accumulator mode). But notice, the carry propagation does not stop before len digits are processed. So it may be preferable to use function c4e_mpvec_cyacc().

Precondition:: py must point to pre-allocated memory of size len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	carry	Initial value for carry propagation.
`[in]`	px	Pointer to source vector of digits.
`[in]`	len	Number of elements in vectors `px`[] and `py`[].
`[out]`	py	Result of `py`[] = `px`[] + `carry`, with the last carry returned by this function.

Returns:: Carry of last propagation

C4eArchDigit c4e_mpvec_cyacc	(	C4eArchDigit	carry,
		C4eArchIdx	len,
		C4eArchDigit *	pxy
	)

In-place carry propagation (accumulator mode) on a vector of digits.

Note:: Carry propagation stops as early as possible. So possibly not all higher order digits of pxy[] are (re-) written.

Parameters:

`[in]`	carry	Initial value for carry propagation.
`[in]`	len	Number of elements in vector `pxy`[].
`[in,out]`	pxy	Result of `pxy`[] = `pxy`[] + `carry`, with the last carry returned by this function.

Returns:: Carry of last propagation.

C4eArchDigit c4e_mpvec_sub	(	C4E_CONST C4eArchDigit *	pa,
		C4E_CONST C4eArchDigit *	pb,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Subtraction of two vectors pa[], pb[] of digits, with borrow propagation.

Note:: It is allowed to set py pointing to pa or pb (accumulator mode).

Precondition:: py must point to pre-allocated memory of size len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	pa	Pointer to first vector of digits (minuend).
`[in]`	pb	Pointer to second vector of digits (subtrahend).
`[in]`	len	Number of elements in vectors `pa`[], `pb`[] and `py`[].
`[out]`	py	Result of `py`[] = `pa`[] - `pb`[], with the last borrow returned by this function.

Returns:: Borrow of last subtraction (unequal to C4E_SYS_DIGIT_ZERO if the result would be negative, means pa[] < pb[])

C4eArchDigit c4e_mpvec_cysub	(	C4eArchDigit	borrow,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Borrow propagation (by subtraction) on a source vector of digits, with result copied to a destination vector.

Note:: It is allowed to set py pointing to px (accumulator mode).

Precondition:: py must point to pre-allocated memory of size len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	borrow	Initial value for borrow propagation.
`[in]`	px	Pointer to source vector of digits.
`[in]`	len	Number of elements in vectors `px`[] and `py`[].
`[out]`	py	Result of `py`[] = `px`[] - `borrow`, with the last borrow returned by this function.

Returns:: Borrow of last propagation (unequal to C4E_SYS_DIGIT_ZERO if the result would be negative, means px[] < borrow).

C4eArchDigit c4e_mpvec_cpl	(	C4eArchDigit	borrow,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Two's complement conversion of a source vector of digits, with result copied to a destination vector.

Note:: It is allowed to set py pointing to px (accumulator mode).

Precondition:: py must point to pre-allocated memory of size len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	borrow	Initial value for borrow propagation.
`[in]`	px	Pointer to source vector of digits.
`[in]`	len	Number of elements in vectors `px`[] and `py`[].
`[out]`	py	Result of `py`[] = 0 - (`px`[] + `borrow`).

Returns:: Borrow of last digit complement.

C4eArchDigit c4e_mpvec_muladd	(	C4eArchDigit	digit,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Multiplication of a source vector px[] of digits with a single digit (inclusive carry propagation), with result added to a destination vector py[].

Parameters:

`[in]`	digit	Digit to be multiplied with each element of `px`[].
`[in]`	px	Source vector (each element multiplied with `digit`, then added to `py`[]).
`[in]`	len	Number of elements in vectors `px`[] and `py`[].
`[in,out]`	py	Result of `py`[] += `px`[] * `digit`, with the last carry returned by this function.

Returns:: Carry of last propagation.

C4eArchDigit c4e_mpvec_dblmuladd	(	C4eArchDigit	digit,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Multiplication of a source vector px[] of digits by another digit, multiplied by two (incl. carry propagation), with result added to a destination vector py[].

Parameters:

`[in]`	digit	Digit to be multiplied with two and each element of `px`[].
`[in]`	px	Source vector of length `len`.
`[in]`	len	Number of elements in vectors `px`[]. The number of elements in `py`[] must be `len` + 1.
`[in,out]`	py	Result of `py`[] += `px`[] * `digit` * 2, of length `len` + 1.

Returns:: Carry of last propagation.

See also:: c4e_mpvec_muladd()

C4eArchDigit c4e_mpvec_mulsub	(	C4eArchDigit	digit,
		C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Multiplication of a source vector px[] of digits with a single digit (inclusive borrow propagation), with result subtracted from a destination vector py[].

Parameters:

`[in]`	digit	Digit to be multiplied with each element of `px`[].
`[in]`	px	Source vector (each element multiplied with `digit`, then subtracted from `py`[]).
`[in]`	len	Number of elements in vectors `px`[] and `py`[].
`[in,out]`	py	Result of `py`[] -= `px`[] * `digit`, with the last borrow returned by this function.

Returns:: Borrow of last propagation (unequal to C4E_SYS_DIGIT_ZERO if the result would be negative, means py[] < px[])

C4eArchDigit c4e_mpvec_sqr	(	C4E_CONST C4eArchDigit *	px,
		C4eArchIdx	len,
		C4eArchDigit *	py
	)

Squaring each digit in a source vector px[] (inclusive carry propagation), with result added to a destination vector py[], means: $y := y + \sum_{i=0}^{n-1} x_i^2 B^{2 i}$ .

Precondition:: py must point to pre-allocated memory of size 2U * len * C4E_ARCH_DIGIT_SIZE.

Parameters:

`[in]`	px	Source vector (each element squared, then added to `py`[]).
`[in]`	len	Number of elements in vector `px`[].
`[in,out]`	py	Result of `py`[] += `px`[] * `px`[], with the last carry returned by this function.

Returns:: Carry of last propagation.

c4e_mpvec.h File Reference

(Version 579)

Defines

Functions

Detailed Description

Define Documentation

Function Documentation