二項式係數

Question

'簡單'問題，計算二項式係數的最快方法是什麼？ - 一些線程算法？

我在尋找提示:) - 未實現:)

Answer 1

根據下面的公式（來自wikipedia），最快的方法是將範圍i = 1，k分割爲線程數，爲每個線程分配一個範圍段，並且每個線程更新鎖中的最終結果。 「學術方式」是將範圍分成任務，每個任務都要計算（n-k + i）/ i，然後不管你有多少個線程，它們都運行在一個循環中，要求下一個任務。首先是更快，其次是...學術。

編輯：進一步解釋 - 在這兩個方面，我們有線程的一些任意數量。通常線程的數量等於處理器內核的數量，因爲添加更多線程沒有好處。兩種方式之間的區別在於這些線程正在做什麼。

在第一種方式中，給出每個線程N，K，I1和I2，其中I1和I2是範圍1..K中的線段。然後每個線程都擁有它所需的所有數據，因此它會計算其結果的一部分，並在完成時更新最終結果。

第二種方法是給每個線程賦予N，K，並訪問一些從1到K計數的同步計數器。然後每個線程從該共享計數器中獲取一個值，計算結果的一部分，更新最終結果，並在此循環，直到計數器通知線程沒有更多的項目。如果發生某些處理器內核比其他處理器內核速度更快，那麼第二種方式將使所有內核達到最大使用狀態。第二種方式的下滑是太多的同步，例如20％的線程總是有效地阻止。

Answer 2

提示：你想要做的少乘法越好。公式是n!/(k! * (n-k)!)。您應該少於2m乘法，其中m是k和n-k中的最小值。如果你想使用（相當）大的數字，你應該使用一個特殊的類來表示數字（例如Java有BigInteger）。

Answer 3

好吧，我認爲最快的方法是從表中讀取它們而不是計算它們。因爲使用雙重表示法對整數精度的要求意味着C（60,30）幾乎都太大，大約在1e17，所以（假設你想要C（m，n）到一定的限制，並且所有的n < = m），你的表格只有大約1800個條目。至於填補我認爲帕斯卡的三角形是要走的路。

Answer 4

這裏的，如果最後的結果是表達本身的機器，從來沒有溢出的方式，不涉及乘法/因式分解，容易被並行化，並推廣到BigInteger的類型：

首先要注意的是，二項式係數滿足以下：

。

這產生了一個簡單的遞歸來計算係數：基礎案例是和，兩者都是1。

subcalls的單個結果是整數，如果\ binom {n} {k}可以用int表示，它們也可以;所以，溢出不是一個問題。

天真地執行，遞歸導致重複的subcalls和指數運行時。

這可以通過緩存中間結果來解決。有 n^2子問題，它們可以在O（1）時間內組合，產生一個O（n^2）複雜性界限。