並行任意精度算術庫

我想通過重複平方（功率總是2的冪在我的情況下，所以我相信這是最有效的方式）以非常大的模數進行整數的模冪運算。由於我的模數的一個很好的屬性，計算餘數很便宜;困難的部分是乘法。並行任意精度算術庫

目前，我在Intel Core 2 Quad上運行GMP。我想高效地使用處理器的四個內核，但GMP不能在SMP環境中擴展，所以我正在尋找一個替代的任意精度算術庫。我在矩陣上找到了一些用於並行計算的庫，但我真正需要的是一個用於整數的庫。

請問我在找什麼？

2011-10-26 Pteromys

你的號碼（數字，位）有多大？即使使用便宜的分支上下文切換時間來使多個CPU能夠在單個算術操作上工作，也可以節省任何費用。如果數字足夠大，你應該做一個遞歸分割和征服加/減[把數字分成左右兩部分，簡單地加入部分，傳播進位]，但我希望勝利是如果有一場勝利的話，可以並行化多重分割。 –

我的模數可以大到2^10000000（！）。 – Pteromys

答案是肯定的，多線程的任意精度庫確實存在。但我不知道一個實際上是公開的。（具有與GMP相當的速度）

例如，在Pi計算程序TachusPi和y-cruncher中使用的任意精度庫能夠進行大數量的多線程算術運算。

但是，這兩個圖書館都是封閉的來源，並沒有供公衆使用。

單位信息披露：我是y-cruncher的作者。所以我自己寫了一個這樣的多線程任意精度庫。

來源

2011-10-26 13:55:35 Mysticial

你能告訴我這些庫使用什麼樣的算法？我瀏覽了Knuth的TAOCP的相關章節，但我找不到明確聲明適合並行計算的bignum算法，除了所謂的模塊算術，這在我的情況下是不合適的。 – Pteromys

所有主要的大型庫都使用某種FFT進行大規模乘法運算。 FFT和它的變體都是非常可並行化的。但是，實現一個專門用於大數乘法的工作並非易事。（你不能僅僅在FFTW的基礎上打一個包裝，並期望它擊敗GMP並且可以通過多個核心進行擴展） – Mysticial

謝謝。（我寧願跳過FFT部分）。但我不認爲，我可以自己實施快速倍增程序... – Pteromys

您是否退房http://mpir.org？他們聲稱正在使用GMP和使用GPU來做這件事。

來源

2011-10-26 13:55:06

他們將其列爲他們的目標之一。但基於他們的文檔，它看起來並沒有被實現。可能是因爲MPIR與GMP分離，而GMP本身並不是並行化的。 – Mysticial

真遺憾。我可以自己平行進行GMP，但實際上有多困難？ – Pteromys

一個有趣的問題。如果MPIR傢伙應該這樣做，而沒有，你應該想知道爲什麼。我希望最難的部分是獲得GMP代碼（用GCC C編寫，右）來執行多線程操作。這種做法需要做到這一點，並且相應的同步在C中可能相對比較雜亂。算法本身：正如我前面所說的那樣，對於加法的分而治之應該很容易，而且我期望乘以C： D的計算主要是計算交叉產品，並且總和也應該以這種方式並行化。這會是一場勝利嗎？很難說不這樣做。 –

並行任意精度算術庫

回答

相關問題