c++ - 取幂的前 n 位数字

Question

我如何确定取幂的前 n 位（a ^b）。

eg: for a = 12, b = 13 & n = 4, the first 4 digits are 1069.

Answer 1

通过以下迭代计算 a ^{b ：}

a ₁ = a ¹ ,
a ₂ = a ² ,
...
a _i = a ⁱ ,
...
a _b = a ^b

你有a _i+1 = a _i ×a。计算每个a _i不准确。问题是a ^b的相对误差小于a 的相对误差的n倍。 您希望获得小于10 ^-n的最终相对误差。因此，每一步的相对误差可能是。删除每一步的最后一位数字。

例如，a=2、b=16、n=1。最终相对误差为10 ^-n = 0.1。每一步的相对误差为0.1/16 > 0.001。因此，3 位数字在每一步都很重要。如果 n = 2，则必须保存 4 位。通用规则：每一步保存 [ n+log ₁₀ b ] 个数字。

2 (1), 4 (2), 8 (3), 16 (4), 32 (5), 64 (6), 128 (7), 256 (8), 512 (9), 1024 (10) → 102、204
（11）、408（12）、816（13）、1632（14）→163、326（15）、652（16）。

答案：6。

该算法的复杂度为O(b)。但是很容易将其更改为O(log b)

Answer 2

另一种解决方案，使用 log10：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char **argv) {
       int a = 12;
       int b = 13;
       int n = 4;
       double x, y;

       x = b * log10(a);
       y = floor(pow(10, x - floor(x) + n - 1));
       printf("Result: %d\n", (int)y);

       return EXIT_SUCCESS;
}

Answer 3

n=9 k=3 n^n=387420489 答案应该是 387

这是同一件事，@RC 在他的代码中所做的。谢谢@RC，我刚刚展示了您的代码的数学表示。

Answer 4

对于这种情况 - 使用幻数 12,13,4：

#include <sstream>
#include <iomanip>
#include <cmath>

double a = 12;
int b = 13;
double result = std::pow(a,b);

std::stringstream strVal;
strVal.setf( ios::fixed, ios::floatfield );
strVal << result;
std::string output(strVal.str().substr(0,4));

输出=“1069”

std::stringstream intStr(output);
int intVal;
intStr >> intVal;

整数值 = 1069

编辑：这应该适用于结果不溢出的任何组合double。

Answer 5

以编程方式执行此操作的最简单方法是使用字符串流将求幂的结果转换为字符串，然后取 n 个最重要（即左侧）字符。

如果您想要一种没有字符串的方法，那么这将起作用：

#include <iostream>
#include <sstream>
#include <math.h>

using namespace std;

double nDigExp( double a, double b, int n )
{
    stringstream ss;
    ss.setf( ios::fixed, ios::floatfield );
    ss << pow(a,b);
    double ret;
    for ( int i = 0; i < n; ++i) ret = (10 * ret) + (ss.get() - '0'); // Yeuch!!
    return ret;
}

int main( )
{
    double result = nDigExp( 12, 13, 4 );

    cout << result << endl;

    return 0;
}

但这并不是最优雅的代码。我相信你可以改进它。