java - java处理大数时的算术错误

Question

我正在使用 Java 进行一些算术运算，这些运算需要处理非常大的数字。

查看这个简单的代码片段:

// A = a^k mod p 

    double k = 96 , a = 13 , p = 353 ;
    double A = (Math.pow(a,k))%p;
    System.out.println(A);

这将打印 29.0。

当我使用 Windows 计算器时，它返回 (13^96) % 353 的 58.0。我知道计算器是正确的。

为什么这段 Java 代码打印出错误的结果？

Answer 1

说明

嗯，Math.pow 可能不会做你想象的那样。这不是你的错，这实际上是在骗你。它返回一个 double，相当接近 13^96，但不完全一样。由于我们在这里讨论的是 10^107 左右的数字，因此较小的相对变化意味着绝对变化远大于 353。因此，所有关于此的赌注都已失败。

示例

为了增加更多的数字，当我们使用十进制科学记数法时，实际上会出现同样的问题:商是 practically one但区别是around 2^91 。一般来说， float 不适合整数运算，您实际上肯定会遇到这些问题。

解决方案

虽然大整数库可以工作，但有一种更基础的方法可以解决此问题:执行 binary exponentiation并取每一步的模数。如果您是初学者，这将教给您的不仅仅是一些大型 int 库的黑匣子。