karatsuba 在 c++ 中不用 std::string 是因字符串操作引发频繁内存分配与拷贝，拖慢性能；应改用低位在前的 std::vector，配合适当递归基（如 32）、中间结果复用、安全移位（resize+fill）及实测调优切回朴素乘法的阈值。
为什么 Karatsuba 在 C++ 里不直接用 std::string 拼数字
因为字符串模拟进位、逐位转 int、反复 push_back 和 substr 会触发大量内存分配和拷贝，实际跑起来比朴素 O(n²) 乘法还慢。Karatsuba 的分治收益全被字符串开销吃掉了。
实操建议：
- 用
std::vector<int></int>存数字的「低位在前」形式（比如123存为{3,2,1}），避免越界检查和反转 - 所有加法、减法、移位（即补零）都用原地
resize+ 循环完成，不新建容器 - 递归基设为长度 ≤ 32 —— 太小导致函数调用压栈开销占比高，太大则分治优势没体现出来
Karatsuba 递归中三个乘积怎么避免重复计算
标准公式是：xy = a·c·10^(2m) + ((a+b)·(c+d) - a·c - b·d)·10^m + b·d，其中 a,b,c,d 是拆分后的高位/低位。关键不是“怎么算”，而是“怎么复用中间结果”。
常见错误现象：每次递归都独立算 a+b 和 c+d，但这两个向量加法本身就有 O(n) 成本，且 a+b 可能比 a 或 b 长一位，导致后续所有操作都要多处理一位。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 先统一补齐
a,b,c,d到相同长度（用resize填 0），再算a+b和c+d - 把
a+b和c+d的结果缓存在局部变量里，后面三次乘法全部复用，不重新构造 - 注意：
(a+b)·(c+d)的结果长度可能达 2n+2，而a·c和b·d最多 2n，做减法时必须按最大长度对齐，否则高位截断
C++ 中如何安全做 vector 移位（等价于 ×10^k）而不爆内存
“移位”在这里指大整数乘以 10 的整数次幂，对应十进制下末尾补零。但直接 insert(begin(), k, 0) 是错的 —— 它补的是高位零，而我们存的是低位在前，该往末尾 insert(end(), k, 0)。
性能影响明显：如果每次乘法都新建一个两倍长的 vector，再拷贝数据，就退化成 O(n² log n)。更糟的是，递归深度约 log₂(n)，每层都这样干，内存峰值会翻倍增长。
实操建议：
- 用
resize扩容，然后std::fill填零，比insert快一个数量级 - 移位后记得清理前导零（即末尾连续的 0），否则下次拆分时长度误判，递归失控
- 不要在递归函数里用
std::move试图优化返回值 —— 返回局部vector编译器自动 RVO，强行move反而阻止优化
什么时候该切回朴素乘法而不是继续递归
不是长度越小越好切。测过主流编译器（GCC 12+/Clang 15+）在 x86-64 上，当数字长度 ≤ 16 位十进制（即 vector size ≤ 16）时，朴素三层循环反而比 Karatsuba 快 2–3 倍。原因很实在：函数调用开销 > 分治节省的乘法次数。
兼容性影响：不同 CPU 对小数组的 cache 行命中率差异大。ARM64 上拐点可能是 24，而某些嵌入式平台甚至要到 64 才值得分治。
实操建议：
- 把递归基写成可配置常量，比如
const int KARATSUBA_CUTOFF = 32;，上线前用真实数据集压测调优 - 别用
if (len 这种硬编码 —— 要考虑 <code>a和b长度不同时，应取max(a.size(), b.size())判断 - 如果输入含大量前导零（比如从文件读的字符串未 trim），务必先
trim_leading_zeros，否则长度误判导致永远不触发朴素路径
真正卡住性能的往往不是算法逻辑，而是 vector 的 resize 策略、零值清理时机、以及递归基在不同硬件上的漂移。跑不通的时候，先打个 std::cerr 看看实际递归了多少层。
