/**
 * Created with IntelliJ IDEA.
 * User: hajadc.tistory.com
 * Date: 8/25/13
 * To change this template use File | Settings | File Templates.
 */
public class Power {
    private static final double BASE = 3.1;
    private static final int POWER = 8;
    private static int count = 0;

    public static void main(String[] args) {
        count = 0;
        System.out.println("Operation: " + BASE + "^" + POWER);
        System.out.println("  Pow1():" + Pow1(BASE, POWER));
        System.out.println("    iterations:" + count);

        count = 0;
        System.out.println("  Pow2():" + Pow2(BASE, POWER));
        System.out.println("    iterations:" + count);
    } // main()

    /**
     * O(N) implementation of power
     *
     * @param base
     * @param power
     * @return
     */
    private static double Pow1(double base, int power) {
        count++;
        if (power == 0) {
            return 1;
        } else if (power > 0) {
            return base * Pow1(base, (power - 1));
        } else {
            return 1 / Pow1(base, -power);
        }
    } // Pow1()

    /**
     * O(log N) implementation of power
     *
     * @param base
     * @param power
     * @return
     */
    private static double Pow2(double base, int power) {
        count++;
        if (power == 0) {
            return 1;
        } else if (power < 0) {
            return 1 / Pow2(base, -power);
        } else {
            if (power % 2 == 0) { // Even power
                double half = Pow2(base, (power / 2));
                return half * half;
            } else {
                return base * Pow2(base, (power - 1));
            }
        }
    } // Pow2()
} // class Power

+ Recent posts