// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Math.jack

/**
 * A library of commonly used mathematical functions.
 * Note: Jack compilers implement multiplication and division using OS method calls.
 */
class Math {
    static Array twoToThe;

    /** Initializes the library. */
    function void init() {
        var int i, x;
        let x = 1;
        let i = 0;
        let twoToThe = Array.new(16);
        while (i < 16){
            let twoToThe[i] = x;
            let x = x + x;
            let i = i + 1;
        }
        return;
    }

    function boolean bit(int x, int i) {
        return ~(x & twoToThe[i] = 0);
    }

    /** Returns the absolute value of x. */
    function int abs(int x) {
        if (x > 0){
            return x;
        } else {
            return -x;
        }
    }

    /** Returns the product of x and y. 
     *  When a Jack compiler detects the multiplication operator '*' in the 
     *  program's code, it handles it by invoking this method. In other words,
     *  the Jack expressions x*y and multiply(x,y) return the same value.
     */
    function int multiply(int x, int y) {
        var int z, res, shiftedX, i;
        let shiftedX = x;
        let i = 0;
        let res = 0;
        while ((twoToThe[i] > x) & (i < 16)) {
            if (Math.bit(y, i)){
                let res = res + shiftedX;
            }
            let shiftedX = shiftedX + shiftedX;
            let i = i + 1;
        }
        return res;
    }

    /** Returns the integer part of x/y.
     *  When a Jack compiler detects the multiplication operator '/' in the 
     *  program's code, it handles it by invoking this method. In other words,
     *  the Jack expressions x/y and divide(x,y) return the same value.
     */
    function int divide(int x, int y) {
        var int ax, ay;
        if (x > 0) {
            if (y > 0) {
                return Math.divide1(x, y);
            } else {
                return -Math.divide1(x, -y);
            }
        } else {
            if (y > 0) {
                return -Math.divide1(-x, y);
            } else {
                return Math.divide1(-x, -y);
            }
        }
    }

    function int divide1(int x, int y) {
        var int q;
        if (y = 0) {
            do Output.printString("Error: division by zero.");
            do Sys.error(0);
        }
        if ((y > x) | (y < 0)) {
            return 0;
        }
        let q = Math.divide1(x, y * 2);
        if (x - (2 * q * y) < y) {
            return 2 * q;
        } else {
            return 2 * q + 1;
        }
    }

    function int length(int x){
        var int n;
        let n = 14;
        while (twoToThe[n] > x){
            let n = n - 1;
        }
        return n;
    }

    /** Returns the integer part of the square root of x. */
    function int sqrt(int x) {
        var int y, k, z, w;
        if (x < 0) {
            do Output.printString("Error: square rooting a negative number.");
            do Sys.error(0);
        }
        let k = Math.length(x) / 2;
        let y = 0;
        while (~(k < 0)) {
            let z = y + twoToThe[k];
            let w = z * z;
            if ((w < x) & (w > 0)) {
                let y = z;
            }
            let k = k - 1;
        }
        return y;
    }

    /** Returns the greater number. */
    function int max(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    /** Returns the smaller number. */
    function int min(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }
}