Division Algorithm

[longberns]

Reading through my course book for discrete mathematics. I am trying to put my programming skills into almost everything i read these days. But this one gives me headache.

  /*
	blongho, 2017-07-27
	Program to run the division algorithm

	From www.inf.ed.ac.uk/teaching/courses/dmmr/slides/13-14/Ch4.pdf
	When an integer is divided by a positive integer, there is a quotient and
	a remainder. This is traditionally called the “Division Algorithm”, but it
	is really a theorem.

	THEOREM
	If a is an integer and d a positive integer, then there are unique
	integers q and r, with 0 ≤ r < d, such that a = dq + r

	a is called the dividend.
	d is called the divisor.
	q is called the quotient. q = a div d
	r is called the remainder. r = a mod d

	Modification: a = dq + r such that 0 ≤ r < |d|
	From: 
	NB: Book is in SWEDISH language
		  Title  : Diskret matematik och diskreta modeller 
		  Authors: Kimmo Eriksson & Hillevi Gavel
		  Edition: Second edition (2013)
		  ISBN	 : 978914408999
		  Page Extract: 36

	The algorithm herein follows this modification. In such way, it takes care
	of negative numbers too. 
*/
#include <iostream>
#include <stdexcept>

void divide(int dividend, int divisor);
bool tryAgain(char text[]);
int main()
{
	std::cout << "This is a small code snippet that helps divide two integers\n"
				<< "It retains the quotient and the remainder" << std::endl;

	do {
		int dividend{ 0 };
		int divisor{ 0 };

		std::cout << "\nEnter dividend(numerator) : ";
		std::cin >> dividend;

		std::cout << "Enter divisor(denominator): ";
		std::cin >> divisor;

		std::cout << std::endl;

		try {
			divide(dividend, divisor);
		}
		catch (std::exception &e) {
			std::cout << e.what() << std::endl;
		}
	}while (tryAgain("Do you want to run another test(y/n)?: "));
	
	return 0;
}

void divide(int dividend, int divisor)
{
	if (divisor == 0) { 
		throw(std::invalid_argument("Exception: Division by zero")); 
	}
	else {

		int quotient{ 0 };
		int remainder{ 0 };

		do {
			quotient = dividend / divisor;
			remainder = dividend % divisor;
			if (remainder < abs(divisor) && remainder >= 0) break;
		} while (remainder > abs(divisor));

		std::cout << dividend << " / " << divisor << " = " 
			<< quotient << "\nRemainder = " << remainder << std::endl;
	}
}

bool tryAgain(char text[])
{
	char ch[10]; // to take upto 10 characters but only Y or N is relevant
	do {
		std::cout << text;
		std::cin >> ch;
		std::cin.get();

		for (auto &c : ch) {
			c = toupper(c);
		}
	} while (!(ch[0] == 'Y' || ch[0] == 'N'));
	return (ch[0] == 'Y');
}

I have a problem getting the right remainder when the dividend is a minus number
Sample output

Enter dividend(numerator) : -25
Enter divisor(denominator): 3

-25 / 3 = -8    // expected -9 according to lecturer's example
Remainder = -1  // should be 2 according to lecturer & theorem

Any fix?

[jonnin]

if it works on positives, the quick fix is to divide the absolute value positive numbers then reapply the correct sign at the end, which you can do with math or a couple of if statements.

If you want to fix the program to handle negatives, I will have to look at it later.
Seems way too complex for integer division. pseudocode for the KISS method..

while(abs(top) > abs(bottom))
subtract it.
what is left is remainder.
apply correct sign.
done.

Its not the most efficient, but if you want efficient, you write x/y and x%y and let the cpu do it.

[helios]

Your results are not inconsistent. It must be true that (quotient*divisor+remainder = dividend), and (-8)*3+(-1) is indeed equal to -25.
In your implementation (0 <= |remainder| < divisor), so if (remainder < 0) then (0 <= remainder + divisor < divisor) holds.

quotient*divisor+remainder = dividend
(quotient-1)*divisor+(remainder+divisor) = dividend

In other words, if you see that you're about to return a negative remainder, simply decrement quotient and add divisor to the remainder.

[longberns]

Thanks guys for taking a look at the work.
@helios, according to your suggestion

if you see that you're about to return a negative remainder, simply decrement quotient and add divisor to the remainder.

i modified the code to be

void divide(int dividend, int divisor)
{
	if (divisor == 0) { 
		throw(std::invalid_argument("Exception: Division by zero")); 
	}
	else {

		int quotient{ 0 };
		int remainder{ 0 };

		do {
			quotient = dividend / divisor;
			remainder = dividend % divisor;

			if (remainder < 0) {
				--quotient;
				remainder += divisor;
			}
			//if (remainder < abs(divisor) && remainder >= 0) break;
		} while (remainder < 0 && remainder > abs(divisor));
		
		std::cout << dividend << " / " << divisor << " = "
			<< quotient << "\nRemainder = " << remainder << std::endl;
	}
}

