C#，模运算给出的结果与计算器不同

Question

所以我想写这个方法：142^23（mod 187），并使用任何计算器我得到结果65，但使用这段代码：

double number = Math.Pow(142, 23) % 187

我得到的结果是 53。为什么会这样，我在这里做错了什么？

Answer 1

Math.Pow(142, 23)

太大，无法用双精度值准确表示。所以你的模数是通过有损计算完成的。

这将给出正确答案：

BigInteger.ModPow(142, 23, 187);

BigInteger

可以在

System.Numerics

命名空间和程序集中找到。

如果您想要像您在问题中使用的大小的整数一样，您也可以自己有效地实现这一点。

private static int ModPow(int basenum, int exponent, int modulus)
{
    if (modulus == 1)
    {
        return 0;
    }
    int result = 1;
    for (var i = 0; i < exponent; i++)
    {
        result = (result * basenum) % modulus;
    }
    return result;
}

BigInteger

使用二进制求幂做了一些更聪明的事情，这对于真正巨大的数字来说效果更好。

Answer 2

如果我们使用

BigInteger

来计算指数的完整结果：

var bi = BigInteger.Pow(142, 23);
Debug.WriteLine(bi);

我们得到这个非常大的数字：

31814999504641997296916177121902819369397243609088
or
3.1814999504642E+49

如果我们随后将该值转换为双精度型，则会导致精度损失，然后再转换回

BigInteger

:

var d = (double) bi;
bi = new BigInteger(d);
Debug.WriteLine(bi);

我们得到：

31814999504641997296916177121902819369397243609088  -- BigInteger
31814999504641993108158684988768059669621048868864  -- BigInteger -> double -> BigInteger
                ^ oh no mah precision

在十六进制中，精度损失更明显：

15C4 C9EB 18CD 25CE 858D 6C2D C3E5 D319 BC9B 8000 00
15C4 C9EB 18CD 2500 0000 0000 0000 0000 0000 0000 00   
                 ^ oh no mah precision

您会注意到精度损失发生在第 17 个十进制数字或第 14 个十六进制数字处。

为什么？

A

double

使用 IEEE-754 编码存储:

Significand or mantissa:          0-51
Exponent:                         52-62
Sign (0 = Positive, 1 = Negative) 63

这里的关键是尾数的 52 位。我们的 14 个十六进制数字是 56 位，接近 52 位的限制。我们如何解释 4 位差异？

（我想我在下面的解释中犯了错误。如果有人能指出，我将不胜感激）

最后一个不变的十六进制数字是

C

，或二进制的

1100

；由于最后两位为零，我们的数字是用 54 位编码的，而不是 56 位。因此，这实际上是 2 位差异。

我们如何解释最后两位？这是由于 IEEE-754 的小数部分是如何确定的。我已经很长时间没有这样做了，所以我将其作为读者的练习:)

Answer 3

BigInteger D = 353068955875873;
BigInteger E = 324734382257802;
BigInteger F = 752748311613664;
D ^ E % F
112448018451627

however:
BigInteger.ModPow(D, E, F)
116860072266913