1
$\begingroup$

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

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.