2

我有兴趣了解使用多个处理器将大整数模（大）常数相乘的时间复杂度。这归结为基本上只是整数乘法，因为除法和余数也可以使用乘法来实现（例如倒数乘法或巴雷特归约）。

我知道目前已知的整数乘法算法的运行时间大致以下限为界o(n * log n)。我的研究未能确定这是针对单核机器还是多核机器。但是，我认为这是针对单核机器的，因为算法似乎使用了分而治之的方法。

m现在我的问题是，目前已知的在内核上实现的并行整数乘法算法的时间复杂度下限是多少？o(n)给定足够多的内核，是否可以实现具有下限或更少的时间复杂度？（即是否m取决于n？）这里o(n)描述了手头整数的输入大小。

到目前为止，在我的研究中，我已经阅读了几篇声称使用并行 FFT 乘法可以提高速度的论文。不幸的是，这些仅声称经验加速（例如“在某某计算机上使用 6 个内核的速度提高了 56%”），然后无法解释以时间复杂度界限表示的理论加速。

我知道尚未找到“最快”的整数乘法算法，这是计算机科学中一个未解决的问题。我只是在询问目前已知的这种并行算法的界限。

更新 #1：用户@delnan 链接到关于NC 复杂性类的 wiki 页面。该维基页面提到整数乘法在NC中，这意味着处理器上存在O((log n)^c)算法。O(n^k)这有助于更接近答案。现在没有回答的部分是整数乘法的c和k常量是什么，哪种并行算法适合这个目的？

更新 #2：根据康奈尔大学计算机科学课程的PDF 文件中的第 12 页（共 15 页），NC 复杂性课程中的整数乘法需要处理器O(log n)上的时间。O(n^2)它还解释了一个关于如何进行此操作的示例算法。我很快就会为这个问题写一个正确的答案。

最后一个问题来满足我的好奇心：有没有人知道“just”或处理器的当前已知时间O(n)复杂O(sqrt(n))度O(log n)？

4

1 回答 1

1

算法的计算复杂度不受并行化的影响。

当然，解决整数乘法之类的问题，您可以找到解决问题的各种算法。这些算法将表现出一系列复杂性。但是考虑到在p处理器上运行它的任何算法，理论上最好的情况下，它会加速p时间。就计算复杂度而言，这就像将现有复杂度乘以O(f(n))一个常数，得到O((1/p)*f(n))。如您所知，将复杂度乘以常数不会影响复杂度分类。

换个说法，也许更实用，改变处理器的数量并不会改变算法在任何给定规模下对任何给定问题执行的基本操作的数量——除了协调操作所需的任何额外操作的并行组件。

同样，请记住，计算复杂度是计算工作量的一个非常理论化的度量，通常以计算给定输入大小所需的某种基本操作的数量来衡量。一种这样的基本操作可能是两个数字（大小有限）的乘法。将基本运算的定义更改为两个数字向量（每个向量的大小有限）的乘法不会改变算法的复杂性。

当然，正如您所发现的，有很多经验证据表明并行算法比串行算法运行得更快。

于 2014-10-01T12:28:22.633 回答