Euclidean Division

Question

Euclidean Division

Asked 8 years, 1 month ago

Viewed 618 times

2

There is a problem of Euclidean division in which the rest r cannot be greater than the b, following the theorem a = b.q + r.

I made a code and got one accepted, but I found one better than mine!

#include <iostream>
#include <cmath>


using namespace std;


int main(){

    int a,b,q,r;

    cin>>a>>b;
    q = a/b;
    r = a - b*q;

    if(r < 0)
        r = r + abs(b);

    q = (a-r)/b;
    cout<<q<<" "<<r<<endl;



    return 0;
}

Does anyone know how I come to the conclusion that r < 0, the new rest is r = r - b or r = r - |b|?

Friend, it is difficult to understand what is your difficulty. What is "a new rest"? The sentence alone, the way it is, does not make sense. Edit the question and improve it, as it is not at all clear. Also explain if your problem is mathematical or programming.

– Luiz Vieira

2017/01/19 at 01:18

1 answer

Browser other questions tagged c++ mathematics

You are not signed in. Login or sign up in order to post.

by Victor Stafusa • **63,338** points · Answer 1 · 2017-01-19T03:25:26+00:00

Imagine we want to split $a$ chocolates for $b$ children so that each child receives $q$ chocolates and above $r$ chocolates at the end. If we have to $r\;\ge\;b$ , then those $r$ Remaining chocolates, we could get more $b$ chocolates and give one more to each child, which means that each child would receive $q+1$ chocolates, a contradiction. Soon we have proven that $r\;\lt\;b$ for positive values.

For negative values, this can be generalized as $|r|\;\lt\;|b|$ . The proof by contradiction would be similar to the previous one, where we could distribute a surplus of $\pm\;b$ items of the supposed rest and changing the supposed quotient.

Then $a=b.q+r$ , soon $a-r=b.q$ , consequently $-r=b.q-a$ and finally $r=a-b.q$ .

Now, on to your show. First:

r = a - b*q;

Now, that is exactly what is in the above equation.

We can also deduce that if $r\;\gt\;0$ , then $a\;\gt\;b.q$ . If $r\;\lt\;0$ , then $a\;\lt\;b.q$ . This can be achieved by testing the four combinations of $a$ and $b$ (and also zero for $a$ ) that $|a|\;\ge\;|b.q|$ and with that that $|a|\;-\;|b.q|\;\ge\;0$ .

It can also be concluded from $|a|\;\ge\;|b.q|$ that $(\text{sgn}(a-b.q)=\text{sgn}(a)\;\;\text{ou}\;\;a\;=\;b.q)$ , and with it $(\text{sgn}(r)=\text{sgn}(a)\;\;\text{ou}\;\;r\;=\;0)$ .

So that we may have $r\;\lt\;0$ , it is because $a\;\lt\;0$ . And that’s where you come in if.

Within the if, we know that $r\;\lt\;0$ . So we have to $r+|b|=|b|-|r|=r_{novo}$ . Since $|r|\;\lt\;|b|$ , then $|b|\;-\;|r|\;\gt\;0$ and with it $r_{novo}>0$ .

Have the chance that $|b|\;-\;|r|\;\ge\;|b|$ is absurd because it would mean that $|r|\;\le\;0$ , and the result of a module cannot be negative and the case of zero does not enter in this if. So we have to $|b|\;-\;|r|\;\lt\;|b|$ and therefore $r_{novo} < |b|$ .

If you don’t get on if, own $|r|\;\lt\;|b|$ already ensures that $|r|\;\ge\;0$ because modules cannot be negative, and that condition also prevents you from reaching or exceeding the value of $|b|$ .

Unifying the cases where you enter or not if, we have to $0 <= r_{final} < |b|$ .

The case where the module makes a difference within the if that’s when $a\;\lt\;0$ and $b\;\lt\;0$ .

The value added to the rest within the if is correct because by adding $|b|$ , It’s like pretending an extra chocolate was given to each child, which should make the resulting rest equal. As explained above, this does not violate the condition that $|r|\;\lt\;|b|$ , and in fact, it serves exactly to put the value of the rest in the expected range, and therefore everything is right.