"I mean, how hard is it to rearrange zeroes and ones all day?" http://dilbert.com/strip/2016-03-06
http://dilbert.com/strip/2010-04-24 > On 4 Apr 2016, at 18:29, 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). > > > -- > 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. -- 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.
