N位加法和乘法的有效时间复杂度

Question

我已经完成了一门关于计算机体系结构的课程，在n位结构字大小最有效的处理器上，加/减两个字的时间复杂度为O(log n)，乘法/除法的时间复杂度为O(n)。

如果不考虑任何特定的体系结构字大小，加减法的最佳时间复杂度是O(n) (https://www.academia.edu/42811225/Fast_Arithmetic_Speeding_up_Multiplication_Division_and_Addition_of_n_Bit_Numbers)，乘法/除法似乎是O(n log n log log n) (Strassen https://en.m.wikipedia.org/wiki/Multiplication_algorithm)。

这是正确的吗？

Answer 1

O(log )是加法的延迟，如果您可以使用n位宽的并行硬件，包括进位选择或进位向前看。

O(n)是需要做的工作量的总和，因此当n趋于无穷时，具有固定宽度ALU的任意双元问题的时间复杂度。

对于乘法，n位乘法中有n个部分乘积，因此将它们全部相加(例如，Dadda树)的顺序是延迟的O(log )门延迟。整数加法是相联的，所以你可以并行地做这件事，例如(a+b) + (c+d)是3，延迟为2，从那里得到更好的结果。

Dadda树可以避免一些进位传播延迟，所以我想它避免了如果单独使用每个部分乘积的正常加法，就会得到log的额外因素。

有关大型Dadda树的实用注意事项，请参见Differences between Wallace Tree and Dadda Multipliers。