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乘法少，其中和m的最小值在哪里。如果你想处理（相当）大的数字，你应该使用一个特殊的类来表示数字（例如 Java 有 BigInteger）。kn-k

于 2010-11-23T13:11:52.320 回答
3

根据下面的等式（来自wikipedia），最快的方法是将范围 i=1,k 拆分为线程数，给每个线程一个范围段，然后每个线程更新锁中的最终结果。“学术方式”是将范围分成任务，每个任务都计算（n - k + i）/i，然后无论你有多少线程，它们都在循环中运行，要求下一个任务。首先是更快，其次是......学术。

替代文字

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

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

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

于 2010-11-23T13:29:58.613 回答
1

如果最终结果可以在机器中本地表达，不涉及乘法/因式分解，易于并行化并推广到 BigInteger 类型，则这是一种永不溢出的方法：

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

比诺姆克.

这产生了计算系数的直接递归：基本情况是 二进制和 二进制文件0，两者都是 1。

子调用的单个结果是整数，如果 \binom{n}{k} 可以用 int 表示，它们也可以；所以，溢出不是问题。

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

这可以通过缓存中间结果来解决。有 n^2 个子问题，可以在 O(1) 时间内组合，产生 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 回答