前不久，看到了个大新闻，有人提出了个的整数乘法算法。不过据说是理论意义大于实际意义。看到这个我就很奇怪了，使用FFT的整数乘法算法的时间复杂度之前难道不就是吗？然后我看到了知乎上相关的讨论，说以前的复杂度是。难道我一直都搞错了吗？经过一番研究后发现，这是由于我们对和运算的定义不同导致的。说复杂度为的，指的是二进制位的个数，其基本运算是二进制位的运算。而具体到我们的常见实现，我们通常采用十进制数下的...

阅读全文 »