在多個處理器上進行大整數模乘運算的最快運行時間是多少？

Question

我有興趣瞭解使用多個處理器乘以大整數modulo（大）常量的時間複雜度。歸結起來基本上只是整數乘法，因爲除法和餘數也可以用乘法實現（例如reciprocal multiplication或Barrett reduction）。

我知道currently known integer multiplication algorithms的運行時間大致以下限o(n * log n)爲界。我的研究未能發現這是否適用於單核或多核機器。但是，我認爲這是針對單核機器的，因爲這些算法似乎採用了分而治之的方法。

現在我的問題是，在m內核上實現的並行整數乘法算法的時間複雜度的當前已知下限是多少？給定足夠的核心，可以在o(n)或更低的下限內實現時間複雜度？ （即，如果m取決於n？）這裏o(n)描述了手頭整數的輸入大小。

到目前爲止，在我的研究中，我已經閱讀了幾篇聲明使用並行FFT乘法加速的論文。不幸的是，這些僅僅宣稱經驗加速（例如，「在這樣和那樣的計算機上使用6個核心的速度提高了56％」），然後未能解釋在時間複雜度範圍內表達的理論加速。

我知道「最快」的整數乘法算法尚未找到，這是一個unsolved problem in computer science。我只是在詢問目前已知的這種並行算法的邊界。

更新＃1：用戶@delnan鏈接到關於NC complexity class的維客頁面。該wiki頁面提到整數乘法在NC中，這意味着在O(n^k)處理器上存在O((log n)^c)算法。這有助於更接近答案。現在還沒有得到答覆的部分是整數乘法的常數是多少，並行算法是否適用於這個目的？

更新＃2：根據this PDF file來自康奈爾大學的計算機科學課程的15第12頁，在NC複雜類整數乘法需要O(log n)時間O(n^2)處理器。它還解釋了一個關於如何去解決這個問題的算法。我很快就會爲這個問題寫一個正確的答案。

爲了滿足我的好奇心，最後一個問題是：可能有人知道「剛纔」O(n)，O(sqrt(n))或O(log n)處理器的當前已知時間複雜性嗎？

Answer 1

算法的計算複雜度不受並行化的影響。

當然，可以考慮整數乘法等問題，並且可以找到各種解決問題的算法。這些算法將呈現一系列複雜性。但是考慮到任何運行在p處理器上的算法，在理論上最好的情況下，將會加速p次。就計算複雜性而言，這就像將現有的複雜度乘以常數即O(f(n))，得到O((1/p)*f(n))。如您所知，將複雜度乘以常數不會影響複雜度分類。

爲了採用另一個也許更實用的參數，改變處理器的數量並不會改變算法對任何給定大小的任何給定問題執行的基本操作的數量 - 除了需要額外的操作通過協調並行組件的操作。

再次記住，計算複雜度是計算工作量的一個非常理論性的度量，通常以給定輸入大小計算所需的某種基本操作的數量來度量。一個這樣的基本操作可能是兩個數字的乘法（大小有限）。將基本操作的定義更改爲乘以兩個數字向量（每個有限大小）不會改變算法的複雜性。當然，有很多經驗證據表明，並行算法的運行速度可能比它們的串行算法更快，正如你發現的那樣。