I. In-Class Exercises

Programming Exercises

1. High-Precision Division: L3041

II. Knowledge Summary

✨ Core Concept

High-precision arithmetic refers to techniques in computer science and numerical computation that can handle and operate on very large numbers. In programming, ordinary integer types (such as int or long) have maximum value limits, and operations exceeding this range will overflow. To handle larger numbers, such as in large-number encryption, scientific computing, or economic model analysis, high-precision (big number) arithmetic is needed.

High-precision division simulates the process of manual long division. Unlike addition, subtraction, and multiplication which start from the lowest digit, division needs to compute the quotient digit by digit starting from the highest digit, while maintaining a remainder. The implementation here covers the case of dividing a high-precision number by a regular integer.

✨ Algorithm Principle

The implementation steps for high-precision division are as follows:

1. String storage: Use string variables to store the entire large number. Each character of the string can be directly mapped to a digit.
2. Reverse storage into array: Store each digit in reverse order into an array for uniform processing.
3. Compute quotient digit by digit from high to low: Starting from the highest digit, multiply the current remainder by 10 and add the current digit, then divide by the divisor to get the quotient for that position, and take the modulus to get the new remainder. This process is exactly the same as manual long division.
4. Remove leading zeros and output: Remove leading zeros and output the result in reverse order.

✨ Code Implementation

Below is the complete implementation of high-precision division (large number divided by regular integer):

1#include <iostream>
2using namespace std;
3
4// Convert digits from string s into integer array a in reverse order
5void convert(int a[], string s) {
6    int len = s.length(); // Get the string length
7    for (int i = 0; i < len; i++) {
8        a[i] = s[len - 1 - i] - '0'; // Store in reverse order for processing from the highest digit
9    }
10}
11
12// Print the number represented by integer array a, where digits are stored in reverse order
13void print(int a[], int len) {
14    for (int i = 0; i < len; i++) {
15        cout << a[len - 1 - i]; // Print array elements from back to front to display the number in correct order
16    }
17    cout << endl;
18}
19
20// Perform high-precision division
21void division(int a1[], int len1, int a2, int result[], int &len) {
22    int remainder = 0; // Initialize remainder
23    for (int i = len1 - 1; i >= 0; i--) {
24        remainder = remainder * 10 + a1[i]; // Multiply remainder by base 10 and add current digit
25        result[i] = remainder / a2; // Compute quotient for current position
26        remainder %= a2; // Update remainder
27    }
28    while (result[len - 1] == 0 && len > 1) { // Remove leading zeros, but keep at least one digit
29        len--;
30    }
31}
32
33int main() {
34    string s1;
35    int a1[105] = {0}; // Array to store the number, initialized to 0
36    int a2 = 0; // Store the divisor
37    cin >> s1 >> a2; // Read the dividend and divisor
38    int len1 = s1.length(); // Get the length of the dividend
39    convert(a1, s1); // Convert the dividend to integer array
40
41    int result[105] = {0}; // Array to store the result, initialized to 0
42    int len = len1; // Set initial result length to the dividend's length
43
44    division(a1, len1, a2, result, len); // Perform division
45
46    print(result, len); // Print the result
47    return 0;
48}

✨ Execution Example

Take the calculation of 1573 ÷ 6 as an example:

Step 1: Reverse storage into array

• a1[] = {3, 7, 5, 1} (ones digit 3, tens digit 7, hundreds digit 5, thousands digit 1 of 1573)
• a2 = 6 (regular integer divisor)
• len1 = 4

Step 2: Compute quotient digit by digit from high to low (from i=3 to i=0)

result[] = {2, 6, 2, 0}, remainder = 1

Step 3: Remove leading zeros

• result[3] = 0, len decreases from 4 to 3.
• result[2] = 2 is not zero, stop removing.

Step 4: Reverse output

• From result[2] to result[0], output 262

Verification: 1573 ÷ 6 = 262 remainder 1, correct.

Note that this process is exactly the same as manual long division:

1    0 2 6 2
2  --------
36 | 1 5 7 3
4    0         → 1÷6=0 remainder 1
5      1 2     → 15÷6=2 remainder 3
6        3 6   → 37÷6=6 remainder 1
7          1 2 → 13÷6=2 remainder 1

✨ Problem-Solving Steps

When you encounter a high-precision division problem, follow these steps:

1. Identify the division type: This lesson covers "large number divided by small number" (high-precision number divided by a regular integer). Dividing a large number by another large number requires a more complex algorithm.
2. Read input: Read the dividend using string and the divisor using int.
3. Reverse storage into array: Store each digit of the dividend in reverse into an array.
4. Calculate from the highest digit: Unlike addition, subtraction, and multiplication which start from the lowest digit, division starts from the highest digit. Maintain a remainder variable, and each time use remainder * 10 + current digit as the current dividend.
5. Compute quotient and remainder: The quotient at the current position = current dividend / divisor, new remainder = current dividend % divisor.
6. Remove leading zeros: The higher digits of the quotient may be 0 (like the thousands digit being 0 in the example above) and need to be removed.
7. Output result: Output the quotient in reverse. If the remainder is needed, it can be output separately.

✨ Common Mistakes

• Wrong direction: High-precision addition, subtraction, and multiplication all start from the lowest digit (index 0), but division starts from the highest digit (index len-1). This is the most common point of confusion for beginners.
• Remainder not carried forward correctly: At each step, the remainder must be multiplied by 10 before adding the next digit. Forgetting to multiply by 10 will produce completely wrong results.
• Not handling division by 0: In actual programming, you should check whether the divisor is 0 to avoid runtime errors.
• Improper leading zero handling: For example, 6 ÷ 12 gives a quotient of 0. If leading zeros are over-removed, nothing will be output. Ensure at least one digit is kept.
• Wrong result length: The initial result length for high-precision division should equal the number of digits in the dividend (unlike multiplication where it's the sum of both lengths), and is then shortened by removing leading zeros.

III. Homework

Programming Exercises

1. Division by 13: L3042