Math CentralQuandaries & Queries


Question from Tim, a student:

I am trying to understand a^(2^n).
The hint they give is a^(2^(n+1)) = (a^(2^n))^2
I am writing a program that will solve a^(2^n) recursively but need to
understand the power before I begin.
I am currently pursuing writing (a) x (a^(2^(n-1))) where the
(a^(2^(n-1))) would be the recursive function call a n approaches 0.
Once n is 0, the result would be multiplied by a two more times.
Anyway, explaining these powers would be appreciated. I will most likely
complete the program before the answer but I want to understand the
logic of these powers. Thank you, Tim

Hi Tim. I hope I understand what you are trying to accomplish. I will proceed with the assumption n is a non-negative integer.

    var p = a;            // let p represent the product
    for (; n>0; n--) {
       p = p^2;
    print p;

This code uses the hint. When n = 0, then p = a^(2^0) which is a^1, so we start at p = a. For each higher value of n, the product is squared again. That's what is implied by the hint a^(2^(n+1)) = (a^(2^n))^2. So this little snippet of code uses a decrement loop such as one it sounds like you were leaning toward.

However, the code above is not recursive; rather, it is iterative. So here's a less obvious bit of code that is recursive:

   // calculate p = a^(2^n) using a function that is recursive.
   p = f(a,n);
   function f(a,n) {
      if (n > 0) {
         var i = f(a,n-1);       // get the value for n-1
         return i*i;             // and square it because a^(2^n) = [ a^(2^(n-1)) ]^2
      } else {
         return a;               // because a^(2^0) = a

Hope this helps,
Stephen La Rocque.

About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS