//****************************************************
// TITLE: FastPower.java                             *
// AUTHOR: Kim Skak Larsen                           *
// DATE: 22/9 2001                                   *
//                                                   *
// Another example of a while loop invariant.        *
// The program computes x^p.                         *
//****************************************************

import java.io.*;

public class FastPower
{
   public static void main (String[] args)
   {
     int x, p, r, q, y;

     // Example values
     p = 5; x = 2;

     // Precondition: p >= 0

     r = 1; q = p; y = x;

     while /*I*/ (q != 0)  // Invariant: r * y^q = x^p and q in N
     {
        if (q % 2 == 1)
        {
           r = r * y;
           q = q - 1;
        }
        else
        {
           y = y * y;
           q = q / 2;
        }
     }

    // Postcondition: r = x^p

     System.out.print(r + "\n");

   } // main

} // FastPower