Content deleted Content added
m r2.7.1) (Robot: Adding pt:Algoritmos de multiplicação |
change link |
||
Line 149:
In base 2, long multiplication reduces to a nearly trivial operation. For each '1' bit in the [[wikt:multiplier|multiplier]], shift the [[wikt:multiplicand|multiplicand]] an appropriate amount and then sum the shifted values. Depending on computer processor architecture and choice of multiplier, it may be faster to code this algorithm using hardware bit shifts and adds rather than depend on multiplication instructions, when the multiplier is fixed and the number of adds required is small.
This [[algorithm]] is also known as Peasant multiplication, because it has been widely used among those who are unschooled and thus have not memorized the [[multiplication
On paper, write down in one column the numbers you get when you repeatedly halve the multiplier, ignoring the remainder; in a column beside it repeatedly double the multiplicand. Cross out each row in which the last digit of the first number is even, and add the remaining numbers in the second column to obtain the product.
Line 271:
}}</ref> To form the product of two 8-bit integers, for example, the digital device forms the sum and difference, looks both quantities up in a table of squares, takes the difference of the results, and divides by four by shifting two bits to the right. For 8-bit integers the table of quarter squares will have 2<sup>9</sup> entries of 16 bits each.
The Quarter square multiplier technique has also benefitted 8 bit systems that do not have any support for a hardware multiplier. Steven Judd implemented this for the [[MOS Technology 6502|6502]].<ref name=sjudd>{{Citation
| last = Judd
| first = Steven
| |||