High Precision Arithmetic

1. Data Structure & Representation

Since standard CPU registers cannot hold these values, high-precision numbers are stored as arrays.

1.1 String to Array Conversion Input is typically received as a string. To facilitate calculation, it is converted into an integer array.

1.2 Little-Endian Storage (Reverse Order) Crucially, numbers are stored in reverse order. The least significant digit (unit place) is stored at index 0. * Input String: "12345" * Array Storage: A[0]=5, A[1]=4, A[2]=3, ...

Why Reverse? Arithmetic operations (addition, multiplication) propagate carries from lower to higher digits. Storing the unit place at index 0 allows the array to expand naturally towards higher indices without shifting elements.

2. High-Precision Addition

Principle: Simulation of columnar addition (vertical addition). Given two large integers \(A\) and \(B\): $\(C_i = A_i + B_i + \text{carry}\)$ $\(Result_i = C_i \pmod{10}\)$ $\(\text{New Carry} = \lfloor C_i / 10 \rfloor\)$

Implementation Logic: 1. Iterate from \(i = 0\) to \(\max(len_A, len_B)\). 2. Sum the current digits and the carry from the previous position. 3. Store the unit digit of the sum. 4. Update the carry. 5. If a carry remains after the loop, append it to the end.

3. High-Precision Multiplication

Principle: Convolutional simulation. The product of digit \(A[i]\) and \(B[j]\) contributes to the position \(C[i+j]\).

Mathematical relation: $\(C_{i+j} = C_{i+j} + (A_i \times B_j)\)$

Implementation Logic: 1. Initialize result array \(C\) to 0. 2. Use nested loops: iterate \(i\) through \(A\) and \(j\) through \(B\). 3. Accumulate \(A[i] \times B[j]\) into \(C[i+j]\). 4. Carry Pass: Iterate through array \(C\) once to handle carries (perform modulo 10 and division by 10) for every position. 5. Trim: Remove any leading zeros from the high-order end of the result.

4. Implementation (C Language)

#include <stdio.h>
#include <string.h>

#define MAXN 2005 // Define buffer size based on problem constraints

/**
 * High-Precision Multiplication: C = A * B
 */
void solve() {
    char s1[MAXN], s2[MAXN];
    int a[MAXN] = {0}, b[MAXN] = {0}, c[MAXN * 2] = {0};

    // 1. Input
    scanf("%s %s", s1, s2);
    int len1 = strlen(s1);
    int len2 = strlen(s2);

    // 2. Convert to Integer Array (Little-Endian / Reverse)
    for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';

    // 3. Multiplication Logic (Accumulate without carry first)
    // The product of index i and j contributes to index i+j
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

    // 4. Handle Carries
    int len = len1 + len2;
    for (int i = 0; i < len; i++) {
        if (c[i] > 9) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }

    // 5. Remove Leading Zeros
    while (len > 1 && c[len - 1] == 0) {
        len--;
    }

    // 6. Output (Reverse Print)
    for (int i = len - 1; i >= 0; i--) {
        printf("%d", c[i]);
    }
    printf("\n");
}

int main() {
    solve();
    return 0;
}

5. Complexity Analysis

Operation	Algorithm	Time Complexity	Space Complexity
Addition	Linear Scan	\(O(N)\)	\(O(N)\)
Multiplication	Naive (shown above)	\(O(N \times M)\)	\(O(N + M)\)
Multiplication	Karatsuba (Advanced)	\(O(N^{\log_2 3}) \approx O(N^{1.585})\)	\(O(N)\)
Multiplication	FFT (Fast Fourier Transform)	\(O(N \log N)\)	\(O(N)\)

\(N\) and \(M\) denote the number of digits.

6. Professional Optimization: Base Compression

In standard implementation, each array element stores 1 digit (Base 10). To improve performance and memory usage, Base Compression (or "Packing") is often used. Instead of storing 1, 2, 3, 4, we store chunks of digits in a single int or long long. * Base \(10^9\): Store 9 digits per array element. * Benefit: Reduces the number of operations by a factor of 9 (for addition) or 81 (for multiplication) and utilizes the full capacity of CPU registers.