/**
 * 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