# Why this division algorithm works?

I found this problem on an algorithmic book. I have solve the requestments about time (O(n^2)) but I can't figure out how it works.

Input: Two n-bit integers x and y, where y ≥ 1

Output: The quotient and remainder of x divided by y

function divide(x, y)

if x = 0:
return (q, r) = (0, 0)

(q, r) = divide(floor(x/2), y)

q = 2 · q
r = 2 · r

if x is odd:
r = r + 1

if r ≥ y:
r = r − y
q = q + 1

return (q, r)

• time ( $O(n^2)$ ) can you find/argue a tighter bound? – greybeard Feb 19 '18 at 21:07
• I think there is not a tighter bound. – Sikelef Feb 20 '18 at 18:00
• What would this algorithm look like using ten instead of two? Can you make the connection to "schoolbook division"? – greybeard Feb 20 '18 at 19:35

For even $a$ and $b \ne 0$ and integral division $$\frac{a}{b} = \frac{2a}{2b} = 2 \cdot \frac{( a / 2 )}{b}$$ Similarly for the remainder $$a = 2 \cdot \frac{a}{2} \space (mod \space b)$$ Effectively transforming your problem of division of number with n bits into division of a number with n-1 bits (half as big number).
The algorithm uses integral division in the floor(x\2) part and there you might lose 1 if x was odd. You're giving it back with the if x is odd: block to the remainder and since this might make your reminder the same size as y you need to check if that happened and change the values accordingly. (Notice that r > y can never happen and there could be just as fine if r == y:.)
You just do this n times where n is the number of bits of x.
Finally the algorithm is not $O(n^2)$ but rather $O(n)$ in the number of bits of x. That's assuming the floor(x/2) part does not call the divide function, because that would end in infinite loop (you would need e.g. compute a/2 to compute a/b which would in turn need again computation of a/2. This can be avoided by using a>>1 instead of a/2 which also authomatically floors the result).