Java Reference
In-Depth Information
SORTING:
Integer Array A
Transform 1
Integers
Integer
0 to n−1
Array A
PAIRING
Array of Pairs
Transform 2
Sorted
Integer Array
Figure17.3
A reduction of SORTING to PAIRING shown as a “blackbox”
diagram.
is multiplied against each digit of the second, this algorithm requires (n
2
) time.
Asymptotically faster (but more complicated) algorithms are known, but none is so
fast as to be in O(n).
Next we ask the question: Is squaring an n-digit number as difficult as multi-
plying two n-digit numbers? We might hope that something about this special case
will allow for a faster algorithm than is required by the more general multiplication
problem. However, a simple reduction proof serves to show that squaring is “as
hard” as multiplying.
The key to the reduction is the following formula:
(X + Y )
2
(X Y )
2
4
X Y =
:
The significance of this formula is that it allows us to convert an arbitrary instance
of multiplication to a series of operations involving three addition/subtractions
(each of which can be done in linear time), two squarings, and a division by 4.
Note that the division by 4 can be done in linear time (simply convert to binary,
shift right by two digits, and convert back).
This reduction shows that if a linear time algorithm for squaring can be found,
it can be used to construct a linear time algorithm for multiplication.
