One can write an algorithm for computing n^m, where both n and m are
integeres, which runs in time proportaional to log(base2) m . Write an
iterative algorithm with the same performance. Prove-by using a loop
invaraiant or otherwise that your algorithm is correct.

Hello Chuvak2k,

You are asking for an iterative algorithm that computes n^m where both
m and n are integers with time proportional to log_2 (m). An iterative
algorith will have a loop (instead of recursion or another method) to
compute the result.

There is a C program at the end that implements this algorithm that
you can build / run to illustrate the algorithm provided. The rest of
the answer explains how the algorithm works and includes example
output of the program.

The iterative loop has the following preconditions:
 - n and m are integers, m is greater than zero
 - set the result to 1 and the "intermediate value" to n

The loop is quite simple:
 - if m is odd, multiply the result by the current intermediate value
 - multiply the intermediate value by itself (squaring it)
 - divide m by two (discarding the remainder)
Exit the loop if m is zero

Let's work through a simple example of 2^9 or m=9, n=2 (result is
512). Going through the loop, the values of the result and
intermediate value are:
  result  intermediate  odd/even
      2            2      odd
      2            4     even
      2           16     even
    512          256      odd
note the number of calculations is roughly proportional to log_2(9)
[between 3 and 4]. You should also notice that the odd / even values
correspond to the binary pattern of the exponent (9 is 1001 in
binary). Basically this means that the program calculates the result
in the following way:
  512 [2^9] = 256 [2^8] * 2 [2^1]
which you can confirm is the correct result.

The program output (using powers of two) is:

maniac% ./a 2 1
./a: Computing 2^1
./a: Result is 2, loops was 1
maniac% ./a 2 2
./a: Computing 2^2
./a: Result is 4, loops was 2
maniac% ./a 2 3
./a: Computing 2^3
./a: Result is 8, loops was 2
maniac% ./a 2 4
./a: Computing 2^4
./a: Result is 16, loops was 3
maniac% ./a 2 5
./a: Computing 2^5
./a: Result is 32, loops was 3
maniac% ./a 2 6
./a: Computing 2^6
./a: Result is 64, loops was 3
maniac% ./a 2 7
./a: Computing 2^7
./a: Result is 128, loops was 3
maniac% ./a 2 8
./a: Computing 2^8
./a: Result is 256, loops was 4
maniac% ./a 2 9
./a: Computing 2^9
./a: Result is 512, loops was 4
maniac% ./a 2 10
./a: Computing 2^10
./a: Result is 1024, loops was 4
maniac% ./a 2 11
./a: Computing 2^11
./a: Result is 2048, loops was 4
maniac% ./a 2 12
./a: Computing 2^12
./a: Result is 4096, loops was 4
maniac% ./a 2 13
./a: Computing 2^13
./a: Result is 8192, loops was 4
maniac% ./a 2 14
./a: Computing 2^14
./a: Result is 16384, loops was 4
maniac% ./a 2 15
./a: Computing 2^15
./a: Result is 32768, loops was 4
maniac% ./a 2 16
./a: Computing 2^16
./a: Result is 65536, loops was 5
maniac% ./a 2 20
./a: Computing 2^20
./a: Result is 1048576, loops was 5
maniac% ./a 2 30
./a: Computing 2^30
./a: Result is 1073741824, loops was 5

This series of results basically illustrates the log_2(m) run time.

Do not hesitate to try with other values (as long as the result is
less than the precision of your integer values).

Please make a clarification request if you have any difficulty
understanding the algorithm or the program. Good luck with your work.

  --Maniac

Program follows. Uncomment the two printf statements in the loop if
you want to see the changing values of result and intermediate. Delete
those lines if your C compiler does not support the // form of
comments.

#include <stdio.h>

int main(int argc, char *argv[]) {

  int n, m;
  int result, intermediate;
  int loops;

  if (argc <= 2) {
    printf("%s: Usage: %s n m\nComputes n^m, both m and n are integers\n",
	   argv[0], argv[0]);
    return 1;
  }

  sscanf(argv[1], "%d", &n);
  sscanf(argv[2], "%d", &m);

  if (m < 0) {
    printf("%s: exponent was %d, must be positive. Quitting\n",
	   argv[0], m);
    return 1;
  }
  else if (m == 0) {
    printf("%s: Result is 1, loops was 0\n", argv[0]);
    return 0;
  }

  printf("%s: Computing %d^%d\n",
	 argv[0], n, m);
  loops = 0;
  intermediate = n;
  for (result=1; m!=0 ; m/=2) {
    loops++;
    //    printf("%s: Loop is %d, result is %d, intermediate is %d\n",
    //	   argv[0], loops, result, intermediate);
    if ((m%2)==1) {
      result *= intermediate;
    }
    //    printf("%s: Loop is %d, result is %d, intermediate is %d\n",
    //	   argv[0], loops, result, intermediate);
    intermediate *= intermediate;
  }
  printf("%s: Result is %d, loops was %d\n", 
	 argv[0], result, loops);

  return 0;
}

You have yet to prove the algorithm to be true in general, which, imo,
is the difficult part of the question.  All you have done is proven it
for two cases.

JC