LOGO-L> Visualizing Complexity with the Tracer

[Yehuda <yehuka@softhome.net>]

neuwirth wrote:

>  we are calculating powers,
>  ...

>  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.

  ...

>  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.
 

Hi there,

We can visualize this (or any) complexity using the built-in tracer (UCBLogo and MSWLogo have it, I have no idea about other Logos).

For this, here's Eric's algorithm, in a slightly modified code:

========================================
to exponent :base :exp
if :exp=0 [op 1]
if evenp :exp[op power2 exponent :base :exp/2]
op :base * power2 exponent :base int :exp/2
end

to power2 :exp
op :exp*:exp
end

to evenp :num
op 0=remainder :num 2
end
========================================

To find, e.g., 5^5 we say: PRINT EXPONENT 5 5.

Now say TRACE "EXPONENT and run it  for 5^5. Here's what I got:

( exponent 5 5 )
 ( exponent 5 2 )
  ( exponent 5 1 )
   ( exponent 5 0 )
   exponent outputs 1
  exponent outputs 5
 exponent outputs 25
exponent outputs 3125
3125

We notice that EXPONENT was called recursively 4 times.

How many recursive calls will be needed if I *multiply* the exponent, to find the value of 5^10?

Let's run again our traced program by saying PRINT EXPONENT 5 10:

( exponent 5 10 )
 ( exponent 5 5 )
  ( exponent 5 2 )
   ( exponent 5 1 )
    ( exponent 5 0 )
    exponent outputs 1
   exponent outputs 5
  exponent outputs 25
 exponent outputs 3125
exponent outputs 9765625
9765625

We can witness 5 recursive calls, one more than before.

So we conclude, that *doubling* the exponent needs *one more* recursive call. In mathematical language: The complexity of this program is logarithmic, or O(log n), as Erich correctly stated.

Best regards...

[[Yehuda]]

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

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