CODEWITHSUNDEEP
c++algorithmdivision
user3347937
user3347937

Reputation:

C++ Programming the division alogrithm

The division algorithm states that given two integers a and d, with d ≠ 0, there exists unique integers q and r such that a = qd + r and 0 ≤ r < |d|, where |d| denotes the absolute value of d. The integer q is the quotient, r is the remainder, d is the divisor, and a is the dividend. prompt the user for a dividend and divisor and then display the division algorithm's results:

   If a = 17 and d = 3, then q = 5 and r = 2, since 17 = 5 * 3 + 2.
   If a = 17 and d = -3, then q = -5 and r = 2, since 17 = -5 * -3 + 2.


The C++ operators for integer division do not conform to the division algorithm. Explain in output displayed to the user of the program when to expect results that disagree with the division algorithm. The program should not attempt to resolve this issue.

Ok, so I've been trying to figure this out for a few days now and I just can't crack it. The only way I can think of solving this is by using mod to find r or using a successive subtraction to find q. However, I'm pretty sure both of those solution don't really count. Is there some other way to solve this problem?

[Edit] I don't think successive subtraction works because that's just Euclid's algorithm so I really wouldn't be using this algorithm and using modulus would just like using the C++ division operator.

Upvotes: 1

Views: 2794

Answers (4)

Don Bourgeois
Don Bourgeois

Reputation: 63

The C++ integer division operator gives the correct result only if both dividend and divisor are positive. This because it always rounds toward zero

Upvotes: 1

Shashank
Shashank

Reputation: 13869

With the way the question is worded, I'm pretty sure you are supposed to use mod to find r and the division operator to find q. It says straight up "The C++ operators for integer division do not conform to the division algorithm. Explain in output displayed to the user of the program when to expect results that disagree with the division algorithm. The program should not attempt to resolve this issue." This means, don't over-think it, and instead just demonstrate how the operators don't conform to the algorithm without trying to fix anything.

Suppose your code naively uses C++ operators to calculate q and r as follows:

int q = a / d;
int r = a % d;

You then get wrong (in this case, wrong just means they don't "conform" to your algorithm) values for both q and r in the following two cases:

  1. a = -17, b = 3

    The code will result in:

    q = -5, r = 2

    This does not conform to the division algorithm because

    -5 * 3 + 2 = -13 so you clearly have the wrong q and r.

  2. a = -17, b = -3

    The code will result in:

    q = 5, r = -2

    This does not conform to the division algorithm because there is a rule that 0 <= r < |d|. In other words, r must be positive.

In the other cases, i.e. where both a and d are positive or when a is positive and d is negative, the C++ operators will correctly "conform" to your algorithm.

Upvotes: 1

selbie
selbie

Reputation: 104474

Here's a hint. For positive numbers, everything works out ok.

The C++ expression q = 17/3 results in q == 5.

But for negative numbers:

The expression q = -17/3 results in q == -5

Upvotes: 2

Amen
Amen

Reputation: 1633

As the question doesn't clearly states the problem I presume you want to output the devision like the examples provided, so a simple code would be: 

int a=17;
int b=-3;
cout<<"If a="<<a<<"and b="<<b<<"then q="<<a/b<<"and r="<<a%b;

Upvotes: 0

Related Questions