用模数1000,000,007计算双倍大功率 [英] Calculating large powers of a double with modulus 1000,000,007

问题描述

我想找到（1 + sqrt（3））^（n + 1）的大幂，其中n从n = 1变化到n = 1000,000,000。
可以使用双打来模块化指数运算吗？怎么样？我已经搜索了很多，但没有正面的结果。任何帮助将高度赞赏？

解决方案

通过平方双工的模幂运算？是否定的，假设我将解释。

运算例如取一个残数为1,000,000,007是各种数论计算的典型代表，其他整数算术。所以，我会假设我们要用整数精度来计算结果。也就是说，我们想要知道对于一些n，0≤n≤1，对于（1 + sqrt（3））^（n + 1）％1,000,000,007最接近的整数。 n≤10 ⁹ 。考虑一个函数x ^{n + 1} 。其关于x的导数是（n + 1）x ⁿ 。当x是1 + sqrt（3）和n是10 9时，导数是大约4.65•10 436488780 。这意味着在4.65×10-4的x中约1分之一的变化将使x n + 1的值改变约1，这当然也改变了残基约1.因此，要计算所需的准确度的残留，我们必须实际上计算1 + sqrt（3）的值超过4.36亿小数位。

<这大大超出了任何现代计算机上双重类型所提供的精度。所以答案是否定的。没有算法可以给你想要的答案，因为double类型是不能够用必要的精度来计算的。

从技术上讲，可以使用双精度算法来构造扩展 - 精确算术。 （因此，上面的答案是以正常方式使用双精度算法来解决的。）因此，使用非同寻常的技术，可以从双精度操作中制造必要的计算。讨论这样做的方法超出了堆栈溢出的问题。通常，整数运算被用于大部分这样的工作，尽管双精度运算可能起作用。和软件包可用于提供这样的扩展精度算法，如GMP（GNU多精度算术库）。

计算和保留4.36亿小数位可能会使计算资源。通过丢弃可以显示不影响最终残基的信息来减少所需的计算是可能的，因此不需要同时需要所有的4.36亿个小数位。然而，我不认为这种减少会产生一个在没有扩展精度技术的双精度算法中是可行的计算。这个问题比这个更糟糕。了解x到4.65•10 436488780中的大约一部分可能会帮助您在1的误差范围内计算结果，但它不会告诉您哪个整数是最接近的。考虑你可以计算（1 + sqrt（3））n + 1％1000000007，并且发现结果非常接近3.5。为了确定最接近结果的整数是3还是4，必须确定结果的哪一边是3.5。这个函数（1 + sqrt（3））n + 1可能有一些非常接近这个中途位置的值，你需要更准确地计算它们来做出正确的决定。

I want to find large powers of (1+sqrt(3))^(n+1) where n varies from n=1 to n=1000,000,000. Can modular exponentiation by squaring work with doubles? How? I have searched a lot but no positive results yet.Any help will be highly appreciated?

解决方案

The answer to the question "Can modular exponentiation by squaring work with doubles?" is no, given some assumptions I will explain.

Operations such as taking a residue modulo 1,000,000,007 are typical of various number theory calculations and other integer arithmetic. So, I will assume we want to calculate the result with integer precision. That is, we want to know the integer closest to (1+sqrt(3))^(n+1) % 1,000,000,007 for some n, 0 < n ≤ 10⁹. Consider a function xⁿ⁺¹. Its derivative with respect to x is (n+1)xⁿ. When x is 1+sqrt(3) and n is 10⁹, the derivative is about 4.65•10^436488780. This means a change in x of about 1 part in 4.65•10^436488780 will change the value of xⁿ⁺¹ by about 1, which of course also changes the residue by about 1. Therefore, to calculate the residue with the desired accuracy, we must, in effect, calculate the value of 1+sqrt(3) to over 436 million decimal places.

This is grossly beyond the precision that is provided by the double type on any modern computer. Therefore, the answer is no; no algorithm can give you the desired answer because the double type is not capable of calculating with the necessary precision.

Technically, one could use double-precision arithmetic to construct extended-precision arithmetic. (Thus, the answer above is addressed at using double-precision arithmetic in normal ways.) So, using extraordinary techniques, one can fabricate the necessary computations from double-precision operations. Discussion of the methods for doing this are beyond a Stack Overflow question. Commonly, integer operations are used for large portions of such work, although double-precision operations may play a role. And software packages are available to provide such extended-precision arithmetic, such as GMP (GNU Multiple Precision Arithmetic Library).

Calculating and retaining 436 million decimal places may strain computing resources. It may be possible to reduce the computations needed by discarding information that can be shown not to affect the final residue, so that not all 436 million decimal places are needed at the same time. However, I do not expect that such reductions would produce a computation that is feasible in double-precision arithmetic without extended-precision techniques.

And the problem is worse than that. Knowing x to about one part in 4.65•10^436488780 might help you calculate the result within an error of 1, but it will not tell you which integer is nearest. Consider that you might calculate (1+sqrt(3))ⁿ⁺¹ % 1,000,000,007 and find the result is very near 3.5. In order to determine whether the integer closest to the result is 3 or 4, you must figure out which side of 3.5 the result is on. This function, (1+sqrt(3))ⁿ⁺¹ might have some values that are extraordinarily close to such a halfway position, and you will need to calculate them even more accurately to make a proper decision.

这篇关于用模数1000,000,007计算双倍大功率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！