Anonymous user
Talk:Ethiopian multiplication: Difference between revisions
Ethiopian???
m (add comment about numbers vs. integers, and also about negative integers.) |
(Ethiopian???) |
||
Line 40:
::: Michael and I discussed it at the time [http://rosettacode.org/wiki/User_talk:Paddy3118#Ethiopian_Multiplication here]. --[[User:Paddy3118|Paddy3118]] 22:11, 22 July 2010 (UTC)
==Ethiopian??? My foot!==
This is just a straightforward long multiplication algorithm using the binary number system!
If you need a video to explain this, you need to go back to CS for a refresher.
Say you want to multiply 100101 by 1101 okay? This is the same thing as:
(100000 * 1101) + (100 * 1101) + (1 * 1101).
See, we have "struck out" the entries that are even (corresponding to the zero digits in the left hand operand).
1 * 1101 == 1101 // 100101 & 1 == 1 -> keep!
10 * 1101 == 1101 << 1 // (100101 >> 1) & 1 == 0
100 * 1101 == 1101 << 2 // (100101 >> 2) & 1 == 1 -> keep!
1000 * 1101 == 1101 << 3 // (100101 >> 3) & 1 == 0
10000 * 1101 == 1101 << 4 // (100101 >> 4) & 1 == 0
100000 * 1101 == 1101 << 5 // (100101 >> 5) & 1 == 1 -> keep!
The algorithm determines which rows to discard by dividing one of the operands repeatedly by by two and testing for even, which is the same thing as shifting right and testing for a 1 bit: i.e. iterating over the binary representation to find the 1's, from the LSB upward. The other operand is multiplied by two to get it into the corresponding bit position.
This is the most basic multiplication algorithm that has been widely implemented in hardware and is also equivalent to long multiplication:
1101
* 100101
------
1101
110100
+ 110100000
----------
<sum>
Same "shift", different pile.[[Special:Contributions/24.85.131.247|24.85.131.247]] 03:50, 9 November 2011 (UTC)
| |||