Algorithm for computing div and mod

Question

In the attached algorithm for computing the quotient and remainder between two numbers, the third-to-last line (q := -(q + 1)) confuses me.

algorithm

Assuming the second begin...end is an iterative structure, and if q starts at zero, it will alternate between 0 and -1. So that's not the right interpretation. Is it not an iterative structure?

Answer 1

It is to deal with negative division:

$7 \div 3 = 2 ... 1$

Then you want

$-7 \div 3 = -3 ... 2$

This is because you want the remainder to always be $\geq 0$.

$a\div b = c ... d \implies a=bc+d$

$-a=-bc-d=b(-c)-d=b(-c-1)+(b-d)$

Therefore, $c \to -(c + 1), d \to b-d$

Hope this helps.

Answer 2

This is simply means in case you have a negative number, you will multiply the quotient $q$ with negative as $d$ in the quotient-remainder algorithm $n = qd + r$ is always positive and $r$ is always positive too, so the only way to have the negative number is to multiply $q$ by negative to give.

Ex: suppose $n=-13$, then $r = 3$ when $d=5$. You can see that $q=2$, so how we can get $-13$ back? It's only by flipping sign of $q$.

Hope this helps and please ask me if you have more questions.