二项式系数

根据下面的方程式(从 wikipedia )最快的方法是将范围i=1,k拆分为线程数,给每个线程一个范围段,每个线程更新锁中的最终结果。”学术上的方法是“将范围分成任务,每个任务都要计算(n-k+i)/i,然后不管你有多少线程,它们都在一个循环中运行,请求下一个任务。一是更快,二是。。。学术性。

编辑:进一步解释-在这两种情况下,我们有一些任意数量的线程。通常线程数等于处理器内核数,因为添加更多线程没有好处。两种方法的区别在于这些线程在做什么。

第一种方法是给每个线程N,K,I1和I2,其中I1和I2是1..K范围内的段。然后每个线程都有它所需要的所有数据,因此它计算结果的一部分,完成后更新最终结果。

在第二种方式中,每个线程被赋予N,K,并访问一些从1到K计数的同步计数器。然后,每个线程从这个共享计数器获取一个值,计算结果的一部分,更新最终结果,并在此上循环,直到计数器通知线程没有更多项为止。如果某些处理器内核比其他处理器更快,那么第二种方法将把所有内核都最大化地使用。第二种方法的缺点是太多的同步会一直有效地阻塞20%的线程。

好吧,我想最快的方法是从表中读取它们,而不是计算它们。

使用双精度表示对整数精度的要求意味着C(60,30)几乎太大,大约为1e17,因此(假设希望所有m的C(m,n)都达到某个限制,并且所有n<=m),您的表将只有大约1800个条目。至于把桌子填满,我认为帕斯卡三角形是个好办法。

提示:你想做尽可能少的乘法运算。公式是 n! / (k! * (n-k)!) . 你应该做的少于 2m 乘法,其中 m 是 k 和 n-k . 如果你想处理(相当)大的数字,你应该使用一个特殊的类来表示数字(例如Java有biginger)。

如果最终结果可以在计算机中以本机方式表示、不涉及乘法/因式分解、易于并行化并推广到BigInteger类型,则以下方法永远不会溢出:

首先注意二项系数满足以下条件:

.

这产生了计算系数的直接递归:基本情况是 和 ,两者都是1。

子类的单个结果是整数,如果\binom{n}{k}可以用int表示,它们也可以;因此,溢出不是问题。

简单地实现,递归会导致重复的子类和指数运行时。

这可以通过缓存中间结果来解决。有 N ^ 2子问题,可以组合在O(1)时间,产生O(n ^ 2)复杂度界。