我想找到 (1+sqrt(3))^(n+1) 的大幂，其中 n 从 n=1 变化到 n=1000,000,000。通过平方的模幂运算可以与双打一起使用吗？如何？我已经搜索了很多，但还没有积极的结果。任何帮助将不胜感激？
问问题
582 次
1 回答
2
对“通过平方进行模幂运算可以与双精度数一起使用吗？”这个问题的答案？不是，给定一些假设，我将解释。
诸如取余数模 1,000,000,007 之类的操作是各种数论计算和其他整数算术的典型操作。所以，我假设我们想要以整数精度计算结果。也就是说，我们想知道对于某些 n，0 < n ≤ 10 9最接近 (1+sqrt(3))^(n+1) % 1,000,000,007 的整数。考虑一个函数 x n+1。它对 x 的导数是 (n+1)x n。当 x 为 1+sqrt(3) 且 n 为 10 9时，导数约为 4.65•10 436488780。这意味着 x 在 4.65•10 436488780中大约 1 部分的变化将改变 x n+1的值大约 1，这当然也将残差改变了大约 1。因此，要以所需的精度计算残差，实际上，我们必须将 1+sqrt(3) 的值计算到超过 4.36 亿位小数。
这大大超出了任何现代计算机上的 double 类型提供的精度。因此，答案是否定的；没有算法可以给你想要的答案，因为 double 类型不能以必要的精度进行计算。
从技术上讲，可以使用双精度算术来构造扩展精度算术。（因此，上面的答案是针对以正常方式使用双精度算术的。）因此，使用非凡的技术，可以从双精度运算中制造必要的计算。讨论这样做的方法超出了堆栈溢出问题。通常，整数运算用于此类工作的大部分，尽管双精度运算可能会起作用。并且可以使用软件包来提供这种扩展精度算术，例如 GMP（GNU 多精度算术库）。
计算和保留 4.36 亿个小数位可能会使计算资源紧张。通过丢弃可以证明不会影响最终残差的信息，可以减少所需的计算量，因此并非同时需要所有 4.36 亿个小数位。但是，我不希望这种减少会产生在没有扩展精度技术的情况下在双精度算术中可行的计算。
问题比这更糟。知道 x 到 4.65•10 436488780中的大约一个部分可能会帮助您在 1 的误差范围内计算结果，但它不会告诉您哪个整数最接近。考虑您可能计算 (1+sqrt(3)) n+1 % 1,000,000,007 并发现结果非常接近 3.5。为了确定最接近结果的整数是 3 还是 4，您必须弄清楚结果在 3.5 的哪一侧。这个函数 (1+sqrt(3)) n+1可能有一些非常接近中间位置的值，您需要更准确地计算它们才能做出正确的决定。
于 2012-07-06T14:30:00.837 回答