> On 04 April 2016 at 18:28 John Francis <[email protected]> wrote: > > > 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).
I thiink I just lost the will to live. -- 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.
