二项式系数

Question

“简单”的问题，什么是计算二项式系数的最快方法？ - ？一些螺纹算法

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

Answer 1

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

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

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

在第二方式的每个线程被赋予N，K，并在一定syncronized计数器访问，从1到K.每个线程然后从该共用的反aquires一个值计数，计算结果的一个分数，更新最终结果，并在此循环，直到计数器通知线程，有没有更多的项目。如果碰巧一些处理器内核速度更快，其他人那么这第二种方式将把所有内核最大限度的利用。缺点第二种方法是太多的同步，其有效的块，也就是说，线程的20％的所有时间。

Answer 2

好了最快的方式，我估计，会从表而不是计算他们阅读。

您整数精度要求使用双表示意味着C（60,30）几乎是太大了，被周围的1E17，这样（假设你想有C（M，N）的所有米至一些限制，所有的n <= M），你的表只会有大约1800项。至于在填充表我觉得帕斯卡三角是要走的路。

Answer 3

提示：你想要做的少乘法越好。式是n! / (k! * (n-k)!)。你应该做的比2m乘法，其中m是k和n-k的最低少。如果你想用（相当）大的数字的工作，你应该使用一类特殊的数表示（Java有BigInteger的举例）。

Answer 4

下面是如果最后的结果是表达本身在机器从未溢出的方式，不涉及乘法/因式分解，容易并行化，并且推广到的BigInteger类型：

首先注意到二项式系数满足下列：

此产率，用于计算系数的简单的递归：基座例是和，这两者都是1。

从子调用的单独的结果是整数，且如果\ binom {N} {K}可通过一个int来表示，它们也可以做到;因此，溢出是不是一个问题。

天真实现，则递归导致重复子调用和指数运行时。

这可通过缓存中间结果被固定。有 N ^ 2子问题，它可以在O（1）时间进行组合，得到为O（n ^ 2）的复杂性的约束。