gpt4 book ai didi

r - 计算错误 R,与大数字的组合偶尔会产生错误的数字

转载 作者:行者123 更新时间:2023-12-04 17:44:40 25 4
gpt4 key购买 nike

我在 R 中创建了一个组合公式来计算大数的组合。

  combination_1 <- function(n,r){
n_0 <- n
num <- 1
denom <- factorial(r)
for(i in 1:(r)){
num <- num * n_0
n_0 <- n_0-1
}
num/denom
}

然后,当两个量相等时,我将这个组合公式应用到 f​​or 循环测试中,然后打印出各自的 n、m 和 r 值。

 both_large <- function(n,m,r){m*combination_1(n,r)}
both_small <- function(n,m,r){factorial(m)*combination_1(n,(r-1))}

for(m in 3:8){
for(n in 20:20000){
for(r in 1:20){
if(both_large(n,m,r) - both_small(n,m,r) == 0){
cat('r = ', r, ', n = ', n,', m= ',m, '\n')
}
}
}
}

然而,此代码仅在某些时候有效。下面显示了以下输出,其中跳过了 r = 9 处的值。

r =  6 , n =  149 , m=  5 
r = 7 , n = 174 , m= 5
r = 8 , n = 199 , m= 5
r = 10 , n = 249 , m= 5
r = 11 , n = 274 , m= 5

在 r = 9, n = 224, m = 5 处肯定有一个值;但是,当我对这些特定值进行减法运算时,R 计算出的值为 -2。当我通过 Wolfram Alpha 运行它时,它计算出的值为 0。我还找到了一种方法来进一步简化我的公式,简化版本的结果也为 0。

为什么 R 不计算 r = 9 时的值,而是在 r = 10 和 r = 11 时正确计算更大的值?它是某种舍入误差吗?如果是,为什么它会计算更大的值?它也不会计算其他值。这只是第一个没有发生的案例。

谢谢!

最佳答案

这是 double precision 的问题。在文章中,我们看到 double 数据类型以 64 位存储,分割如下:

  1. 符号位:1位
  2. 指数:11位
  3. 有效位数精度:53 位(显式存储 52 位)

将其转换为以 10 为底数,我们看到我们保证至少获得 15 位十进制数字的精度。

log10(2^53 - 1)
[1] 15.95459

我们可以通过使用简单的算术观察奇怪的行为来看到这一点:

options(scipen = 999)

1e16
[1] 10000000000000000

1e16 + 5
[1] 10000000000000004 ## incorrect.. should be 10000000000000005

以您的 r = 9n = 224m = 5 以及一些 print 为例> 您的 combination_1 函数中的语句,我们发现了罪魁祸首:

combination_1_Verbose <- function(n,r,verbose = FALSE){
n_0 <- n
num <- 1
denom <- factorial(r)
for(i in 1:(r)){
num <- num * n_0
n_0 <- n_0-1
}

if (verbose) {
print(num)
print(log10(num))
}

num/denom
}

combination_1_Verbose(n, r - 1, TRUE)
[1] 5585745606995474432
[1] 18.74708
[1] 138535357316356

我们正在对超过 18 位数字进行算术运算……超出了 double 据类型提供给我们的精度范围。

同样不明显的是,返回值并不完全是 138535357316356。使用 printdigits 参数,我们实际上看到返回值不是整数。

print(combination_1_Verbose(n, r - 1), digits = 22)
[1] 138535357316356.015625

这最终成为您错误的根源。如果我们取 .015625 并乘以 factorial(m) = 120,我们得到:

.015625 * 120
[1] 1.875

这会四舍五入到 2,这是我们检查中的差值。

我们可以使用多精度库 gmp 纠正这种行为:

library(gmp)
combination_1_GMP <- function(n,r,verbose = FALSE){
n_0 <- as.bigz(n)
num <- as.bigz(1)
denom <- factorialZ(r)
for(i in 1:(r)){
num <- mul.bigz(num, n_0)
n_0 <- sub.bigz(n_0, 1)
}

if (verbose) {
print(num)
print(log10(num))
}

as.bigz(num/denom)
}

combination_1_GMP(n, r-1, TRUE)
Big Integer ('bigz') :
[1] 5585745606995473920
[1] 18.74708
Big Integer ('bigz') :
[1] 138535357316356

在原始函数中,num5585745606995474432,而在我们的 gmp 示例中,我们获得了 5585745606995473920。请注意,差异小于 500,这是一个 3 位数的数字。这是有道理的,因为我们的数字超过 18 位,并且如上所述,我们只能保证总共 15 位精度(即 18 - 3 = 15)。

或者,我们可以四舍五入最终结果。如果绝对需要精度,我不会推荐此选项,因为 nmr 的某些值仍然会受 double 的支配。它在这个例子中虽然有效:

combination_1_Round <- function(n,r){
n_0 <- n
num <- 1
denom <- factorial(r)
for(i in 1:(r)){
num <- num * n_0
n_0 <- n_0-1
}
round(num/denom)
}

both_large_r <- function(n,m,r){m*combination_1_Round(n,r)}
both_small_r <- function(n,m,r){factorial(m)*combination_1_Round(n,(r-1))}

both_large_r(n,m,r) - both_small_r(n,m,r)
[1] 0

最后,您最好的选择是重写您的算法以将数字保持在 double 限制内。

combination_1_Improved <- function(n,r){

denom <- num <- 1
i <- (n - r + 1)

for (denom in 1:r) {
num <- num * i;
num <- num / denom;
i <- i + 1
}

num
}

print(combination_1_Improved(n,r-1), digits = 22)
[1] 138535357316356

关于r - 计算错误 R,与大数字的组合偶尔会产生错误的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52708595/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com