Information Technology Reference
In-Depth Information
10.5.2 Cyclic Shifting
The
cyclic shifting function
f
(
n
)
n
defined in Section
2.5.2
is a sub-
function of many functions, including integer multiplication and squaring (see Section
2.9.5
),
integer reciprocal (see Section
2.10.1
), and powers of integers (see Problems
2.34
and
2.35
).
Cyclic shifting is another good example of a problem for which a lower bound on the
exchange of space and time exists. The method used to establish the independence properties
of this function can be generalized to the class of transitive functions. (See Problem
10.22
.)
We redefine
f
(
n
)
n
+
log
n
cyclic
:
B
→B
. The input variables of
f
(
n
)
cyclic
are segmented
into two groups, an
n
-tuple
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
of
value variables
and a
k
-tuple
s
=
(
s
k−
1
,
...
,
s
1
,
s
0
)
of
control variables
. The control variables specify the integer
cyclic
here. Let
k
=
log
n
|
s
|
:
=
s
k−
1
2
k−
1
+
+
s
1
2
1
+
s
0
|
s
|
···
|
is the number of places by which the value inputs must be shifted left cyclically to produce
the output
n
-tuple
y
=(
y
n−
1
,
...
,
y
1
,
y
0
)
.Thatis,
f
(
n
)
s
|
cyclic
(
x
,
s
)=(
y
)
,where
y
j
=
x
(
j−|
s
|
)mod
n
≤
j
≤
log
n
−
for 0
1
(10.2)
A circuit to implement
f
(
n
)
cyclic
isgiveninSection
2.5.2
that cyclically shifts
x
left by 2
j
places
for each of those values of
j
,0
1, such that
s
j
=
1.
The independence properties of the cyclic function are shown by demonstrating that some
permutation of the input vector
x
aligns unselected inputs with selected outputs.
≤
j
≤
log
n
−
LEMMA
10.5.2
f
(
n
)
n
+
log
n
→B
n
cyclic
:
B
is
(
2,
n
+
log
n
,
n
,
n/
2
)
-independent.
Proof
Consider subsets
X
0
and
Y
1
of the inputs
X
and outputs
Y
of
f
(
n
)
satisfying
cyclic
=
p
=
n/
2. For
f
(
n
)
|
,
n
,
n/
2
)
-independent, there must
be an assignment to input variables in
X
0
such that the output variables in
Y
1
have more
than
X
0
|
+
|
Y
1
|
cyclic
to be
(
2,
n
+
log
n
1
distinct values as the input variables of
f
(
n
)
cyclic
|B|
(
|Y
1
|/
2
)
−
in
X
1
=
X
−
X
0
range
over all possible values.
Let
X
0
contain
e
elements from
x
.Let
y
i
∈
Y
1
.As
s
runs through all possible shift
values,
y
i
is made equal to every one of the inputs in
x
.For
n
−
e
of these shifts
y
i
is
set equal to an input in
X
1
=
X
−
X
0
.(Forexample, f
n
=
6and
e
=
2, say with
X
1
=
,thenas
s
ranges over all of its values, each
of the three
y
i
in
Y
1
is assigned four different variables in
X
1
.) Thus, the number of input
variables assigned to outputs, summed over all cyclic shifts, is
{
x
0
,
x
3
,
x
4
,
x
5
}
and
Y
1
=
{
y
2
,
y
3
,
y
5
}
e
)
.Sincethereare
n
cyclic shifts, for some shift the number of variables in
X
1
that are matched with outputs
in
Y
1
is at least the average of this quantity; that is, at least
|
Y
1
|
(
n
−
|
Y
1
|
(
1
−
e/n
)
≥|
Y
1
|
/
2. Thus,
/
2inputsin
X
1
to outputs in
Y
1
. Since these outputs can assume
|B|
|Y
1
|/
2
different values, it follows that
f
(
n
)
|
Y
1
|
some shift sets at least
cyclic
is
(
2,
n
+
log
n
,
n
,
n/
2
)
-independent.
THEOREM
10.5.2
Every pebbling strategy for straight-line programs computing the cyclic shifting
function
f
(
n
)
n
+
log
n
n
requires space
S
and time
T
satisfying the inequality
cyclic
:
B
→B
n
2
/
16
(
S
+
1
)
T
≥
Search WWH ::
Custom Search