No Subject

[neuwirth <neuwirth@smc.univie.ac.at>]

the last 2 digits of 2^999

once again i cannot resist generalizing.

the problem of course can be reformulated
in the following way:

we want the remainder of 2^999 divided by 100
(which is what yeduda is using in his program).

elementary number theory shows us the for any 2 numbers
a b and m we get the same result if we
on one hand we multiply a and be and the calculate
the remainder for the product divided my m
and on the other hand we
calculate the remainders for a and b,
multiply these remainders, and if necessery,
once again devivde this product of remainders by m
and again take the remainder.

the mathematical expression for this is

(a mod m) * (b mod m) = (a*b mod m)

this is the general method for yehuda's problem.

now, for another aspect.

we are calculating powers,
i.e. results of iterative application of multiplication.

so yehuda's solution can be rewritten:

to mod.mult :a :b :m
output remainder :a * :b :m
end

to mod.power :a :exp :m
if :exp = 0 [output 1]
output mod.mult :a (mod.power :a :exp - 1 :m) :m
end

this works reasonably well,
but if we calculate 2^9999 we notice that
this way of calculation powers is not very fast.
in fact, time used is linear in :exp

we can do faster!

let us illustrate the idea with an exaple:

2^16=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2

needs 15 multiplications in the standard way:
but

2^16=(2*2*2*2*2*2*2*2)*(2*2*2*2*2*2*2*2)
is just the square of 2^8
if we calculate 2^8 and multiply it by itselt,
we save 7 multiplications.

2^8 itself can be calculated by squaring 2^4 and so on.

this only works if the exponent is even.
if the exponent is odd,
we use the following method:

2^17=2^16*2
and then we apply the method for 2^17 and multly the result by 2.

this leads to the following method:

to evenp :n
output 0 = (remainder :n 2)
end


to mod.square :a :m
output mod.mult :a :a :m
end


to mod.fast.power :a :exp :m
if :exp = 0 [output 1]
if evenp :exp [output mod.square (mod.fast.power :a :exp / 2 :m) :m]
output mod.mult :a (mod.fast.power :a :exp - 1 :m) :m
end

mathematically speaking this method works because 
we can put in the parentheses arbitrarily,
so we are using the fact that multiplication
is associative.

it is also intersting to study the maximal number of multiplications 
needed.
an informal analysis shows that
you can't get any better than squaring at each step.

which for exponents n=2^k
gives k=log2(n) as the number of multiplications.
the worst thing that can happen is that you have to split of a factor of
2 at each second step.
it turns out that the "bad numbers" in that sense are just exponents 
n=(2^k)-1

from this, we can derive that
exponentiation with an exponent n
has 
2*log2(n)
as an upper bound for the number of multiplications.
this is much better than linear.
and it is due to the associative law.





--
Erich Neuwirth <neuwirth@smc.univie.ac.at>
Computer Supported Didactics Working Group, Univ. Vienna
Visit our SunSITE at http://sunsite.univie.ac.at



---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.