1
$\begingroup$

I've managed to get a VM code of a function that performs integer division. After some work, I translated it into high-level language. I know the translation I made is correct, since I was able to compile it and get the exact VM code I started with. I'm providing here the high-level pseudo-code.

   function int divide(int x, int y) {
        int i, res, isNeg, var3;
        if(y = 0){
            Sys.error(3);
        }

        isNeg = ((x<0) && (y>0))  ||  ((x>0)&&(y<0));
        B[0] = Math.abs(y);
        x = Math.abs(x);

        while((i<15) &&  (!var3)){
            var3 = (32767 - (B[i] - 1))  <  (B[i] - 1);
            if(!var3){
                B[i+1] = B[i] + B[i];
                var3 = (B[i+1] - 1) > (x-1);
                if(!var3){
                    i = i + 1;
                }
            }
        }

        while(i > (-1)){
            if(!((B[i] - 1) > (x - 1))){
                    res = res + A[i];
                    x = x - B[i];
            }
            i = i - 1;
        }

        if(isNeg){
            res = -res;
        }
        return res;
    }

Some notes: A and B are both static arrays. A holds all the powers of 2 (i.e A[i] = 2^i, i=0...15). Each int variable is 16-bit in 2's complement representation (and thus, 32767 is the greatest number that can be represented).
The thing is, I'm not sure how the algorithm works (and it does). Could someone explain this division algorithm?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.