// BigIntegerTest.java SJ


import java.math.BigInteger;

public class BigIntegerTest {

	public static void main(String[] args) {

        int N = 10, M = 2, K = 1;

        DsaTimer a = new DsaTimer("Total");

		BigIntegerTest l = new BigIntegerTest();

        if (args.length > 0)
            N = Integer.valueOf(args[0]);

        if (args.length > 1)
            M = Integer.valueOf(args[1]);

        if (args.length > 2)
            K = Integer.valueOf(args[2]);

        for (int i = 8; i <= N; i*=2) {
            if (i > 100*1000)
                K = 5;
            if (i > 500*1000)
                K = 1;
            l.test(i-1, M, K);
            l.test(i, M, K);
        }

        System.out.println(a);

	} // main()


    void test(int n, int m, int k) {

        BigInteger x = BigInteger.valueOf(m);

        DsaTimer best1 = null;
        DsaTimer best2 = null;
        for (int j = 0; j < k; j++) {

            DsaTimer t = new DsaTimer();
            BigInteger r = pow1(x, n);
            t.stop();

            if (n < 10 && j == 0)
                System.out.println("pow1 " + r);

            if (t.compareTo(best1) < 0)
                best1 = t;

            t = new DsaTimer();
            r = pow2(x, n);
            t.stop();

            if (n < 10 && j == 0)
                System.out.println("pow2 " + r);

            if (t.compareTo(best1) < 0)
                best2 = t;
        }

        System.out.println("pow1 n = " + n + " m = " + m + " " + best1);
        System.out.println("pow2 n = " + n + " m = " + m + " " + best2);
        System.out.println("pow1/pow2  n = " + n + " " + (1.0*best1.time()/best2.time()));
    }

    BigInteger pow1(BigInteger x, int n) {
        BigInteger r = new BigInteger("1");
        for (int i = 0; i < n; i++)
            r = r.multiply(x);
        return r;
    }

    BigInteger pow2(BigInteger x, int n) {
        if (n == 0 )
            return BigInteger.valueOf(1);
        if (n == 1 )
            return x;
        if (n%2 == 0)					// n even
            return (pow2(x.multiply(x), n/2 ) );			 // pow(x*x, n/2)
        else
            return (x.multiply(pow2(x.multiply(x), n/2 ) )); // pow(x*x, n/2)*x
    }


} // class BigIntegerTest