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".