Computing 2*q*y in division algorithm without multiplication

[sam11]

"an inspection of the divide algorithm’s logic reveals that the value of the expression 2*q*y can be computed without multiplication. Instead, it can be obtained from its value in the previous recursion level, using addition."

I don't understand how to implement this optimization. I would appreciate if I could get a starting point to implement this. I could replace 2*q*y with (q+q)*y but I don't know how to get rid of multiplication with y.

The division algorithm that I have is implemented as follows:
```
    function int divide(int x, int y) {
        var int q;
        let q = Math._divide(Math.abs(x), Math.abs(y));  // runs Math._divide on absolute values of x and y
        if ((x < 0) = (y < 0)) {
            return q;
        } else {
            return q*(-1);
        }
    }

    function int _divide(int x, int y) {
        var int q;
        if ((y > x) | (y < 0)) {
            return 0;
        }
        let q = Math._divide(x, y+y);
        if ((x - (2*q*y)) < y) {
            return q+q;
        } else {
            return q+q+1;
        }
    }

```

[ivant]

It is a bit hard to spot. Here's the original algorithm. Try to compute the next value of 2 * q * y near all the return points. For now don't worry about actually returning the value.

divide(x, y):
    if (y > x) {
        next2qy = // compute the next 2 * q * y
        return 0
    }
    q = divide(x, 2 * y)
    if ((x - 2 * q * y) < y) {
        next2qy = // compute the next 2 * q * y
        return 2 * q
    } else {
        next2qy = // compute the next 2 * q * y
        return 2 * q + 1
    }

Now imagine that we can return several values at the same time (some languages like Python support this). Then the algorithm can look like this:

divide(x, y):
    if (y > x) {
        next2qy = // compute the next 2 * q * y
        return 0, next2qy
    }
    q, qy2 = divide(x, 2 * y)
    if ((x - qy2) < y) {
        next2qy = // compute the next 2 * q * y
        return 2 * q, next2qy
    } else {
        next2qy = // compute the next 2 * q * y
        return 2 * q + 1, next2qy
    }

[ivant]

I don't want to post the solution as to not spoil it for everybody. But feel free to ask me directly if you need further assistance. You can do so by clicking on my name and then "Send Email to ivant".

[daCypher]

It becomes clearer, when you think about how you would implement a long division in binary if you didn't have that algorithm

Let's say you want to divide

0000 0011 1110 1000

 by

0000 0000 0000 1010

. You shift the second number to the right until the leftmost 1s are aligned with each other:

x 0000 0011 1110 1000
y 0000 0010 1000 0000

Then, if y fits into x, you subtract y from x and append a 1 to the result. If y doesn't fit, you leave x as it is and append a 0 to the result. After that, you shift y one position to the right, to check the next digit

x      0000 0001 0110 1000
y      0000 0010 1000 0000
result 0000 0000 0000 0001

x      0000 0001 0110 1000
y      0000 0001 0100 0000
result 0000 0000 0000 0001

x      0000 0000 0010 1000
y      0000 0000 1010 0000
result 0000 0000 0000 0011

x      0000 0000 0010 1000
y      0000 0000 0101 0000
result 0000 0000 0000 0110

...

x      0000 0000 0000 0000
y      0000 0000 0000 1010
result 0000 0000 0110 0100

You can find some of those shifts and appends in the provided algorithm.

let q = Math._divide(x, y+y);

 shifts y to the left recursively until it is larger than x, and then uses the returns to shift y back to its starting value.

return q+q;

 appends a 0 to the result,

return q+q+1;

 appends a 1 to the result.

If you would subtract y from x, the statement

if ((x - (2*q*y)) < y) {

 would just become

if (x < y) {

Maybe you have already spotted the reason why we don't just subtract y from x: x and y are local to the current invocation of the _divide() function and therefore you can't pass a new x value back to the calling invocation. That's where 2qy comes into play. Instead of subtracting y from x, we leave x at it is and compare y to x minus something.

I guess, by now you have figured out, what value is represented by 2qy. It is just the sum of values that you would have subtracted from x so far, if you did the direct approach.