I. In-Class Exercises

Programming Exercises

1. High-Precision Multiplication: L3031

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 multiplication simulates the process of manual long multiplication. Unlike addition and subtraction, multiplication requires multiplying each digit of one number with each digit of the other, accumulating the results at the corresponding positions, and then processing carries uniformly at the end.

✨ Algorithm Principle

The implementation steps for high-precision multiplication 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, making it convenient to start calculations from the lowest digit.
3. Multiply digit by digit and accumulate: Complete the digit-by-digit multiplication from low to high. The key formula is result[i+j] += a1[j] * a2[i], meaning the product of the j-th digit of the first number and the i-th digit of the second number is accumulated at the (i+j)-th position of the result. After all digit multiplications are done, carries are processed uniformly.
4. Remove leading zeros and output: Remove leading zeros and output the result in reverse order. Note that the product of two n-digit numbers has at most 2n digits.

✨ Code Implementation

Below is the complete implementation of high-precision multiplication. The core lies in the double loop for digit-by-digit multiplication and the unified carry processing:

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 calculation starting from the lowest 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 multiplication using the traditional multiplication algorithm
21void multiplication(int a1[], int len1, int a2[], int len2, int result[], int &len) {
22    for (int i = 0; i < len2; i++) {
23        for (int j = 0; j < len1; j++) {
24            result[i + j] += a1[j] * a2[i]; // Multiply corresponding digits and add to the appropriate position in result
25        }
26    }
27    for (int i = 0; i < len; i++) {
28        result[i + 1] += result[i] / 10; // Process carry
29        result[i] %= 10; // Keep only the ones digit
30    }
31    while (result[len - 1] == 0 && len > 1) { // Remove leading zeros, but keep at least one digit
32        len--;
33    }
34}
35
36int main() {
37    string s1, s2;
38    int a1[105] = {0}; // Array to store the first number, initialized to 0
39    int a2[105] = {0}; // Array to store the second number, initialized to 0
40    cin >> s1 >> s2;
41    int len1 = s1.length(); // Length of the first string
42    int len2 = s2.length(); // Length of the second string
43    convert(a1, s1); // Convert the first string to integer array
44    convert(a2, s2); // Convert the second string to integer array
45
46    int result[205] = {0}; // Array to store the result, initialized to 0, length is the sum of both lengths
47    int len = len1 + len2; // Set initial result length to the sum of both lengths
48
49    multiplication(a1, len1, a2, len2, result, len); // Perform multiplication
50
51    print(result, len); // Print the result
52    return 0;
53}

✨ Execution Example

Take the calculation of 123 × 45 as an example:

Step 1: Reverse storage into array

• a1[] = {3, 2, 1} (ones digit 3, tens digit 2, hundreds digit 1 of 123)
• a2[] = {5, 4} (ones digit 5, tens digit 4 of 45)

Step 2: Multiply digit by digit and accumulate

Core formula: result[i+j] += a1[j] * a2[i]

Iterate through each digit of a2 (i) and multiply with each digit of a1 (j):

After multiplication: result[] = {15, 22, 13, 4, 0}

Step 3: Unified carry processing

After carry processing: result[] = {5, 3, 5, 5}

Step 4: Reverse output

• Output 5535

Verification: 123 × 45 = 5535, correct.

✨ Problem-Solving Steps

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

1. Determine the result array size: If the two numbers have n and m digits respectively, the product has at most n+m digits. The array should be at least n + m + 1 in size.
2. Reverse conversion: Store both strings in reverse into arrays.
3. Double loop multiplication: The outer loop iterates through each digit of the second number, and the inner loop iterates through each digit of the first number, accumulating the product at result[i+j]. At this point, values in result may be greater than 9, which is normal.
4. Unified carry processing: After all multiplications, process carries uniformly from low to high. Each position keeps the ones digit (%10), and the carry value (/10) is added to the higher position.
5. Remove leading zeros: Check from the highest position and remove extra zeros.
6. Reverse output: Output the result from high to low.

✨ Common Mistakes

• Result array too small: An n-digit number times an m-digit number can produce at most n+m digits. If the array is only sized for n or m, array out-of-bounds will occur.
• Wrong accumulation position: The product of a1[j] * a2[i] should be accumulated at result[i+j], not result[i] or result[j]. This formula corresponds to the long multiplication rule: "the product of the i-th digit and the j-th digit goes to the (i+j)-th position."
• Processing carries before completing multiplication: The correct approach is to complete all multiplication accumulations first, then process carries uniformly. Processing carries while multiplying makes the logic more complex and error-prone.
• Forgetting to handle multiplication by 0: If one of the numbers is 0, the result should output 0, but excessive leading zero removal might cause nothing to be output.
• Carry loop range too small: The carry processing loop should cover up to len-1 (i.e., n+m-1), otherwise carries at higher positions may be lost.

III. Homework

Programming Exercises

1. Big Integer Multiplication: L3032