c4e_pstdiv.h File Reference

(Version 580)

Pope and Stein division algorithm subroutines More...

#include "c4e_elements.h"

Include dependency graph for c4e_pstdiv.h:

Go to the source code of this file.

Functions
C4eArchUint	c4e_pstdiv_start (C4eElement *C4E_RESTRICT a, C4eElement *C4E_RESTRICT b)
	Start of Pope and Stein division algorithm.
C4eArchDigit	c4e_pstdiv_step (C4eArchIdx step, C4E_CONST C4eElement *C4E_RESTRICT a, C4E_CONST C4eElement *C4E_RESTRICT b)
	One step of Pope and Stein division algorithm, determining a (next) quotient digit in .
void	c4e_pstdiv_stop (C4eArchUint shift, C4eElement *C4E_RESTRICT a, C4eElement *C4E_RESTRICT b)
	End of Pope and Stein division algorithm.

---

Detailed Description

Pope and Stein division algorithm subroutines

Author:

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

Version:

Id

c4e_pstdiv.h 580 2015-05-30 06:15:17Z ralf

Definition in file c4e_pstdiv.h.

---

Function Documentation

C4eArchUint c4e_pstdiv_start	(	C4eElement *C4E_RESTRICT	a,
		C4eElement *C4E_RESTRICT	b
	)

Start of Pope and Stein division algorithm.

Attention:

The divisor b is temporary modified in this function, but restored to it's original value in c4e_pstdiv_stop().

Precondition:

The numbers a and b must be normalized.

The size of a must be greater/equal than the size of b (else a itself is the remainder).

Postcondition:

At least call c4e_pstdiv_stop(), optionally do division(s) using c4e_pstdiv_step().

Parameters:

[in,out]	a	Dividend. There must be enough memory space in a->digits to hold a->size + 1 digits.
[in,out]	b	Divisor.

Returns:

Algorithm specific number, to be passed to c4e_pstdiv_stop().

See also:

c4e_pstdiv_stop(), C4eElement, C4E_ELEM_ASGN_MEM()

C4eArchDigit c4e_pstdiv_step	(	C4eArchIdx	step,
		C4E_CONST C4eElement *C4E_RESTRICT	a,
		C4E_CONST C4eElement *C4E_RESTRICT	b
	)

One step of Pope and Stein division algorithm, determining a (next) quotient digit in .

Precondition:

Call of c4e_pstdiv_start().

Note:

Parameter a can be declared as C4E_CONST because the structure it points to isn't modified. Instead only the digits in a->digits[] will change (and the double indirection prevents any const inheritance, at least when using "C").

Bibliography:

D. A. Pope and M. L. Stein: Multiple Precision Arithmetic. CACM, 3:652-654, 1960

Bibliography:

D. E. Knuth: The Art of Computer Programming, Vol. 2 (Semi-Numerical Algorithms). Addison-Wesley, 1997

Parameters:

[in]	step	Iteration step, from a->size - b->size (as size values were before the call to c4e_pstdiv_start()) down to 0. step corresponds to an offset in a->digits from which is subtracted.
[in,out]	a	Dividend digits as input, next remainder as output.
[in]	b	Divisor.

Returns:

Quotient digit in expression , satisfying the requirement, that the next digit of a vanishes. For an typical division application it is the next digit, to be stored at position step of digit vector q[].

See also:

c4e_pstdiv_start(), c4e_pstdiv_stop()

void c4e_pstdiv_stop	(	C4eArchUint	shift,
		C4eElement *C4E_RESTRICT	a,
		C4eElement *C4E_RESTRICT	b
	)

End of Pope and Stein division algorithm.

Precondition:

At least call c4e_pstdiv_start(), optionally followed by division using c4e_pstdiv_step().

Parameters:

[in]	shift	Algorithm specific number, returned from c4e_pstdiv_start()
[in,out]	a	Dividend
[in,out]	b	Divisor

See also:

c4e_pstdiv_start()