algorithm - 使用分治法的整数乘法算法？

Question

作为家庭作业，我应该使用低于 O(n) 的分而治之方法对 1000 位数字实现整数乘法。我应该研究什么算法？

Answer 1

Schönhage–Strassen algorithm是已知最快的乘法算法之一。它需要 O(n log n log log n) 时间。

Fürer's algorithm是迄今为止已知最快的大数乘法算法，需要 O(n*log n * 2^O(log*n)) 时间。

我认为任何乘法算法都不会小于甚至等于 O(n)。这根本不可能。