With this, i get

// NB: expected is what the lecturer gives as expected solution to the problem

25 / 3 = 8          // as expected
Remainder = 1   // as expected

-25 / 3 = -9      // as expected
Remainder = 2  // as expected

25 / -3 = -8        // as expected
Remainder = 1   // as expected

-25 / -3 = 7        // expected 9
Remainder = -4   // expected 2

It is true that

 
7 * (-3) + (-4) = -25  // and that
9*(-3) + 2 = -25 

Why does my lecturer expect(prefer) the first to the second? Is it because it is called "discrete mathematics" that things have to be different or there is any backing to this?

The course is actually called "Discrete mathematics for programmers". Do programmers have to change the way mathematics is?

Thanks in advance for your inputs

[helios]

Notice that what I said above only applies if (0 <= |remainder| < divisor). If (divisor < 0) that can't apply. There's an adjustment very similar to what I said earlier, but I'll let you figure it out, because it's not too difficult.

Why does my lecturer expect(prefer) the first to the second?

There are several ways to define division for negative operands.
https://en.wikipedia.org/wiki/Modulo_operation#/media/File:Divmod.svg
Your original implementation was probably using truncated division, while your lecturer was using Euclidean division.

[jonnin]

discrete math is what it is, but there is a proofs version, a theoretical approach, and there is undergrad basics, and there is a programmer centric approach where you write code (something a math major may not be able to do), etc. The math does not change, but you can look at it differently.

What your professor prefers is hard to answer. I had a professor blow his stack and have a meltdown hissyfit because I used the multiplication (chain rule) for derivatives instead of the 3 page long division "formula". I had a stern lecture from my physics prof on doing my exam with algebra because "its a calculus based course" but the problems did not justify the extra time and energy. Professors are a weird breed.

[longberns]

@jonin. Got it. It boils down to one's background and intentions.

@helios, i don't think the "it is not too difficult" to fix that code to work as expected. I have tried to change many parts of it but i still not get it.

[helios]

Think about it. (remainder < 0 && divisor < 0) so (remainder + divisor) is more negative than (remainder). You want a positive or zero (remainder) and less than |divisor|. Say... (remainder - divisor).

if divisor < 0:
quotient*divisor + remainder = dividend
(quotient + 1)*divisor + (remainder - divisor) = dividend

if divisor > 0:
quotient*divisor + remainder = dividend
(quotient - 1)*divisor + (remainder + divisor) = dividend

[longberns]

I still haven gotten the "fix" when both numerator and denominator are negative. I guess i will leave the solution as is. It gives the right answer anyway.

[48T7M4Gy]

Not rigorously tested but gives the same results as the prof. FWIW :)

#include <iostream>

int ABS(int);
int DIV(int, int);
int REM(int, int);

void display(int, int, int, int);

int main()
{
    int a = -25;    // dividend
    int d = -3;     // divisor
    
    int quotient = 0;
    int remainder = 0;
    
    
    if(a > 0 and d > 0)
    {
        quotient = DIV(a,d);
        remainder = REM(a,d);
    }
    else if(a < 0 and d > 0)
    {
        quotient = -DIV(ABS(a),d) - 1;
        remainder = -REM(ABS(a),d) + d;
    }
    else if(a > 0 and d < 0)
    {
        quotient = -DIV(a, ABS(d));
        remainder = REM(a,ABS(d));
    }
    else
    {
        quotient = DIV(ABS(a),ABS(d)) + 1;
        remainder = -REM(ABS(a),ABS(d)) - d;
    }
    
    display(a,d, quotient, remainder);
    
    return 0;
}

// absolute value
int ABS(int n)
{
    if (n < 0)
        return 0 - n;
    else
        return n;
}

// integer division
int DIV(int aa, int dd)
{
    int result{0};
    
    while(aa - dd >= 0)
    {
        aa -= dd;
        result++;
    }
    
    return result;
}

// remainder
int REM(int aa, int dd)
{
    return aa - DIV(aa,dd) * dd;
}

void display(int aa, int dd, int qq,  int rr)
{
    
    std::cout
    << " dividend a: " << aa << '\n'
    << "  divisor d: " << dd << "\n\n"
    << " quotient q: " << qq << '\n'
    << "remainder r: " << rr << '\n';
    
    if( aa == dd * qq + rr)
    {
        std::cout << aa << " = (" << dd << " x " << qq << ") + " << rr << '\n';
    }
    else
        std::cout << "Error\n";
}

[longberns]

@kemort
Thanks for the closer look. This works. Evidently, the problem was not as easy as i had imagined.
Many thanks to all who took a look at the problem.
SOLVED

What do i do for the program to compile in VS (VS Enterprise 2017)? It seems as if the and is not recognized.

[48T7M4Gy]

use && instead

[longberns]

I actually had done so. I was just wondering why and didn't work for me.
Thanks again.

[coder777]

vs does not recognize 'and' as a keyword. To make it work

#include <iso646.h>