On Sun, Apr 03, 2016 at 08:47:13PM +0100, Bob W-PDML wrote:
> >
> > also tried to dig into his multiplication algorithm, but became impatient
Back in the days when it was invented (in 1950), binary multiplication was done
by shifting and adding. Shifting was fast, but adding took significantly
longer.
This meant that. to a first-order approximation, the time to multiply by a
number
was directly proportional to the number of '1' bits in the binary representation
of that number.
Booth's algorithm attempts to speed the multiplication process up by reducing
the
number of addition steps needed. It does this by looking for a string of '1'
bits
anywhere in the number and handling all of them in two addition steps. To take a
very simple example, if it found a string of four '1' bits somewhere in the
number
('1111', in binary, represents the number 15) it would, instead, treat this as
if
it were "16 - 1"; the "-1" is handled by adding the negative value of the number
being multiplied, and the 16 is handled a little later on by one further
addition.
(16 is a power of two, so only has a single '1' bit in its binary
representation)
The actual implementation is rather clever, and is again designed for the
hardware
of the day (where fast register storage was the most expensive part of a
computer);
it uses the same shift register to hold the multiplier and the eventual product,
can produce a double-length product using ony a single-length adder, and only
has
to look at the two low-order bits of the shift register to decide whether to add
the positive or negative representation of the multiplicand, or to do nothing.
(If you want even more details, there's a fairly good Wikipedia article).
--
PDML Pentax-Discuss Mail List
[email protected]
http://pdml.net/mailman/listinfo/pdml_pdml.net
to UNSUBSCRIBE from the PDML, please visit the link directly above and follow
the directions.
