这种计算大数的方式如何工作？

Question

通常,要处理超出C++中long long范围的整数,您必须将它们表示为字符串并以这种方式对它们执行操作.但是,我在互联网上发现这个代码似乎像魔术一样.它计算两个幂的总和(没有2 ^ 0),即使它不能存储在很长的长度中.

#include <iostream>  
#include <cmath>  
#include <iomanip>  
#include <sstream>  
using namespace std;

int main() {
    int n;
    stringstream ss;
    cin >> n;

    ss << fixed << setprecision(0) << pow(2, n + 1) - 2;

    if (n >= 54) {
        string a = ss.str();

        a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

        cout << a;
        return 0;
    }

    cout << ss.str();

}

它是如何工作的？它适用于涉及大量的任何操作吗？如果n的值非常大(我试过1024)它只打印"inf".可以这种方式计算的数字范围的上限是多少？

以下部分到底做了什么以及它为什么这样做？

a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

Answer 1

它适用于涉及大量的任何操作吗？

您可以使用浮点执行与浮点相同的操作.但每次计算都涉及错误,并非所有整数都可以表示.

可以这种方式计算的数字范围的上限是多少？

取决于处理器使用的双精度浮点类型.

您可以找到最高可表示的数字std::numeric_limits<double>::max().但是,这些高数字的精度非常差.并非所有整数都可以表示为此数字.连续可表示整数的最大值是std::pow(std::numeric_limits<double>::radix, std::numeric_limits<double>::digits).

以下部分到底做了什么以及它为什么这样做？

a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

这可以简化为

a[a.size() - 1] -= 2;

它只是从最后一个(最低)数字中扣除2.它依赖于数学事实,即2的幂不是0或1模10(除了2 ⁰),在这种情况下,最后一个数字将变为非数字字符.

这也依赖于事实pow(2, n + 1) - 2 == pow(2, n + 1)的n >= 54.该代码假定浮点如下无处不二进制IEEE-754格式,其中std::pow(std::numeric_limits<double>::radix, std::numeric_limits<double>::digits)是std::pow(2, 54).当n大于或等于54时,计算结果std::pow(2, 54 + 1)变得如此之大,如果从中扣除一个小数字2,则最接近的可表示结果与您开始时的结果相同.计算的准确度误差等于较小的操作数!这个计算根本不能用浮点数来执行.这就是为什么之后用数字字符摆弄它固定的原因.

2的所有幂(直到极限)都是可表示的,因此功率计算本身从不会出现任何精度误差.