CS3343/3341
 Analysis of Algorithms 
  Exponentiation  
  Three Ways  

Exponentiation, Three ways

This shows three exponentiation programs. Each program explores the particular multiplications and squarings that occur as a result of carrying out the exponentiation. For this purpose all three programs use special functions mul and sqr to perform these operations. Output code within these functions produces a log of the particular low-level actions of the algorithms.

At the end, you can see that the output from the text's routine and from the recursive version is exactly the same, while the output from the routine presented in class is quite different, not just in the order of operations, but in the particular operations that occur.

Output at the end includes all the examples that were asked for in Recitation 4. The first table gives implementations in C, while the second gives implementations in Java using long type. The earlier examples produce exactly the same output, while Java programs show a run with much bigger numbers.

Exponentiation Algorithms in C
From ClassRecursiveFrom Text
// exponend.c: test fast exponen
#include <stdio.h>

double mul (double r, double s){
   printf("mul: r=%.0f, ", r);
   printf("s=%.0f\n", s);
   return r*s;
}

double sqr (double r) {
   printf("sqr: r=%.0f\n", r);
   return r*r;
}

// expon: fast exponentiation
double expon(double a, int b) {
   double d = 1; // final result

   while(b > 0) {
      if (b%2 == 1) d =mul(d,a);
      b = b/2; // drop right bit
      if (b > 0) a = sqr(a);
   }
   return d;
}

int main() {
   double a, res;
   int b;
   scanf("%lf %i", &a, &b);
   res = expon(a, b);
   printf("a: %g, b: %i, ",a,b);
   printf("res: %.0f\n", res);
}

// exprecd.c: test recur. expon
#include <stdio.h>

double mul (double r, double s){
   printf("mul: r=%.0f, ", r);
   printf("s=%.0f\n", s);
   return r*s;
}

double sqr (double r) {
   printf("sqr: r=%.0f\n", r);
   return r*r;
}

// expon: recur. exponentiation
double expr(double a, int b) {
   if (b == 0) return 1;
   if (b%2 == 0) {
      double d=sqr(expr(a,b/2));
      return d;
   }
   if (b%2 == 1) {
      double d = mul(sqr(expr(a,
         (b-1)/2)), a);
      return d;
   }
}

int main() {
   double a, res;
   int b;
   scanf("%lf %i", &a, &b);
   res = expr(a, b);
   printf("a: %g, b: %i, ",a,b);
   printf("res: %.0f\n", res);
}

// exponend2.c: test fast expon
#include <stdio.h>
int binary(int , int []);
double mul(double r, double s){
   printf("mul: r=%.0f, ", r);
   printf("s=%.0f\n", s);
   return r*s;
}

double sqr (double r) {
   printf("sqr: r=%.0f\n", r);
   return r*r;
}

// expon: fast exponentiation
double expon(double a, int b[],
      int k) {
   double d = 1; // final res
   int i;
   for (i = k; i >= 0; i--) {
      d = sqr(d);
      if (b[i] == 1)d=mul(d,a);
   }
   return d;
}

int main() {
   double a, res;
   int bin, k, i;
   int b[20];
   scanf("%lf %i", &a, &bin);
   k = binary(bin, b);
   res = expon(a, b, k);
   printf("a: %.0lf, b: ", a);
   for (i = k; i >= 0; i--)
      printf("%i", b[i]);
   printf(", res: %.0f\n",res);
}

//  produce binary rep of exp
int binary(int bin, int b[]) {
   int k = 0;
   while (1) {
      b[k] = bin%2;
      bin = bin/2;
      if (bin == 0) break;
      k++;
   }
   return k;
}
Output: 3^23
%cc -o exponend exponend.c -Wall
% ./exponend
3 23
mul: r=1, s=3
sqr: r=3
mul: r=3, s=9
sqr: r=9
mul: r=27, s=81
sqr: r=81
sqr: r=6561
mul: r=2187, s=43046721
a: 3, b: 23, res: 94143178827

% cc -o exprecd exprecd.c -Wall
% ./exprecd
3 23
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
mul: r=81, s=3
sqr: r=243
mul: r=59049, s=3
sqr: r=177147
mul: r=31381059609, s=3
a: 3, b: 23, res: 94143178827

% cc -o exponend2 exponend2.c
% ./exponend2
3 23
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
mul: r=81, s=3
sqr: r=243
mul: r=59049, s=3
sqr: r=177147
mul: r=31381059609, s=3
a: 3, b: 10111, res:94143178827
Output: 3^22
% ./exponend
3 22
sqr: r=3
mul: r=1, s=9
sqr: r=9
mul: r=9, s=81
sqr: r=81
sqr: r=6561
mul: r=729, s=43046721
a: 3, b: 22, res: 31381059609

% ./exprecd
3 22
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
mul: r=81, s=3
sqr: r=243
mul: r=59049, s=3
sqr: r=177147
a: 3, b: 22, res: 31381059609

% ./exponend2
3 22
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
mul: r=81, s=3
sqr: r=243
mul: r=59049, s=3
sqr: r=177147
a: 3, b: 10110, res:31381059609
Output: 3^19
% ./exponend
3 19
mul: r=1, s=3
sqr: r=3
mul: r=3, s=9
sqr: r=9
sqr: r=81
sqr: r=6561
mul: r=27, s=43046721
a: 3, b: 19, res: 1162261467

