I. In-Class Exercises

Programming Exercises

1. High-Precision Subtraction: L3021

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 subtraction is similar to addition, simulating the process of manual column subtraction. The difference is that subtraction requires additional handling of borrowing and negative results.

✨ Algorithm Principle

The implementation steps for high-precision subtraction 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. Comparison and sign handling: Compare the two high-precision numbers. If the minuend is smaller than the subtrahend, record a negative sign and swap the two numbers, ensuring we always subtract the smaller number from the larger one.
3. Reverse storage into array: Store each digit in reverse order into an array, making it convenient to start calculations from the lowest digit.
4. Subtract digit by digit with borrowing: Complete the digit-by-digit subtraction from low to high, handling borrowing during the process. If a digit is not large enough to subtract, borrow 1 from the next higher digit (equivalent to adding 10 to the current digit).
5. Remove leading zeros and output: Remove leading zeros from the result and output the digit-by-digit subtraction result in reverse order.

✨ Code Implementation

Below is the complete implementation of high-precision subtraction. Note the special handling when the minuend is smaller than the subtrahend:

1#include <iostream>
2using namespace std;
3
4// Convert digits from string s into integer array a, stored 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'; // Convert each character from back to front into an integer and store in array
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 subtraction of two numbers, result stored in result array, len is the result length
21void subtraction(int a1[], int len1, int a2[], int len2, int result[], int &len) {
22    for (int i = 0; i < len; i++) {
23        result[i] += a1[i] - a2[i]; // Subtract corresponding digits plus any previous borrow
24        if (result[i] < 0) { // Check if borrowing is needed
25            result[i + 1]--; // Borrow
26            result[i] += 10; // Add base 10 to current digit
27        }
28    }
29    while (result[len - 1] == 0 && len > 1) { // Remove leading zeros, but keep at least one digit
30        len--;
31    }
32}
33
34int main() {
35    string s1, s2;
36    int a1[105] = {0}; // Array to store the first number, initialized to 0
37    int a2[105] = {0}; // Array to store the second number, initialized to 0
38    cin >> s1 >> s2;
39
40    if (s1.length() < s2.length() || (s1.length() == s2.length() && s1 < s2)) {
41        swap(s1, s2); // If s1 is smaller than s2, swap them to ensure a positive result
42        cout << '-'; // Output negative sign
43    }
44    int len1 = s1.length(); // Length of the first string
45    int len2 = s2.length(); // Length of the second string
46    convert(a1, s1); // Convert the first string to integer array
47    convert(a2, s2); // Convert the second string to integer array
48
49    int result[105] = {0}; // Array to store the result, initialized to 0
50    int len = len1; // Set initial result length to len1
51
52    subtraction(a1, len1, a2, len2, result, len); // Perform subtraction
53
54    print(result, len); // Print the result
55    return 0;
56}

✨ Execution Example

Take the calculation of 503 - 287 as an example:

Step 1: String storage

• Input s1 = "503", s2 = "287"

Step 2: Comparison

• s1.length() == s2.length() and s1 > s2 ("503" > "287"), no swap needed, result is positive.

Step 3: Reverse storage into array

• a1[] = {3, 0, 5} (ones digit 3, tens digit 0, hundreds digit 5)
• a2[] = {7, 8, 2} (ones digit 7, tens digit 8, hundreds digit 2)

Step 4: Subtract digit by digit with borrowing (len = 3)

result[] = {6, 1, 2}, len = 3

Step 5: Remove leading zeros and output

• result[2] = 2 is not zero, no leading zeros to remove.
• Reverse output: 216

Verification: 503 - 287 = 216, correct.

Another example with a negative result: Calculate 123 - 456

• s1.length() == s2.length() and s1 < s2 ("123" < "456"), swap so s1="456", s2="123", output negative sign -.
• Calculate 456 - 123 = 333, final output -333.

✨ Problem-Solving Steps

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

1. Determine the size relationship: First compare the two large numbers. The comparison rule is: compare lengths first, the longer one is larger; if lengths are equal, compare the strings lexicographically.
2. Determine the sign: If the minuend is smaller than the subtrahend, record a negative sign and swap the two numbers, ensuring we always subtract the smaller from the larger.
3. Reverse conversion: Store both strings in reverse into arrays.
4. Subtract digit by digit: Starting from the lowest digit, subtract corresponding digits. If the current digit is not large enough (result is negative), borrow 1 from the higher digit and add 10 to the current digit.
5. Remove leading zeros: The higher digits of the result may have extra zeros. Remove them from high to low, but keep at least one digit (output "0" when the result is 0).
6. Output the result: If a negative sign was recorded earlier, output the negative sign first, then output the result array in reverse.

✨ Common Mistakes

• Forgetting to handle the negative case: When the minuend is smaller than the subtrahend, if you don't swap and output a negative sign, the calculation result will be wrong.
• Incorrect size comparison: You cannot directly use < to compare string values of two large numbers (string comparison is only equivalent to numerical comparison when lengths are the same). You must compare lengths first, then compare strings.
• Not removing leading zeros: For example, 1000 - 999 = 001. Without removing leading zeros, the output would be 001 instead of 1.
• Over-removing leading zeros: When the result is 0 (e.g., 100 - 100), at least one digit must be kept, otherwise nothing is output.
• Forgetting to subtract 1 from the higher digit when borrowing: The borrowing operation consists of two steps: add 10 to the current digit and subtract 1 from the next higher digit. Both are essential.

III. Homework

Programming Exercises

1. Big Integer Subtraction: L3022