Division is a basic mathematical operation that we often use in our daily lives. Although we can easily perform divisions using predefined functions or libraries, it is important to know how a division algorithm works and how to implement it on our own.

In mathematics the division algorithm is stated as follows:

The above theorem defines a way to calculate the quotient and remainder of a division, but it does not seem to be an algorithm itself. However, its mathematical approach can be useful in developing an efficient division algorithm. The idea is to apply the concepts of the theorem to create a systematic and repetitive process that allows dividing two numbers and obtaining the desired result. In this way, we can use logic and mathematics to solve practical problems and apply theory in practice.

Explanation of the division algorithm for integers

Before implementing the algorithm, let’s review how manual division is performed, also considering negative numbers. We will take the division of 17 by 5 as an example and then explain how to handle negative cases.

1. Initialization: We start with a dividend of 17, a divisor of 5, the quotient at 0, and the remainder equal to the dividend.

2. Main loop: While the absolute value of the remainder is greater than or equal to the absolute value of the divisor, we perform the following actions: subtract the absolute value of the divisor from the absolute value of the remainder and increment the absolute value of the quotient by one. In our example, since $|17| \geq |5|$, we subtract the absolute value of the divisor from the absolute value of the remainder: 17 - 5 = 12. Then, we increase the quotient by 1: 0 + 1 = 1. We repeat the loop until the condition is no longer met. The sequence of these steps is shown in the following iteration table:

   Iteration	Dividend	Divisor	Quotient	Remainder
   1	17	5	0	17
   2	17	5	1	12
   3	17	5	2	7
   4	17	5	3	2

3. At the end, the absolute value of the quotient is 3, and the remainder is 2.

Handling Negative Numbers in Division

When performing division with negative numbers, it is important to follow a few additional rules to correctly determine the sign of the quotient and how to handle the remainder. The first step is to determine the sign of the result: if both the dividend and the divisor have the same sign, whether both are positive or both negative, the quotient will be positive. If the signs are different, the quotient will be negative. This rule applies regardless of the specific values of the numbers involved.

Once the sign of the quotient is determined, the next step is to work only with the absolute values of the numbers. This way, we focus on the magnitude of the numbers without temporarily worrying about the sign. The division process—repeatedly subtracting the divisor from the dividend and counting how many times this can be done—remains exactly the same as in the case of positive numbers.

After completing the division, we adjust the sign of the quotient as determined earlier. However, the remainder always retains the same sign as the original dividend. This is important because while the quotient's sign may change according to the absolute values, the remainder must reflect the sign of the number being divided.

Example of Divisions with Negative Numbers

Let’s see how this process works in some concrete examples. First, take the case of -17 divided by 5. Since the dividend is negative and the divisor is positive, the quotient will be negative. We work with the absolute values, dividing 17 by 5 in the usual way. This gives us a quotient of 3 and a remainder of 2, but since we determined at the beginning that the quotient must be negative, the final result is: quotient = -3, remainder = -2.

Now, consider the inverse case: 17 divided by -5. Here, the dividend is positive, and the divisor is negative, which again tells us the quotient will be negative. Following the same process, we get a quotient of 3 and a remainder of 2, but we adjust the sign of the quotient to obtain: quotient = -3, remainder = 2.

Finally, take the case of -17 divided by -5. Since both numbers are negative, the quotient will be positive. After performing the division with the absolute values, we get a quotient of 3 and a remainder of 2, and since the quotient must be positive, the result is: quotient = 3, remainder = -2.

Special Case: Dividend Less Than Divisor

A special case occurs when the absolute value of the dividend is less than that of the divisor. In this scenario, the quotient is always 0, as the divisor cannot be subtracted from the dividend even once. The remainder will simply be the same value as the dividend, as no full division takes place. For example, dividing 3 by 5 results in a quotient of 0 and a remainder of 3. The same happens if the dividend is negative: -3 divided by 5 gives a quotient of 0 and a remainder of -3. If the divisor is also negative, as in 3 divided by -5, the quotient remains 0, but the remainder stays positive, that is, 3. Finally, in -3 divided by -5, the quotient is 0, and the remainder is -3, following the same logic.

Implementation of the division algorithm in Python

Next, we present a pseudocode that describes the division algorithm for integers, including the handling of negative numbers.

An example of code in Python that implements the above process is as follows:

def division(dividend, divisor):
    if divisor == 0:
        raise ValueError("Divisor cannot be zero")

    # Determine the sign of the result more explicitly
    if (dividend >= 0 and divisor > 0) or (dividend <= 0 and divisor < 0):
        sign = 1
    else:
        sign = -1

    # Work with absolute values
    dividend = abs(dividend)
    divisor = abs(divisor)

    quotient = 0
    remainder = dividend

    while remainder >= divisor:
        remainder -= divisor
        quotient += 1

    # Adjust the sign of the quotient and remainder
    quotient *= sign
    remainder *= -1 if dividend < 0 else 1

    return quotient, remainder

# Test the algorithm
dividend = int(input("Enter the dividend: "))
divisor = int(input("Enter the divisor: "))
quotient, remainder = division(dividend, divisor)
print("Quotient:", quotient)
print("Remainder:", remainder)

This code performs the division of two numbers entered by the user. First, the variables quotient y remainder, are defined, and the value of the dividend is assigned to remainder. hen, a while loop is used that runs while remainder is greater than or equal to divisor. EOn each iteration, divisor is subtracted from remainder and the value of quotient s increased by one. Finally, the values of quotient and remainder are returned as the result of the division() function.

When this code is executed and two numbers are provided as input, we will obtain the quotient and the remainder of the division. For example, if we divide $15$ by $3$, the result would be a quotient of $5$ and a remainder of $0$. If we divide $17$ by $3$, the result would be a quotient of $5$ and a remainder of $2$.

It is important to note that the division algorithm we have implemented is a basic and effective way of performing divisions, but there are other more advanced and efficient ways. However, this example is useful for understanding the basic concepts behind division and how to apply them in practice with a programming language.

I hope this helps you understand how a division algorithm works and how to implement it in Python without using libraries. If you have any additional questions, feel free to ask.

References