2

我有一个处理任意大网格的函数。我需要计算另一个数字的幂的网格是否由于使用std::pow. 如果不能，我想采用不同的分支并使用 gnu 多精度库而不是正常的。

有没有一种快速的方法来查看是否：

int a = 1024;
int b = 0-10;

if(checkPowFitsDouble(a, b)) {
    long c = static_cast<long>(std::pow(a, b)); //this will only work if b < 6
} else {
    mpz_t c; //yada yada gmp
}

我完全被 checkPowFitsDouble 难住了；也许有一些我不知道的数学技巧。

4

4 回答 4

4

检查幂运算是否会溢出的一个常见技巧是使用对数。这个想法是基于这些关系：

a^b <= m <=> log(a^b) <= log(m) <=> b * log(a) <= log(m) <=> b <= log(m) / log(a)

例如，

int a = 1024;

for (int b = 0; b < 10; ++b) {
    if (b * std::log(a) < std::log(std::numeric_limits<long>::max())) {
        long c = std::pow(a, b);
        std::cout << c << '\n';
    }
    else
        std::cout << "overflow\n";
}

这给出了这个想法。我希望这有帮助。

于 2013-09-04T08:58:43.437 回答
4

除非它对性能特别重要，否则建议尝试一下。如果它溢出一个双精度，std::pow将返回HUGE_VAL。因此类似于：

double val = std::pow(a, b);
if(val != HUGE_VAL) {
    ...
} else {
    mpz_t c; 
    //...
}
于 2013-09-04T08:47:24.370 回答
3

您可以在测试中轻松使用反向函数：

if ( std::log( DBL_MAX ) / std::log( a ) < b ) {
    //  std::pow( a, b ) will not overflow...
} else {
}

做 pow 可能同样好，看看它是否成功：

errno = 0;
double powab = std::pow( a, b );
if ( errno == 0 ) {
    //  std::pow succeeded (without overflow)
} else {
    //  some error (probably overflow) with std::pow.
}

仅计算 不会获得太多时间std::log( a )。(std::log( DBL_MAX )当然是一个常数，所以只需要计算一次。)

于 2013-09-04T08:58:50.357 回答
2

使用以 10 为底的对数，您可以推断出std:pow(a, b)有log(a^b) = b log a数字。然后，您可以轻松地查看它是否适合双精度数，该双精度数可以适合高达 DBL_MAX 的值。

但是，此方法执行额外的计算，而不仅仅是计算a^b一次。首先用 GMP 测量一个版本，看看检查溢出是否真的提供了任何可测量和可重现的好处。

编辑：忽略这个，std::pow如果发生溢出，已经返回一个适当的值，所以使用它。

于 2013-09-04T08:58:09.430 回答