大整数乘法实现日志：从查表法到逐位运算

在我做项目时，遇到一个乘法问题，一算就报错Error。后来咨询大神才知道，这是运算规模超出乘法限度了。

使用基本类型如int或long会导致溢出。浮点数虽能表示大范围数值，但无法精确表示所有整数。

在处理超出基本数据类型范围的整数运算时（例如计算 12345678901234567890 * 98765432109876543210），我们必须自己实现算法。

本文将深入剖析一个基于 C++ 实现的大整数乘法程序，探讨其设计思路、核心算法与可优化之处。

整体架构与思路

大整数乘法通常通过模拟手工竖式计算实现，将每一位相乘并累加到对应位置，处理进位。例如，C语言代码中，将输入字符串转换为整数数组，逆序存储以便从低位开始计算，每一位相乘后累加到结果数组的对应位置，最后处理进位并逆序输出结果。

大整数乘法核心在于模拟手工竖式计算，通过逐位相乘并累加结果，最终处理进位。对于两个n位数，时间复杂度为O(n²)。

该程序的核心思想是模拟人类手算乘法的过程：

1. 将输入的大数字符串反转，以便从最低位开始计算。
2. 使用乘数的每一位去乘以被乘数的每一位，同时处理每一位的乘积和进位。
3. 将每次乘得的中途结果累加起来。
4. 处理最终结果的进位，并反转回高位在前的字符串表示，同时去除前导零。

程序主要由以下模块组成：

• 字符串反转 (strrev)
• 预计算查表 (table_pos, table_addition)
• 单比特乘法和进位处理 (bit_multiple, carry, bit_add)
• 大数加法 (add)
• 大数乘法 (multiple)
• 输入输出 (Input, main)

让我们逐模块进行解析。

模块解析与关键代码

1. 字符串反转函数 strrev

void strrev(char * source) {
    char * des;
    int len = strlen(source);
    des = (char*)malloc(sizeof(char) * (len + 1)); // 分配临时空间
    des[len] = '\0'; // 设置字符串结束符
    for (int i = 0; i < len; i++) {
        des[len - i - 1] = source[i]; // 逆序拷贝
    }
    strcpy(source, des); // 拷回原字符串
    free(des); // 释放临时空间
}

• 功能： 将输入的字符串原地反转。
• 分析： 此函数为算法做准备。因为手算乘法从最低位开始，而字符串存储数字是高位在前（例如 "123"）。反转后变成低位在前（"321"），极大简化了后续按索引顺序（[0] 开始）进行计算的逻辑。
• 注意： 该实现使用了动态内存分配 (malloc 和 free)，在 C++ 中通常更推荐使用 new[] 和 delete[]，或者直接使用 std::string 和 std::reverse。

2. 核心查表法：预计算矩阵

分治法优化：Karatsuba算法通过分治策略将时间复杂度从O(n²)降至O(n^1.59)。其核心是将大数拆分为高位和低位，通过三次递归乘法（AC、BD、(A-B)(D-C)）和加减法组合结果，减少乘法次数。例如，将X=A10^(n/2)+B和Y=C10^(n/2)+D相乘时，传统方法需4次乘法，而Karatsuba仅需3次。

在分治法中，预先计算小规模乘法的结果（如所有可能的m位小数相乘），存储为表格。当处理大数乘法时，直接查表获取结果，避免重复计算。例如，在Karatsuba算法中，若将大数分为m位块，预先计算所有m位小数的乘积，后续递归调用时直接引用，减少计算量。

char table_pos[10][10] = { ... }; // 个位数乘法结果表
char table_addition[10][10] = { ... }; // 个位数乘法进位表

• 功能： 这两个二维数组是程序的性能优化核心。它们预先计算了所有两个一位数（0-9）相乘的结果。
  • table_pos[a][b]： 存储 a * b 所得结果的个位数字。
  • table_addition[a][b]： 存储 a * b 所得结果的十位（进位）数字。
• 举例： 7 * 8 = 56。那么 table_pos[7][8] = '6', table_addition[7][8] = '5'。
• 优势： 避免了在密集循环中进行昂贵的 (a - '0') * (b - '0') % 10 和 (a - '0') * (b - '0') / 10 运算，直接用一次内存访问得到结果，以空间换时间。

3. 单比特运算与进位处理

在模拟竖式计算中，每一位相乘的结果可能超过基数（如十进制中的10），需将余数留在当前位，进位传递到高位。例如，C语言代码中，使用变量存储进位，每次相乘后更新结果数组和进位值，确保每一位数值正确。

void bit_multiple(char &pos, char &addition, const char factor1, const char factor2) {
    pos = table_pos[factor1 - '0'][factor2 - '0']; // 查表得个位
    addition = table_addition[factor1 - '0'][factor2 - '0']; // 查表得十位（进位）
}

