Talk:Booth's multiplication algorithm
Here is a reference to Booth's paper:
A. D. Booth. A Signed Binary Multiplication Technique, Quarterly Journal of Mechanics and Applied Mathematics 4 (1951), 236--240.
This shows that Booth proposed his multiplication technique in 1951. The article gives a date of "around 1957".
U can get the pdf copy of the paper ("A Signed Binary Multiplication Technique")at the given URL:
Get it for better knowledge of Booth's Multiplier.
-Prasad Babu P (INDIA)
Booth actually has 2 algorithms. The first one was found to contain a flaw, so the second algorithm is the one that is now used and referenced in industry as Booth's Algorithm, since no one uses his original algorithm. - I suggest having both algorithms on this page(I shall do this if I have time). -source= class @ San Jose State University CS147
-Oliver Seet (USA) (student)
error in example
Please correct me if I'm wrong, but I think that there should be -4 × 3 instead of -6 × 2. Because 0011 is 3 (and 1101 is -3 in two's complement notation) and 1100 is -4 in two's complement notation. Of course, the product is the same. 184.108.40.206 11:20, 5 April 2007 (UTC)
- I think there still is an error in the example. The Length of A, S and P do not match the above definition. They have length 9 in the example, which is not equal to 3+4+1. —Preceding unsigned comment added by 220.127.116.11 (talk) 08:59, 5 May 2008 (UTC)
- The 9 bits refer to 4+4+1 (the number of bits x and y, not the values x and y). I have changed x and y to m and r, so hopefully there is less confusion. The whole description is confusing, but I only learned the algorithm a few minutes ago so I won't dare to fix it yet. :) Maghnus (talk) 21:19, 10 January 2009 (UTC)
- There is definitely an error in the example and maybe the description of the algorythm. It does not work out when using the correct 2's complement numbers. —Preceding unsigned comment added by 18.104.22.168 (talk) 22:30, 8 September 2009 (UTC)
Improved method that handles multiplication by the minimum negative number
The described method in the article can't handle multiplications like -128 x 1 (when using 8 bits). The problem arises from the fact that -128 is the minimum negative number when using 8 bits for representation. I have made a minor modification in the method and added one more example to show the improved technique. Hope that everything is OK. Prekageo 12:22, 15 August 2007 (UTC)
- What is the additional bit initialized to? Reinderien 04:37, 2 December 2007 (UTC)
- I added some clarification to that part, based on what I believe is a correct interpretation: the typical implementation states, "A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros." It seems to be the case that, should you add more bits to the front, you still fill all of them with the value of m--you're just filling more bits with the same value now, so the sign bit will be further out, and you'll have an extra '1' for each bit you add, to balance out the fact that the sign bit is now more significant. KoriganStone (talk) 20:19, 20 August 2014 (UTC)
Number of times to perform the loop
- Because in the example, x = 4 and y = 4.
no of step's decided by no. of bits used.for no. 0-9 we use 4 bit,for >9 we use 5 bit. so multiplyin <9 no. use 4 step else 5 step. —Preceding unsigned comment added by 22.214.171.124 (talk) 21:41, 7 May 2008 (UTC)
Motive of the algorithm is unclear
It is not clear to me why this algorithm is important. It does not seem to be an improvement over what one might do just by duplicating what I learned to do in multiplying decimal numbers by hand. Of course those are sign-and-magnitude numbers, but that can be dealt with by recognizing that in 2's complement numbers the high-order bit is a sign bit, and has the value of the most-negative number. Accordingly if that bit is on, it calls for subtraction rather than addition.
Following this idea, we get an algorithm that adds or subtracts once per 1-bit in the multiplier, shifts the same number of times as Booth's algorithm, and only has to examine one bit rather than pairs of bits. In software, this is perhaps easier (depending on the language). In hardware, I don't see much difference. Since this algorithm seems obscure, I'm wondering why it gets any attention.
Sorry to not cite references, but this is an extrapolation of what I learned in grade school. I'll add more advanced ones if it seems worth putting on the main page.
For unsigned case, it's simply increase that to 5 x 5 signed bit, so a 15 x 15 would work.
But keep in mind, if you are work on radix-4 or high order of design, let say a 8 x 8 in radix-4 method.
You are actually working on a 9 x 9 case instead, and the last cycle will be radix-2 only, yes that's odd.
So for a 64 x 64 => 65 x 65 case, the chose of radix-?? will be difficult.