Information Technology Reference
In-Depth Information
u
2
n/
2
the invocation of
recip(
,n/2)
.Thatis,
C
recip
(
n
)
C
recip
(
n/
2
)+
cM
int
(
n
,
c
)
C
recip
(
1
)=
1
for some constant
c>
0. This inequality implies the following bound:
≤
M
int
n
2
j
,
c
log
n
log
n
1
2
j
C
recip
(
n
)
≤
c
≤
cM
int
(
n
,
c
)
j
=
0
j
=
0
=
O
(
M
int
(
n
,
c
))
which follows since
M
int
(
dn
,
c
)
≤
dM
int
(
n
,
c
)
when
d
≤
1.
The depth
D
recip
(
n
)
of the circuit produced by this algorithm is at most
c
log
n
plus the
depth
D
recip
(
n/
2
)
. Since the circuit has at most 1
+log
2
n
stages with a depth of at most
c
log
n
each,
D
recip
(
n
)
2
c
log
2
n
when
n
≤
≥
2.
THEOREM
2.10.1
If
n
=
2
k
, the reciprocal function
f
(
n
)
recip
n
n
+
2
:
B
→B
for
n
-bit binary
numbers can be realized by a circuit with the following size and depth:
C
Ω
f
(
n
)
recip
≤
O
(
M
int
(
n
,
c
))
D
Ω
f
(
n
)
recip
c
log
2
n
≤
VERY FAST RECIPROCAL
Beame, Cook, and Hoover [
33
] have given an
O
(log
n
)
circuit for
the reciprocal function. It uses a sequence of about
n
2
/
log
n
primes to represent an
n
-bit
binary number
x
,
.
5
x
<
1, using arithmetic modulo these primes. The size of the circuit
produced is polynomial in
n
, although much larger than
M
int
(
n
,
c
)
.ReifandTate[
325
]show
that the reciprocal function can be computed with a circuit that is defined only in terms of
n
and has a size proportional to
M
int
(and thus nearly optimal) and depth
O
(log
n
log log
n
)
.
Although the depth bound is not quite as good as that of Beame, Cook, and Hoover, its size
bound is very good.
≤
2.10.1 Reductions to the Reciprocal
In this section we show that the reciprocal function contains the squaring function as a sub-
function. It follows from Problem
2.33
and the preceding result that integer multiplication
and division have comparable circuit size. We use Taylor's theorem [
315
, p. 345] to establish
the desired result.
THEOREM
2.10.2
(Taylor)
Let
f
(
x
):
be a continuous real-valued function defined
on the interval
[
a
,
b
]
whose
k
th derivative is also continuous for
k
→
≤
n
+
1
overthesameinterval.
Then for
a
≤
x
0
≤
x
≤
b
,
f
(
x
)
can be expanded as
x
0
)
n
n
!
x
0
)
f
[
1
]
(
x
0
)+
(
x
−
x
0
)
2
2
+
(
x
−
f
[
2
]
(
x
0
)+
f
[
n
]
(
x
0
)+
r
n
f
(
x
)=
f
(
x
0
)+(
x
−
···
where
f
[
n
]
denotes the
n
th derivative of
f
and the remainder
r
n
satisfies
r
n
=
x
x
0
t
)
n
f
[
n
+
1
]
(
t
)
(
x
−
dt
n
!
Search WWH ::
Custom Search