r中大数间模运算结果不正确

Question

为了解决来自hackerrank的难题，我试图在R (v4.2.2)中应用大数之间的模运算。但是，当至少有一个操作数非常大时，我会得到不正确的结果。例如，52504222585724001 %% 10在r中产生0，这是不正确的。然而，当我在python (v3.9.12)中尝试52504222585724001 % 10时，我得到了正确的结果1。所以我决定测试一些其他的数字。我下载了一组测试用例，我的代码失败了，我为每个n值做了n*n mod (10^9 + 7)。

R代码:

summingSeries <- function(n) {
return(n^2 %% (10^9 + 7))
}
n <- c(229137999, 344936985, 681519110, 494844394, 767088309, 307062702, 306074554, 555026606, 4762607, 231677104)
expected <- c( 218194447, 788019571, 43914042, 559130432, 685508198, 299528290, 950527499, 211497519, 425277675, 142106856 )
result <- rep(0L, length(n))
start <- Sys.time()
for (i in 1:length(n)){
result[i] <- summingSeries(n[i])
}
print(Sys.time() - start)
df <- data.frame(expected, result, diff = abs(expected - result))
print(df)

我将结果以及与期望值的绝对差值粘贴在下面

expected    result   diff
-------------------------
218194447 218194446    1
788019571 788019570    1
43914042  43914070    28
559130432 559130428    4
685508198 685508205    7
299528290 299528286    4
950527499 950527495    4
211497519 211497515    4
425277675 425277675    0
142106856 142106856    0

Python3代码:

import numpy as np
def summingSeries(n):
return(n ** 2 % (10 ** 9 + 7))
n = [229137999,
344936985,
681519110,
494844394,
767088309,
307062702,
306074554,
555026606,
4762607,
231677104]
expected = [218194447,
788019571,
43914042,
559130432,
685508198,
299528290,
950527499,
211497519,
425277675,
142106856]
result = [0] * len(n)
for i in range(0, len(n)):
result[i] = summingSeries(n[i])
print(np.array(result) -  np.array(expected))

我使用上面的python代码得到正确的结果。有人能解释一下为什么会有不一致，为什么R会得出错误的结果吗?

Answer 1

使用gmp包(参见Carl withthoft的评论)

gmp::mod.bigz(gmp::as.bigz(n)^2, 1e9 + 7) - expected
#> Big Integer ('bigz') object of length 10:
#>  [1] 0 0 0 0 0 0 0 0 0 0

之前/劣质答:

library(Rmpfr)
n <- c(229137999, 344936985, 681519110, 494844394, 767088309, 307062702, 306074554, 555026606, 4762607, 231677104)
expected <- c(218194447, 788019571, 43914042, 559130432, 685508198, 299528290, 950527499, 211497519, 425277675, 142106856)
data.frame(
precision = 53:64, # 53 corresponds to double precision
sumAbsErr = sapply(53:64, function(p) sum(abs(expected - as.numeric(mpfr(n, p)^2 %% (1e9 + 7)))))
)
#>    precision sumAbsErr
#> 1         53        53
#> 2         54        29
#> 3         55        21
#> 4         56        16
#> 5         57         1
#> 6         58         1
#> 7         59         1
#> 8         60         0
#> 9         61         0
#> 10        62         0
#> 11        63         0
#> 12        64         0

对于这个例子来说，60位的精度已经足够了。