Python中两数相乘的实现方式及对应时间复杂度是多少

Python的数值类型分两类，乘法实现路径完全不同：

• 对于固定位宽的类型：包括小整数（数值落在机器字长范围内，64位系统下通常是绝对值小于2^63的整数）、所有float双精度浮点数，乘法直接调用CPU对应的硬件乘法指令完成，没有额外的软件层计算逻辑。
• 对于超出机器字长的任意精度整数（也就是Python默认int类型支持的无溢出大整数），CPython内部会把整数拆成固定长度的数字块（叫digit，64位系统下每个块存30个二进制位，32位系统下每个块存15个二进制位）存在数组里，再根据两个数字块数组的长度动态选择最优乘法算法：
  • 当较短的那个数的数字块长度小于阈值（当前CPython源码中该阈值为70）时，直接使用优化过的竖式逐位乘算法，也就是基础笔算乘法逻辑，循环做逐块相乘、累加、进位处理，这个算法常数极低，小数据量下性能远好于复杂的高阶乘法算法。
  • 当数字长度超过竖式乘法的最优区间、但还没达到更高阶算法的阈值时，切换到Karatsuba算法，通过把数拆成高低两段，用3段结果的加减组合替换掉1次乘法操作，减少总乘法次数。
  • 当数字长度进一步增大，会切换到Toom-Cook 3路拆分算法，把数拆成3段，用更少的乘法次数完成计算；针对百万位以上的超大整数，部分定制编译的Python版本会启用FFT快速傅里叶变换乘法，但官方默认发行版一般不会开启这个路径，因为FFT的常数开销极高，只有极大数字下才能体现性能优势。

时间复杂度没有统一值，完全根据输入数值的类型和大小走对应路径：

• 固定位宽类型（小整数、float）：时间复杂度为 O(1)，执行时间和数值大小无关，由硬件直接决定。
• 大整数走竖式乘法路径时：时间复杂度为 O(n²)，n为两个数的数字块总长度，和数字的十进制位数呈线性关系。
• 大整数走Karatsuba算法路径时：时间复杂度为 O(n^log₂3) ≈ O(n^1.585)。
• 大整数走Toom-Cook算法路径时：时间复杂度约为 O(n^1.465)；如果是启用了FFT乘法的版本，超大整数场景下复杂度可以到 O(n log n)。

补充说明：所有算法的切换阈值都是CPython核心开发者经过大量基准测试调优过的，保证在任意数字长度下，选中的都是当前长度区间常数开销最低、实际运行最快的算法，不会为了追求理论复杂度强行在小数据上用高阶算法。

内容的提问来源于stack exchange，提问作者VRM