I. In-Class Exercises

Programming Exercises

1. High-Precision Addition: L3011

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 addition is the most fundamental type of high-precision arithmetic. Its approach is exactly the same as manual column addition: add digit by digit starting from the ones place, and carry one to the next higher digit when the sum reaches ten or more.

✨ Algorithm Principle

The implementation steps for high-precision addition 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. This allows us to break through the digit limit of basic data types.
2. Reverse storage into array: Store each digit in reverse order into an array. The purpose of reverse storage is to make array index 0 correspond to the ones place, making it convenient to start calculations from the lowest digit and handle carries.
3. Add digit by digit with carry: Complete the digit-by-digit addition from low to high, handling carries during the process. If the sum at any digit is greater than or equal to 10, carry 1 to the next higher digit and keep only the ones digit at the current position.
4. Output result in reverse: Output the digit-by-digit addition result in reverse order to restore the normal number sequence.

✨ Code Implementation

Below is the complete implementation of high-precision addition, including three core functions: string-to-array conversion, digit-by-digit addition, and result output:

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 characters from the end of string to digits, stored at the beginning of 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 addition of two numbers, result stored in result array, len is the result length
21void addition(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];  // Add corresponding digits plus any previous carry
24        if (result[i] >= 10) {       // Check if carry is needed
25            result[i + 1]++;         // Carry
26            result[i] -= 10;         // Keep only the ones digit at current position
27        }
28    }
29    if (result[len] != 0) {  // Check for final carry; if present, increase result length by 1
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;  // Read two large numbers
39    int len1 = s1.length();  // Length of the first string
40    int len2 = s2.length();  // Length of the second string
41    convert(a1, s1);  // Convert the first string to integer array
42    convert(a2, s2);  // Convert the second string to integer array
43
44    int result[105] = {0};  // Array to store the result, initialized to 0
45    int len = max(len1, len2);  // Calculate the initial length of the result array
46
47    addition(a1, len1, a2, len2, result, len);  // Perform addition
48
49    print(result, len);  // Print the result
50    return 0;
51}

✨ Execution Example

Take the calculation of 385 + 97 as an example:

Step 1: String storage

• Input s1 = "385", s2 = "97"

Step 2: Reverse storage into array

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

Step 3: Add digit by digit with carry (len = max(3, 2) = 3)

result[] = {2, 8, 4}, len = 3

Step 4: Reverse output

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

Verification: 385 + 97 = 482, correct.

✨ Problem-Solving Steps

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

1. Determine if high precision is needed: Check the data range. If the number of digits exceeds 18 (the limit of long long), high precision is needed.
2. Read input: Read large numbers using string.
3. Reverse conversion: Store the string in reverse into an int array. Note that characters '0' through '9' need to have '0' subtracted to convert to digits.
4. Determine result length: The initial length is the longer of the two numbers.
5. Add digit by digit: Starting from index 0, add corresponding digits, carrying 1 when the sum reaches 10.
6. Check for carry at the highest digit: If there is a carry at the highest digit, increase the result length by 1.
7. Output in reverse: Output from the highest digit to the lowest.

✨ Common Mistakes

• Array too small: Adding two 100-digit numbers may produce a 101-digit result. The array should be at least max_digits + 2 in size.
• Forgetting to initialize the array to 0: Uninitialized values will cause garbage data to participate in calculations, producing wrong results.
• Forgetting to subtract '0' when converting characters to digits: s[i] is a character with an ASCII value (e.g., '3' is 51). You must subtract '0' (48) to get the digit 3.
• Reversing storage direction incorrectly: Array index 0 should store the ones digit (the last character of the string), not the highest digit.
• Incomplete carry handling: Only handling carries inside the loop but forgetting to check whether the highest digit still has a carry.

III. Homework

Programming Exercises

1. Big Integer Addition: L3012