Information Technology Reference
In-Depth Information
2.33 Construct a circuit for the division of two
n
-bit binary numbers from circuits for the
reciprocal function
f
(
n
)
recip
and the integer multiplication function
f
(
n
)
mult
. Determine
the size and depth of this circuit and the accuracy of the result.
2.34 Let
f
:
n
kn
be an integer power of
x
;thatis,
f
(
x
)=
x
k
B
→B
for some integer
k
.
Show that such functions contain the shifting function
f
(
m
)
shift
as a subfunction for some
integer
m
. Determine
m
dependent on
n
and
k
.
x
q/
2
k
n
n
be a fractional power of
x
of the form
f
(
x
)=
2.35 Let
f
:
B
→B
,0
<
<
log
2
n
. Show that this function contains the shifting function
f
(
m
)
q<
2
k
shift
as a
subfunction. Find the largest value of
m
for which this holds.
Chapter Notes
Logic circuits have a long history. Early in the nineteenth century Babbage designed me-
chanical computers capable of logic operations. In the twentieth century logic circuits, called
switching circuits, were constructed of electromechanical relays. The earliest formal analysis of
logic circuits is attributed to Claude Shannon [
306
]; he applied Boolean algebra to the analysis
of logic circuits, the topic of Section
2.2
. Reduction between problems, a technique central
to computer science, is encountered whenever one uses an existing program to solve a new
problem by pre-processing inputs and post-processing outputs. Reductions also provide a way
to identify problems with similar complexity, an idea given great importance by the work of
Cook [
74
], Karp [159], and Levin [
199
]on
NP
-completeness. (See also [
335
].) This topic is
explored in depth in Chapter
8
.
The upper bound on the size of ripple adder described in Section
2.7
cannot be improved,
as shown by Red'kin [
276
] using the gate elimination method of Section
9.3.2
. Prefix compu-
tations, the subject of Section
2.6
,werefirstusedbyOfman[
234
]. He constructed the adder
based on carry-lookahead addition described in Section
2.7
.Krapchenko[
173
]andBrent
[
57
] developed adders with linear size whose depth is
+
O
(
log
n
log
n
)
, asymptotically
log
n
almost as good at the best possible depth bound of
.
Ofman used carry-save addition for fast integer multiplication [
234
]. Wallace indepen-
dently discovered carry-save addition and logarithmic depth circuits for addition and multipli-
cation [
356
]. The divide-and-conquer integer multiplication algorithm of Section
2.9.2
is due
to Karatsuba [
155
]. As mentioned at the end of Section
2.9
,Schonhage and Strassen [
303
]
have designed binary integer multipliers of depth
O
(log
n
)
whose size is
O
(
n
log
n
log log
n
)
.
Sir Isaac Newton around 1665 invented the iterative method bearing his name used in
Section
2.10
for binary integer division. Our treatment of this idea follows that given by Tate
[
325
]. Reif and Tate [
278
] have shown that binary integer division can be done with circuit
size
O
(
n
log
n
log log
n
)
and depth
O
(log
n
log log
n
)
using circuits whose description is log-
space uniform. Beame, Cook, and Hoover [
33
] have given an
O
(log
n
)
-depth circuit for the
reciprocal function, the best possible depth bound up to a constant multiple, but one whose
size is polynomial in
n
and whose description is not uniform; it requires knowledge of about
n
2
/
log
n
primes.
The key result in Section
2.11
on symmetric functions is due to Muller and Preparata
[
226
]. As indicated, it is the basis for showing that every one-output symmetric function can
be realized by a circuit whose size and depth are linear and logarithmic, respectively.
Search WWH ::
Custom Search