# Computing 2*q*y in division algorithm without multiplication

3 messages
Open this post in threaded view
|

## Computing 2*q*y in division algorithm without multiplication

 This post was updated on . "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;         }     } ```
 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 } ```