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 is stored using IEEE-754 encoding:

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 的小数部分是如何确定的。我已经很久没有这样做了，所以我会把它留作 reader :)

的练习

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

C#, Modulo operation gives diffrent result than a calculator

c#

math

mod