// --------
// Pow.java
// --------

final class Pow {
    /**
     * O(log n) in space
     * O(log n) in time
     * Precondition: (e >= 0) && ((n != 0) || (e != 0))
     */
    public static long eval (long n, int e) {
        assert (e >= 0) && ((n != 0) || (e != 0));
        if (n == 0)
            return 0;
        if (e == 0)
            return 1;
        final long p = eval(n, e / 2);
        if ((e & 1) == 0)
            return p * p;
        return p * p * n;}}

final class PowTest {
    public static void main (String[] args) {
        System.out.println("Pow.java");

        assert Math.pow( 0, 1) ==     0;
        assert Math.pow( 1, 0) ==     1;
        assert Math.pow( 1, 1) ==     1;
        assert Math.pow( 2, 0) ==     1;
        assert Math.pow( 2, 1) ==     2;
        assert Math.pow( 2, 2) ==     4;
        assert Math.pow( 2, 3) ==     8;
        assert Math.pow( 2, 4) ==    16;
        assert Math.pow( 2, 5) ==    32;
        assert Math.pow( 2, 6) ==    64;
        assert Math.pow( 2, 7) ==   128;
        assert Math.pow(-3, 0) ==     1;
        assert Math.pow(-3, 1) ==    -3;
        assert Math.pow(-3, 2) ==     9;
        assert Math.pow(-3, 3) ==   -27;
        assert Math.pow(-3, 4) ==    81;
        assert Math.pow(-3, 5) ==  -243;
        assert Math.pow(-3, 6) ==   729;
        assert Math.pow(-3, 7) == -2187;

        assert Pow.eval( 0, 1) ==     0;
        assert Pow.eval( 1, 0) ==     1;
        assert Pow.eval( 1, 1) ==     1;
        assert Pow.eval( 2, 0) ==     1;
        assert Pow.eval( 2, 1) ==     2;
        assert Pow.eval( 2, 2) ==     4;
        assert Pow.eval( 2, 3) ==     8;
        assert Pow.eval( 2, 4) ==    16;
        assert Pow.eval( 2, 5) ==    32;
        assert Pow.eval( 2, 6) ==    64;
        assert Pow.eval( 2, 7) ==   128;
        assert Pow.eval(-3, 0) ==     1;
        assert Pow.eval(-3, 1) ==    -3;
        assert Pow.eval(-3, 2) ==     9;
        assert Pow.eval(-3, 3) ==   -27;
        assert Pow.eval(-3, 4) ==    81;
        assert Pow.eval(-3, 5) ==  -243;
        assert Pow.eval(-3, 6) ==   729;
        assert Pow.eval(-3, 7) == -2187;

        System.out.println("Done.");}}