计算二项式系数2n2n在 Matlab 中

计算科学 matlab 组合学
2021-12-06 15:59:02

我想为适中的在 Matlab 中,一起使用会给出警告:“警告:结果可能不准确。系数大于 9.007199e+15,并且只能精确到 15 位”。我知道是一个很大的数字,但我真正需要的是,大约是 0.1026。(nk)/2nnknchoosek(n,k)n=60k=30(6030)(6030)/260

我的问题是,有没有一种方法可以计算而不会牺牲 Matlab 中的数值精度?(nk)/2n

3个回答

如果您安装了 MATLAB 的 Symbolic Math Toolbox,那么只需编写以下代码:

evalin(symengine, 'binomial(60, 30) / 2^60')

或者,您可以使用多精度算术(在 MATLAB 中通过像这样的第三方工具箱提供)编写自己的版本nchoosek(请参阅)。您也可以考虑编写自己的代码来添加任意精度整数算术(这不是太难)。

我会记录您的表达式,使用表现良好的内置函数(即不会下溢或溢出)计算表达式的对数,然后在最后取幂。

(nk)=n!k!(nk)!

所以

log((nk)2n)=logn!logk!log(nk)!nlog2.

您可以通过计算,因为,其中是 Gamma 函数。(不要将计算为,因为它不会避免溢出问题!)这种方法应该表现得更好。您还可以通过使用斯特林对的近似来快速估算,即我怀疑你想要更准确的东西,但斯特林的近似值会给你一个合理的想法,即你的指数运算最终是否会溢出。logn!gammaln(n+1)n!Γ(n+1)Γlogn!log(gamma(n+1))logn!nlognn

如果最大速度不是一个问题,我会去重写nchoosek在计算中穿插分区,以便临时值保持有界。下面是一个示例实现。

function accumulator=dividedbinomial(n,k)
  num=n; %factor to multiply at the numerator
  den=k; %factor to multiply at the denominator
  powers=n; %powers of 2 still left to divide
  accumulator=1; 
  for i=1:k
    accumulator=accumulator*n/k;
    n=n-1;
    k=k-1;
    %divides now by enough powers of two so that the result stays below 1
    while accumulator>1 && powers>0 
      accumulator=accumulator/2;
      powers=powers-1;
    end
  end
  %divides by the remaining powers of two
  while powers>0
    accumulator=accumulator/2;
    powers=powers-1;
  end
end