by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
The code below the two algorithms for carrying out integer exponentiation that were presented in the text. Each function has additional debug statements to provide extra output. The non-debug code is given in purple.
// Exp: test Java versions of two exponentiation algorithms
public class Exp {
// exp1: uses binary representation of the exponent.
// Works on binary bits from most significant to least.
// Variable y only present to give loop invariant:
// x^y = z, and y gives the leading bits of Y.
public static long exp1(long x, long Y[], int k) {
long y = 0, z = 1;
int round = 0;
dump1("Initial. ", x, y, z);
for (int i = k; i >= 0; i--) {
y = 2*y;
z = z*z;
dump1("Round: " + (round) + ", ", x, y, z);
if (Y[i] == 1) {
y++;
z = z*x;
dump1("Round: " + (round++) + ", ", x, y, z);
}
}
return z;
}
// dump1: function to spit out debug information
private static void dump1(String s, long x, long y, long z) {
System.out.println(s + "x: " + x + ",\ty: " + y + ",\tz: " + z +
",\t(x^y): " + (exp(x, y)));
}
// exp2: uses binary representation of exponent, without constructing it.
// Works on binary bits from least significant to most.
// Loop invariant is: z*x^y = X^Y
public static long exp2(long X, long Y) {
long x = X, y = Y, z = 1;
dump2("Initial. ", x, y, z);
int round = 1;
while (y > 0) {
while (y%2 == 0) {
x = x*x;
y = y/2;
dump2("Round: " + (round) + ", ", x, y, z);
}
z = z*x;
y = y - 1;
dump2("Round: " + (round++) + ", ", x, y, z);
}
return z;
}
// exp: extra copy of second exp function without debug code
public static long exp(long X, long Y) {
long x = X, y = Y, z = 1;
while (y > 0) {
while (y%2 == 0) {
x = x*x;
y = y/2;
}
z = z*x;
y = y - 1;
}
return z;
}
// dump2: function to spit out debug information
private static void dump2(String s, long x, long y, long z) {
System.out.println(s + "x: " + x + ",\ty: " + y + ",\tz: " + z +
",\tz*(x^y): " + (z*exp(x, y)));
}
public static void main(String[] args) {
long x = Long.parseLong(args[0]);
long y = Long.parseLong(args[1]);
// Convert y to array Y of bits
long Y[] = new long[50];
int k = 0;
long yt = y;
while (yt > 0) {
Y[k++] = yt % 2;
yt = yt/2;
}
k--;
System.out.println("Try first exponentiation algorithm ...");
long z1 = Exp.exp1(x, Y, k);
System.out.println("Method 1: exp1(" + x + ", " + y + ") = " + z1);
System.out.println("\nTry second exponentiation algorithm ...");
long z2 = Exp.exp2(x, y);
System.out.println("Method 2: exp2(" + x + ", " + y + ") = " + z2);
}
}
Here are results of test runs, with a few extra blanks to improve readability:
% java Exp 3 12 Try first exponentiation algorithm ... Initial. x: 3, y: 0, z: 1, (x^y): 1 Round: 1, x: 3, y: 0, z: 1, (x^y): 1 Round: 1, x: 3, y: 1, z: 3, (x^y): 3 Round: 2, x: 3, y: 2, z: 9, (x^y): 9 Round: 2, x: 3, y: 3, z: 27, (x^y): 27 Round: 3, x: 3, y: 6, z: 729, (x^y): 729 Round: 3, x: 3, y: 12, z: 531441, (x^y): 531441 Method 1: exp1(3, 12) = 531441 Try second exponentiation algorithm ... Initial. x: 3, y: 12, z: 1, z*(x^y): 531441 Round: 1, x: 9, y: 6, z: 1, z*(x^y): 531441 Round: 1, x: 81, y: 3, z: 1, z*(x^y): 531441 Round: 1, x: 81, y: 2, z: 81, z*(x^y): 531441 Round: 2, x: 6561, y: 1, z: 81, z*(x^y): 531441 Round: 2, x: 6561, y: 0, z: 531441, z*(x^y): 531441 Method 2: exp2(3, 12) = 531441 % java Exp 2 23 Try first exponentiation algorithm ... Initial. x: 2, y: 0, z: 1, (x^y): 1 Round: 1, x: 2, y: 0, z: 1, (x^y): 1 Round: 1, x: 2, y: 1, z: 2, (x^y): 2 Round: 2, x: 2, y: 2, z: 4, (x^y): 4 Round: 2, x: 2, y: 4, z: 16, (x^y): 16 Round: 2, x: 2, y: 5, z: 32, (x^y): 32 Round: 3, x: 2, y: 10, z: 1024, (x^y): 1024 Round: 3, x: 2, y: 11, z: 2048, (x^y): 2048 Round: 4, x: 2, y: 22, z: 4194304, (x^y): 4194304 Round: 4, x: 2, y: 23, z: 8388608, (x^y): 8388608 Method 1: exp1(2, 23) = 8388608 Try second exponentiation algorithm ... Initial. x: 2, y: 23, z: 1, z*(x^y): 8388608 Round: 1, x: 2, y: 22, z: 2, z*(x^y): 8388608 Round: 2, x: 4, y: 11, z: 2, z*(x^y): 8388608 Round: 2, x: 4, y: 10, z: 8, z*(x^y): 8388608 Round: 3, x: 16, y: 5, z: 8, z*(x^y): 8388608 Round: 3, x: 16, y: 4, z: 128, z*(x^y): 8388608 Round: 4, x: 256, y: 2, z: 128, z*(x^y): 8388608 Round: 4, x: 65536, y: 1, z: 128, z*(x^y): 8388608 Round: 4, x: 65536, y: 0, z: 8388608, z*(x^y): 8388608 Method 2: exp2(2, 23) = 8388608 % java Exp 2 53 Try first exponentiation algorithm ... Initial. x: 2, y: 0, z: 1, (x^y): 1 Round: 1, x: 2, y: 0, z: 1, (x^y): 1 Round: 1, x: 2, y: 1, z: 2, (x^y): 2 Round: 2, x: 2, y: 2, z: 4, (x^y): 4 Round: 2, x: 2, y: 3, z: 8, (x^y): 8 Round: 3, x: 2, y: 6, z: 64, (x^y): 64 Round: 3, x: 2, y: 12, z: 4096, (x^y): 4096 Round: 3, x: 2, y: 13, z: 8192, (x^y): 8192 Round: 4, x: 2, y: 26, z: 67108864, (x^y): 67108864 Round: 4, x: 2, y: 52, z: 4503599627370496, (x^y): 4503599627370496 Round: 4, x: 2, y: 53, z: 9007199254740992, (x^y): 9007199254740992 Method 1: exp1(2, 53) = 9007199254740992 Try second exponentiation algorithm ... Initial. x: 2, y: 53, z: 1, z*(x^y): 9007199254740992 Round: 1, x: 2, y: 52, z: 2, z*(x^y): 9007199254740992 Round: 2, x: 4, y: 26, z: 2, z*(x^y): 9007199254740992 Round: 2, x: 16, y: 13, z: 2, z*(x^y): 9007199254740992 Round: 2, x: 16, y: 12, z: 32, z*(x^y): 9007199254740992 Round: 3, x: 256, y: 6, z: 32, z*(x^y): 9007199254740992 Round: 3, x: 65536, y: 3, z: 32, z*(x^y): 9007199254740992 Round: 3, x: 65536, y: 2, z: 2097152, z*(x^y): 9007199254740992 Round: 4, x: 4294967296, y: 1, z: 2097152, z*(x^y): 9007199254740992 Round: 4, x: 4294967296, y: 0, z: 9007199254740992, z*(x^y): 9007199254740992 Method 2: exp2(2, 53) = 9007199254740992