/**
 * 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
/**
 * Created with IntelliJ IDEA.
 * User: hajadc.tistory.com
 * Date: 8/25/13
 * To change this template use File | Settings | File Templates.
 */
public class Division {
    private static final int DIVISOR = 2;
    private static final int DIVIDEND = 1024;
    private static int count = 0;

    public static void main(String[] args) {
        // 1024 / 2
        count = 0;
        System.out.println("Operation: " + DIVIDEND + " / " + DIVISOR);
        System.out.println("  Div1():" + Div1(DIVIDEND, DIVISOR));
        System.out.println("    iterations:" + count);
        count = 0;
        System.out.println("  Div2():" + Div2(DIVIDEND, DIVISOR, 1));
        System.out.println("    iterations:" + count);

        // 1025 / 2
        count = 0;
        System.out.println("Operation: " + (DIVIDEND + 1) + " / " + DIVISOR);
        System.out.println("  Div1():" + Div1(DIVIDEND + 1, DIVISOR));
        System.out.println("    iterations:" + count);
        count = 0;
        System.out.println("  Div2():" + Div2(DIVIDEND + 1, DIVISOR, 1));
        System.out.println("    iterations:" + count);

        // 1023 / 2
        count = 0;
        System.out.println("Operation: " + (DIVIDEND - 1) + " / " + DIVISOR);
        System.out.println("  Div1():" + Div1(DIVIDEND - 1, DIVISOR));
        System.out.println("    iterations:" + count);
        count = 0;
        System.out.println("  Div2():" + Div2(DIVIDEND - 1, DIVISOR, 1));
        System.out.println("    iterations:" + count);
    } // main()

    /**
     * O(N) implementation of division
     *
     * @param dividend
     * @param divisor
     * @return
     */
    private static int Div1(int dividend, int divisor) {
        count++;
        int curr = dividend - divisor;
        if (curr > 0) {
            return Div1(curr, divisor) + 1;
        } else if (curr == 0) {
            return 1;
        } else {
            return 0;
        }
    } // Div1()

    /**
     * O(log N) implementation of division
     *
     * @param dividend
     * @param divisor
     * @param multi
     * @return
     */
    private static int Div2(int dividend, int divisor, int multi) {
        count++;
        int curr = dividend - (multi * divisor);
        if (curr > 0) {
            return Div2(curr, divisor, multi * 2) + multi;
        } else if (curr == 0) {
            return multi;
        } else {
            if (multi > 1) {
                return Div2(dividend, divisor, multi / 2);
            } else {
                return 0;
            }
        }
    } // Div2()
} // class Division

+ Recent posts