LOGO-L> Last 2 Digits of 2^999

[Yehuda <yehuka@softhome.net>]

Hello Logo friends,

Logo is a great program to do arithmetics too - a fact that is sometimes overlooked. Last week, a friend asked me what were the last 2 digits of 2^999 (2 raised to the power of 999).

Scheme people are fortunate, as their language features bignum, which provides full precision with integer calculations. They say (expt 2 999) and look at the result (over 300 digits!).

We, Logo people, don't have bignum (yet ???); all we have is 16 meaningful digits of precision (at least in UCBLogo and MSWLogo), so we need to do some thinking.

It doesn't take too much to come to the conclusion, that in every subsequent multiplication by 2, it's enough for us to retain only the last 2 digits of the result, and ignore the other digits. So we remain all the time in the safe region of our Logo.

One way to implement the above idea is the following:

to calculate :base :exp
 op  tail :base :exp :base
end

to tail :base :exp :last_two
 if :exp=1[op :last_two]
 op tail :base :exp-1 remainder :last_two*:base 100
end

to run it you say:

    pr calculate 2 999

and get the correct answer: 88.

You might want to generalize the program to output the last n digits of any integer a raised to the power of any integer b. Remember, that n has to be a reasonable integer in size, less then the maximal precision of your favorite Logo.
 

    _/    _/     _/ _/_/_/_/_/ _/_/_/_/
   _/   _/     _/_/    _/          _/
  _/_/_/     _/  _/   _/        _/
 _/   _/   _/_/_/_/  _/      _/
_/     _/_/      _/ _/     _/_/_/_/

http://www.geocities.com/CollegePark/lab/2276/
e-mail: yehuka@softhome.net