普通高精度乘法不能直接套fft，因fft处理复数点值乘法，而高精度是整数系数多项式相乘，直接映射会导致浮点舍入误差使低位错乱；需倒序压位、补零至2的幂、逆变换后手动进位三步转换才能安全使用。

为什么普通高精度乘法不能直接套FFT

因为FFT处理的是复数序列的点值乘法，而高精度乘法本质是十进制（或压位后）的整数系数多项式相乘。直接把字符串每位当系数喂给FFT，会因浮点精度误差导致低位错乱——比如999 * 999本该得998001，但用双精度FFT在长度较大时可能算出998000或998002。这不是算法逻辑错，而是std::complex<double></double>在累加、逆变换后截断时引入的舍入误差。

FFT加速高精度乘法的三步关键转换

必须做三件事才能让FFT“安全”用于整数乘法：

• 倒序存储 + 压位：把输入字符串按低位在前存入数组，并以base=10000（即每项存4位十进制）压位，减少数组长度，降低FFT点数和误差累积
• 补零到2的幂：用std::bit_ceil(la + lb)（C++20）或手动计算下一个2的幂，对两个系数数组补零，否则迭代FFT会崩溃或结果未定义
• 逆变换后手动进位：FFT输出是近似实数数组，需先四舍五入为long long，再从低位开始逐位进位（c[i] += c[i-1] / base），不能依赖浮点结果直接输出

容易被忽略的精度与内存陷阱

这几个点不处理，代码跑通但结果随机出错：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• cv::dft()不做cv::DFT_SCALE标志，逆变换结果会放大n倍；手写迭代FFT漏掉最后除以n，同理
• 用std::vector<:complex>></:complex>传给FFTW？不行——FFTW要求内存对齐，必须用fftw_alloc_complex(n)分配，否则AVX指令下大概率崩溃
• 输入含前导零但没清理，压位后高位全零，FFT点数虚高，耗时翻倍且误差放大
• 没检查abs(c[i].imag()) 就取实部，某些平台FFT中间步骤虚部残留达<code>1e-12，截断后影响低位

什么时候该放弃FFT改回O(n²)模拟

不是所有大数都值得上FFT。真实项目里，以下情况直接用竖式更稳更快：

• 两数长度都 O(n²)实际更快
• 需要精确到个位且不允许任何误差（如金融结算）：FFT是近似算法，即使调高精度也难100%保个位
• 嵌入式或内存受限环境：FFT要开两倍长度的std::complex<double></double>数组，5000位数就要约 160KB，而竖式只需线性空间
• 只做一次乘法且后续无批量需求：FFT预处理（位逆序重排、蝶形参数计算）本身就有开销

真正发挥FFT价值的场景，是像HDU-1402那样，单次处理接近50000位的数，且对响应时间敏感——这时O(n log n)和O(n²)的差距是秒级和分钟级。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！