% ./exprecd
3 19
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
sqr: r=81
mul: r=6561, s=3
sqr: r=19683
mul: r=387420489, s=3
a: 3, b: 19, res: 1162261467

% ./exponend2
3 19
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
sqr: r=81
mul: r=6561, s=3
sqr: r=19683
mul: r=387420489, s=3
a: 3, b: 10011, res: 1162261467
Output: 5^13
% ./exponend
5 13
5 13
mul: r=1, s=5
sqr: r=5
sqr: r=25
mul: r=5, s=625
sqr: r=625
mul: r=3125, s=390625
a: 5, b: 13, res: 1220703125

% ./exprecd
5 13
sqr: r=1
mul: r=1, s=5
sqr: r=5
mul: r=25, s=5
sqr: r=125
sqr: r=15625
mul: r=244140625, s=5
a: 5, b: 13, res: 1220703125

% ./exponend2
5 13
5 13
sqr: r=1
mul: r=1, s=5
sqr: r=5
mul: r=25, s=5
sqr: r=125
sqr: r=15625
mul: r=244140625, s=5
a: 5, b: 1101, res: 1220703125

Exponentiation Algorithms in C
From ClassRecursiveFrom Text
// Exponen.java: test fast exponen
public class Exponen {

   static long mul (long r, long s){
      System.out.print("mul: r=" + r+", ");
      System.out.println("s=" + s);
      return r*s;
   }

   static long sqr (long r) {
      System.out.println("sqr: r=" + r);
      return r*r;
   }

   // expon: fast exponentiation
   static long expon(long a, long b) {
      long d = 1; // final result

      while(b > 0) {
         if (b%2 == 1) d =mul(d,a);
         b = b/2; // drop right bit
         if (b > 0) a = sqr(a);
      }
      return d;
   }

   public static void main(String[] args) {
      long a = Integer.parseInt(args[0]);
      long b = Integer.parseInt(args[1]);
      long res = expon(a, b);
      System.out.print("a: " + a + ", b:" +
         b + ", ");
      System.out.println("res: " + res);
   }
}

// Exprec.c: test recursive expon
public class Exprec {

   static long mul (long r, long s){
      System.out.print("mul: r=" + r+", ");
      System.out.println("s=" + s);
      return r*s;
   }

   static long sqr (long r) {
      System.out.println("sqr: r=" + r);
      return r*r;
   }

   // expon: recursive exponentiation
   static long expr(long a, long b) {
      if (b == 0) return 1;
      if (b%2 == 0) {
         long d = sqr(expr(a, b/2));
         return d;
      }
      if (b%2 == 1) {
         long d = mul(sqr(expr(a,
            (b-1)/2)), a);
         return d;
      }
      return -1; // for compiler
   }

   public static void main(String[] args) {
      long a = Integer.parseInt(args[0]);
      long b = Integer.parseInt(args[1]);
      long res = expr(a, b);
      System.out.print("a: " + a + ", b:" +
         b + ", ");
      System.out.println("res: " + res);
   }
}

// Exponen2.java: test recursive expon
//  uses binary rep of exponent
public class Exponen2 {

   static long mul (long r, long s){
      System.out.print("mul: r=" + r + ", ");
      System.out.println("s=" + s);
      return r*s;
   }

   static long sqr (long r) {
      System.out.println("sqr: r=" + r);
      return r*r;
   }

   // expon: fast exponentiation
   static long expon(long a, int b[], int k) {
      long d = 1; // final result
      for (int i = k; i >= 0; i--) {
         d = sqr(d);
         if (b[i] == 1) d = mul(d, a);
      }
      return d;
   }

   public static void main(String[] args) {
      long a = Integer.parseInt(args[0]);
      int bin = Integer.parseInt(args[1]);
      int[] b = new int[20];
      int k = binary(bin, b);
      long res = expon(a, b, k);
      System.out.print("a: " + a + ", b: ");
      for (int i = k; i >= 0; i--)
         System.out.print(b[i]);
      System.out.println("res: " + res);
   }

   //  produce binary rep of exp
   static int binary(int bin, int b[]) {
      int k = 0;
      while (true) {
         b[k] = bin%2;
         bin = bin/2;
         if (bin == 0) break;
         k++;
      }
      return k;
   }
}
Output: 3^23
java Exponen  2 61
mul: r=1, s=2
sqr: r=2
sqr: r=4
mul: r=2, s=16
sqr: r=16
mul: r=32, s=256
sqr: r=256
mul: r=8192, s=65536
sqr: r=65536
mul: r=536870912, s=4294967296
a: 2, b:61, res: 2305843009213693952

java Exprec  2 58
sqr: r=1
mul: r=1, s=2
sqr: r=2
mul: r=4, s=2
sqr: r=8
mul: r=64, s=2
sqr: r=128
sqr: r=16384
mul: r=268435456, s=2
sqr: r=536870912
a: 2, b:58, res: 288230376151711744

java Exponen2  3 37
sqr: r=1
mul: r=1, s=3
sqr: r=3
sqr: r=9
sqr: r=81
mul: r=6561, s=3
sqr: r=19683
sqr: r=387420489
mul: r=150094635296999121, s=3
a: 3, b: 100101, res: 450283905890997363

Revision date: 2012-09-16. (Please use ISO 8601, the International Standard Date and Time Notation.)