
182
<: N,& {:, ~i ~ ~ g~ 4 Multiplication
o
This 2n-bit result is required because the range is
--(2n-1)(2 n-1 --
1) < p <
(--2n-1)(--2 n-l) -- 2 2n-2
4.4
so that the most positive value is represented by a vector of 2n bits.
IfxR, yR, and PR are the corresponding positive integer representa-
tions of x, y, and p, respectively, the high-level algorithm is
PR-
XRYR
22n -- (2 n --
XR)YR
22n --
XR( 2n -- YR)
(2 n
--XR)(2 n --YR)
ifx >0, y >0
if x < O, y > 0
if x > O, y < 0
if x < O, y < 0
4.5
As will be seen, this algorithm can be simplified when using the
corresponding digit-vectors.
In the next sections two types ...