void carry(char pre_addition, char &cur_pos, char &cur_addition) {
    cur_pos = cur_pos + pre_addition - '0'; // 将进位加到当前位
    if (cur_pos - '0' > 9) { // 如果当前位又产生新的进位
        cur_addition++; // 向更高位进位
        cur_pos -= 10; // 调整当前位
    }
}

• bit_multiple： 封装了查表操作，是乘法运算的原子操作。
• carry： 关键函数。它处理复杂的进位链。不仅处理乘法本身的进位 (addition)，还要处理之前步骤传递下来的进位 (pre_addition)。它确保 cur_pos 始终是一个一位的数字字符。

4. 大数加法 add

void add(char * num1, char * num2) {
    // ... 逻辑：将 num2 加到 num1 上，结果存储在 num1 中
    // 1. 遍历两个数字的每一位
    // 2. 对每一位调用 bit_add (其内部调用 carry) 进行相加和进位处理
    // 3. 处理两个数字长度不等时剩余的位数和可能的最高位进位
}

• 功能： 实现两个大数的加法。这是乘法算法中不可或缺的一部分，因为乘法最终体现为部分和的累加。
• 逻辑： 该函数仔细处理了 num1 和 num2 长度不同的情况，确保了进位能正确地向更高位传播。

5. 核心：大数乘法 multiple

void multiple(char* mul1, char* mul2, char * result) {
    strrev(mul1); // 反转被乘数
    strrev(mul2); // 反转乘数

    char result_basic[MAX_LENGTH] = {0}; // 初始化和（初始为0）
    char result_add[MAX_LENGTH] = {0}; // 临时存储当前计算的部分积

    for (int i = 0; i < strlen(mul2); i++) { // 遍历乘数的每一位
        // ... 内部循环：用乘数的第 i 位 mul2[i] 去乘以被乘数的每一位 mul1[j]
        // 对于每一对位 (j, i)，计算乘积并通过 carry 处理进位
        // 将计算得到的部分积（已处理完所有进位）存储在 result_add 中，
        // 其有效位数是 strlen(mul1)，并在末尾可能有一位进位。

        // 将当前部分积 result_add 累加到总结果 result_basic 上
        add(result_basic, result_add);
    }

    strrev(result_basic); // 将总结果反转回高位在前
    // ... 去除结果的前导零
    cout << result_basic << endl; // 输出最终结果
}

流程如下：

1. 反转： 将两个操作数反转，转为低位在前模式。
2. 初始化： result_basic 初始化为0，用于累积所有部分和。
3. 双重循环：
   • 外层循环： 遍历乘数 mul2 的每一位。
   • 内层循环： 对于乘数的当前位 i，遍历被乘数 mul1 的每一位 j，计算 mul1[j] * mul2[i]，并与之前的进位相加，得到当前位的值和新进位。这步生成一个部分积（result_add）。
4. 累加： 将当前计算出的部分积加到总结果 result_basic 上。
5. 后处理： 将所有结果反转回正常顺序，并去除可能存在的无意义的前导零。

总结与评价

大整数乘法通过模拟竖式计算实现，查表法与分治算法（如Karatsuba）可显著优化性能。进位处理是核心细节，需确保每次累加后正确传递进位。代码优化可从进制转换、并行计算和内存管理入手，同时注意符号与前导零的处理。

1. 优点：

• 思路清晰： 完美复现了手算乘法的流程，易于理解。
• 性能优化： 使用查表法替代实时计算，是亮点所在，显著提升了核心运算的速度。
• 模块化设计： 将进位、加法、乘法等操作封装成函数，结构清晰。

2. 可改进之处：

• 内存与安全性： 使用原始 char* 和 malloc，存在缓冲区溢出的风险（例如，结果超出 MAX_LENGTH）。现代 C++ 应优先使用 std::string 或 std::vector<char>，它们能动态管理内存，更安全。
• 代码健壮性： 缺乏输入验证。如果输入字符串包含非数字字符，程序会出错。
• 效率瓶颈： 算法复杂度为 O(n²)，这是大数乘法的固有特性。但对于极大数，有更高效的算法（如 Karatsuba 算法、FFT based 算法）。
• 代码风格： 部分变量命名可更具描述性（如 result_basic 可改为 sum_total），并且存在一些调试用的注释代码 cout。
• 结果返回： 函数 multiple 声称将结果存入 result 参数，但实际实现中直接 cout 了 result_basic，这是一个逻辑不一致的地方。应改为将处理好的字符串拷贝到 result 中。

3. 深入思考 尽管有可优化之处，这段代码的核心价值在于清晰地展示了大数运算的基本原理，并引入了查表法这一重要优化思想。它为我们理解更复杂、更高效的算法打下了坚实的基础。对于学习者而言，读懂并调试这样的代码，对深入理解计算机如何表示和操作数据大有裨益。