Subject: Re: [HM] Binary Numbers
From: Prof. Lueneburg (luene@mathematik.uni-kl.de)
Date: Wed Dec 31 1969 - 18:59:59 EST
Marinus wrote on Jan. 29, 2000
>
>
> If I am not mistaken, the ancient egyptian method of multiplication
> presupposes the knowlegde that any natural number can be represented
> by a (unique) sum of different powers of 2.
>
This is a delicate question. It is not necessary to know explicitly that
any natural number is the sum of distinct powers of 2. You will see it
from the following argument. As this method of multiplication is also
called the russian peasant method of multiplication, I start defining the
function russ by
russ(a,b,c) := ab + c.
This function has the following properties:
a) russ(a,b,0) = ab.
b) russ(a,0,c) = c = russ (0,b,c)
c) russ(a,kb,c) = russ(ak,b,c)
d) russ(a,b + 1,c) = russ(a,b,a + c)
Now, given $A$ and $B$ then
a:= A; b := B; c := 0; then russ(a,b,c) = AB
while b > 0 do
if odd(b) then b := b - 1; c := a + c endif; then russ(a,b,c) = AB
a := 2a; b := b/2 then russ(a,b,c) = AB
endwhile;
Then russ(a,b,c) = AB and b = 0. Hence c = AB
One can actually use any q > 1 instead of 2. Then one gets the folowing
procedure for multiplying two natural numbers:
Given $A$ and $B$ then
a:= A; b := B; c := 0; then russ(a,b,c) = AB
while b > 0 do
while not b divisible by q do
b := b - 1; c := a + c then russ(a,b,c) = AB
endwile;
a := qa; b := b/q then russ(a,b,c) = AB
endwhile;
Then russ(a,b,c) = AB and b = 0. Hence c = AB. The performance of this
algorithm is as good as the one we use. The constant in the O may be a
little bit bigger as in the O for ordinary multiplication.
Best regards, Heinz Lueneburg
This archive was generated by hypermail 2b28 : Mon Jan 31 2000 - 10:09:50 EST