二项式系数 [英] Binomial coefficient

问题描述

简单的问题，什么是计算二项式系数最快的方法是什么？ - 有些线程算法

'Simple' question, what is the fastest way to calculate the binomial coefficient? - Some threaded algorithm?

我在寻找提示:) - 未实现：）

I'm looking for hints :) - not implementations :)

推荐答案

根据以下（等式从维基百科）最快的方式是将分裂范围I = 1，k，进而线程数，给每个线程一个量程段，并且每个线程更新最终结果中的锁。 学术方法是将范围划分为任务，每个任务是计算（N - K + I）/ I，然后不管你有多少线程都有，他们在一个循环中运行的所有要求的下一个任务。首先是速度快，二是学术...

According to the equation below (from wikipedia) the fastest way would be to split the range i=1,k to the number of threads, give each thread one range segment, and each thread updates the final result in a lock. "Academic way" would be to split the range into tasks, each task being to calculate (n - k + i)/i, and then no matter how many threads you have, they all run in a loop asking for next task. First is faster, second is... academic.

编辑：进一步解释 - 在这两个方面，我们有线​​程的一些任意数量。一般线程数等于处理器内核的数量，因为在添加更多的线程没有好处。两种方式之间的区别是什么这些线程正在做什么。

further explanation - in both ways we have some arbitrary number of threads. Usually the number of threads is equal to the number of processor cores, because there is no benefit in adding more threads. The difference between two ways is what those threads are doing.

在第一种方式的每个线程给出N，K，I1和I2，其中I1和I2是范围1..K的段。每个线程然后拥有所有它NEADS的数据，因此它计算结果的其一部分，并且在更新结束的最终结果。

In first way each thread is given N, K, I1 and I2, where I1 and I2 are the segment in the range 1..K. Each thread then has all the data it neads, so it calculates its part of the result, and upon finish updates the final result.

在第二种方式的每个线程都有N，K，并获得一些syncronized计数器，从1到K每个线程然后从该共用的反aquires一个值计算，计算结果的一小部分，更新了最终的结果，和循环在此，直到计数器通知没有更多项的线程。如果它发生了一些处理器核心是速度更快，其他人那么这第二条路将把所有核心，以最大限度地利用。缺点第二个方法实在是太多了同步，有效地阻止，说，线程的20％，所有的时间。

In second way each thread is given N, K, and access to some syncronized counter that counts from 1 to K. Each thread then aquires one value from this shared counter, calculates one fraction of the result, updates the final result, and loops on this until counter informs the thread that there are no more items. If it happens that some processor cores are faster that others then this second way will put all cores to maximum use. Downside to second way is too much synchronization that effectively blocks, say, 20% of threads all the time.

这篇关于二项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！