4

「単純な」質問です。二項係数を計算する最速の方法は何ですか? - いくつかのスレッド化されたアルゴリズム?

私はヒントを探しています:)-実装ではありません:)

4

5 に答える 5

4

最速の方法は、計算するのではなく、テーブルから読み取ることだと思います。

二重表現を使用することによる整数精度の要件は、C（60,30）がほとんど大きすぎて、1e17前後であることを意味します。したがって、（ある制限まですべてのmに対してC（m、n）が必要であると仮定します。そして、すべてn <= m）の場合、テーブルには約1800のエントリしかありません。テーブルを埋めるということに関しては、パスカルの三角形が進むべき道だと思います。

于 2010-11-23T14:31:17.090 に答える
3

ヒント: 乗算はできるだけ少なくします。式はn! / (k! * (n-k)!)です。はとの最小値2mです。（かなり）大きな数を扱いたい場合は、数値表現に特別なクラスを使用する必要があります（JavaにはBigIntegerがあります）。mkn-k

于 2010-11-23T13:11:52.320 に答える
3

以下の式 (ウィキペディアから) によると、最も速い方法は、範囲 i=1,k をスレッド数に分割し、各スレッドに 1 つの範囲セグメントを与え、各スレッドが最終結果をロックで更新することです。「アカデミックな方法」は、範囲をタスクに分割し、各タスクが (n - k + i)/i を計算することであり、スレッドの数に関係なく、次のタスクを要求するループですべて実行されます。1 つ目は高速で、2 つ目は...アカデミックです。

代替テキスト

編集: さらなる説明 - どちらの方法でも、任意の数のスレッドがあります。スレッドを追加してもメリットがないため、通常、スレッドの数はプロセッサ コアの数と同じです。2 つの方法の違いは、それらのスレッドが行っていることです。

最初の方法では、各スレッドに N、K、I1、I2 が与えられます。ここで、I1 と I2 は 1..K の範囲のセグメントです。各スレッドには必要なすべてのデータがあるため、結果の一部を計算し、終了時に最終結果を更新します。

2 番目の方法では、各スレッドに N、K、および 1 から K までカウントする同期カウンターへのアクセスが与えられます。各スレッドは、この共有カウンターから 1 つの値を取得し、結果の一部を計算し、最終結果を更新して、ループします。これは、カウンターがスレッドにアイテムがなくなったことを通知するまで続きます。一部のプロセッサ コアが他のプロセッサ コアよりも高速である場合は、この 2 番目の方法ですべてのコアを最大限に活用できます。2 番目の方法の欠点は、同期が多すぎて、たとえば常に 20% のスレッドを効果的にブロックすることです。

于 2010-11-23T13:29:58.613 に答える
1

最終結果がマシンでネイティブに表現可能であり、乗算/因数分解を含まず、簡単に並列化され、BigInteger 型に一般化される場合、オーバーフローしない方法を次に示します。

最初に、二項係数が次を満たすことに注意してください。

ビノムンク.

これにより、係数を計算するための簡単な再帰が得られます。基本ケースは ビノムルと binomr0で、どちらも 1 です。

サブコールからの個々の結果は整数であり、\binom{n}{k} が int で表現できる場合、それらも可能です。したがって、オーバーフローは問題ではありません。

素朴に実装された再帰は、サブコールの繰り返しと指数関数的なランタイムにつながります。

これは、中間結果をキャッシュすることで修正できます。O(1) 時間で結合できる n^2 個の部分問題があり、O(n^2) の複雑さの限界が得られます。

于 2010-11-23T19:50:49.537 に答える
0

この回答は、Python で二項式を計算します。

def h(a, b, c):
    x = 0
    part = str("=") 
    while x < (c+1):
        nCr = math.comb(c,x)
        part = part+'+'+str(int(a**(c-1))*int(b**x)*int(nCr)+'x^'+str(x)
        x = x+1
    print(part) 
    
    h(2,6,4)
于 2021-02-07T13:29:47.907 に答える