| Author |
Message |
Enila Nero
Guest
|
 Posted:
Thu Jul 28, 2005 11:34 pm Post subject:
Multiplying by repeated addition |
|
|
I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
Surely something like that exists since it's useful for machines
without multiplication circuitry.
Thank you. |
|
| Back to top |
|
 |
David Kastrup
Guest
|
| Posted:
Fri Jul 29, 2005 12:13 am Post subject:
Re: Multiplying by repeated addition |
|
|
Enila Nero <geortal@yahoo.com> writes:
| Quote: | I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
|
Go to your library and get "Donald Knuth, The Art of Computer
programming Vol. 2, Seminumerical Algorithms".
You won't easily find a more extensive analysis of this problem
anywhere else.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum |
|
| Back to top |
|
|
Randy Poe
Guest
|
| Posted:
Fri Jul 29, 2005 12:15 am Post subject:
Re: Multiplying by repeated addition |
|
|
Enila Nero wrote:
| Quote: | I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
Surely something like that exists since it's useful for machines
without multiplication circuitry.
|
I think multiplication circuitry is just a hardware
implementation of an addition-based algorithm.
This is easy in base 2, because multiplying by powers
of 2 is done by bitshifting (represented in C by the <<
operator). So 11 << 1 is 11*2, and 11 << 2 is 11*4,
.... x << n is x * 2^n.
Now suppose you wanted to multiply 11 by 9.
Write 9 in base 2: 1001 = 2^3 + 2^0
So 11*9 = 11*2^3 + 11*2^0
Shift 11 by 3, shift 11 by 0 and add the two numbers.
- Randy |
|
| Back to top |
|
|
Pubkeybreaker
Guest
|
| Posted:
Fri Jul 29, 2005 12:15 am Post subject:
Re: Multiplying by repeated addition |
|
|
Use the same algorithm that people use for modular exponentiation: the
binary
method, only instead of modular multiplication at each step, one does
addition.
See Knuth Vol 2.
To multiple A*B, choose the smaller of the two and represent it in
binary. (say A)
Set a variable x = B. Delete the MSB in A. Then, for each 0 in
the representation
of A, add x to itself. For each 1, add x to itself, and also add B.
This requires, on average 3/2 log_2(A) additions. |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Fri Jul 29, 2005 7:13 am Post subject:
Re: Multiplying by repeated addition |
|
|
Enila Nero wrote:
| Quote: | I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
Surely something like that exists since it's useful for machines
without multiplication circuitry.
Thank you.
|
I think you just invented shift and add as a multiply. :-)
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Fri Jul 29, 2005 8:15 am Post subject:
Re: Multiplying by repeated addition |
|
|
Pubkeybreaker wrote:
| Quote: | Use the same algorithm that people use for modular
exponentiation: the binary method, only instead of
modular multiplication at each step, one does
addition.
See Knuth Vol 2.
To multiple A*B, choose the smaller of the two and
represent it in binary. (say A)
Set a variable x = B. Delete the MSB in A.
Then, for each 0 in the representation
of A, add x to itself.
For each 1, add x to itself, and also add B.
This requires, on average 3/2 log_2(A) additions.
|
This is normally used for integer exponentiation.
It isn't optimal but it is close. Knuth explains
a few cases where it isn't optimal, but close enough
for most people.
-- glen |
|
| Back to top |
|
|
Han de Bruijn
Guest
|
| Posted:
Fri Jul 29, 2005 8:15 am Post subject:
Re: Multiplying by repeated addition |
|
|
Enila Nero wrote:
| Quote: | I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
Surely something like that exists since it's useful for machines
without multiplication circuitry.
Thank you.
|
Hmm, I've seen such a thing with powers. Adapting it a bit
results in a (Pascal) program that mostly uses additions.
program for_you;
function product(x : integer; n : integer) : integer;
var
m : integer;
p, y : integer;
begin
m := n;
y := x;
p := 0;
while m > 0 do begin
if (m and 1) > 0 then p := p + y;
m := m shr 1;
y := y + y;
end;
product := p;
end;
procedure test(a,b : integer);
begin
Writeln(a,' * ',b,' = ',product(a,b));
end;
begin
test(5,6);
test(10,15);
end.
Hope this helps.
Han de Bruijn |
|
| Back to top |
|
|
Grumble
Guest
|
|
| Back to top |
|
|
Enila Nero
Guest
|
| Posted:
Sat Jul 30, 2005 8:15 am Post subject:
Re: Multiplying by repeated addition |
|
|
Del Cecchi <cecchinospam@us.ibm.com> writes:
| Quote: | Enila Nero wrote:
I am looking for an optimized algorithm for multiplying by repeated
addition. For example instead of doing
result = 11 * 9 = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 do
temp = 11 + 11
temp = temp + temp //temp has 4 * 11
temp = temp + temp //temp has 8 * 11
result = temp + 11
which is 4 less additions. For large numbers the savings can be
substantial by the use of temporary variables (i.e. registers in a
machine) to hold intermediate results.
Surely something like that exists since it's useful for machines
without multiplication circuitry.
Thank you.
I think you just invented shift and add as a multiply. :-)
|
I vaguely recall that, but what I asked, though not made explicit, is
to perform multiplications strictly with additions, no shifts. The
machine I am working with has no shifts. I know that adding a number
to itself if left shift by 1. The absence of right shift makes
bookkeeping a bit more difficult, or perhaps just different, from the
standard shift and add algorithm. The right shift is used to obtain
the next least significant bit of the multiplier, based on which you
know whether to shift and add or just shift. I am limited to ALU
operations ADD, SUB, NOT, AND, their immediate versions, and
conditional branches based on the sign bit.
A naive approach is to start from 1 and keep doubling, once you exceed
the multiplier you know where its most significant bit is. Subtract
the msb with the trailing zeros from the multiplier, and repeat to find
out where the next msb is. By discovering the positions of the bits
of the multiplier, using additions, which are used to simulate left
shifts as well, one can compute the product.
Thanks.
| Quote: |
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Jul 30, 2005 1:22 pm Post subject:
Re: Multiplying by repeated addition |
|
|
Enila Nero wrote:
(snip)
| Quote: | I vaguely recall that, but what I asked, though not made explicit, is
to perform multiplications strictly with additions, no shifts. The
machine I am working with has no shifts. I know that adding a number
to itself if left shift by 1. The absence of right shift makes
bookkeeping a bit more difficult, or perhaps just different, from the
standard shift and add algorithm. The right shift is used to obtain
the next least significant bit of the multiplier, based on which you
know whether to shift and add or just shift. I am limited to ALU
operations ADD, SUB, NOT, AND, their immediate versions, and
conditional branches based on the sign bit.
|
The exponentiation algorithm, I believe, works with a left shift.
Start with 1, if the sign bit is zero, square, if it is one,
square and multiply by X.
So for multiply, look at the sign bit. If it is zero double the
accumulator, if it is one double and add. Shift the multiplier
left and repeat the appropriate number of times.
-- glen |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in