// This program serves as an example for doing timing experiments.
// Specifically, the program computes 2^n, for values of n entered
// by the user, in a uniquely inefficient way -- the time to compute
// 2^n by this algorithm is itself proportional to 2^n. This slow
// algorithm is thus a fairly easy thing to time, and various
// hypotheses can be formed about it.

// History:
//
//   January 2007 -- Created by Doug Baldwin as an example for
//     CSci 240.



import javax.swing.JOptionPane;




public class TimingExample {
    
    
    
    
    // The exponentiation algorithm. This is a recursive algorithm, based on
    // the idea that 2^0 is 1, and for any n > 0, 2^n is 2 * 2^(n-1), which in
    // turn can be rewritten as 2^(n-1) + 2^(n-1).
    
    private static long exponentiate( long n ) {
        
        if ( n <= 0 ) {
            return 1;
        }
        else {
            return exponentiate( n - 1 ) + exponentiate( n - 1 );
        }
    }
    
    

    
    // The main program gets an n value from the user, raises 2 to that
    // power, and prints the result.
    
    public static void main (String args[]) {
        
        long n;
        String nAsString = JOptionPane.showInputDialog( "Enter a non-negative integer" );
        
        try {
            n = Long.parseLong( nAsString );
        }
        catch ( NumberFormatException error ) {
            System.out.println( "Replacing invalid number '" + nAsString + "' with 0." );
            n = 0;
        }
        
        long startTime = System.nanoTime();
        long power = exponentiate( n );
        
        System.out.println( "2^" + n + " = " + power );
        long endTime = System.nanoTime();
        System.out.println( "Eapsed time = " + (endTime - startTime) );
    }
}