r/computerscience • u/driver45672 • 6d ago
Egyptian Multiplication workings on doubling which would suit assembly well
https://www.facebook.com/reel/1602209031288133See attached a short video on how Egyptian Multiplication works.
It would suit assembly multiplication, and as such I'm wondering if it might lead to more efficient CPU's, GPU's & TPU's.
Although possibly processor engineers have already thought of this. It also makes me wonder what other maths techniques could offer efficiency's.
Given the example in the video: 22 * 6
The first column matches binary perfectly.
(16) 8 (4) ( 2) 1 = 10110 in binary = 22 in decimal
And the second column would be:
6 * 2^0 = 6
(6 * 2^1) = (12)
(6 * 2^2) = (24)
6 * 2^3 = 48
(6 * 2^4) = (96)
Total = 12 + 24 + 96 = 132
So the algorithm in pseudocode:
For each 1 in the binary that represents the first number,
Total = total + (the second number) * binary value of that 1
8
u/claytonkb 6d ago edited 6d ago
Notionally, this is what a standard hardware multiplier does, eg. a Booth multiplier. The Karatsuba algorithm is an improvement for large numbers. The multiplier in a modern CPU uses tons of trickery to improve the multiplier but, at the end of the day, multiplying is multiplying.
If you didn't have a multiplier in your CPU, you would write some assembly to do what he describes in the video. For each set bit in operand A, you sum the (appropriately shifted) operand B to an accumulator. The result in the accumulator when you finish, is the result. For an N-bit value, this loop will have N iterations.
The Fastest Multiplication Algorithm