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

Question

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

Answer 1

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

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

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

Answer 2

看看Karatsuba 算法。它涉及一个递归步骤，您可以轻松地使用分治法进行建模。