In the attached algorithm for computing the quotient and remainder between two numbers, the third-to-last line (q := -(q + 1)) confuses me.
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?
2 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
