取幂的前n位数

Question

如何确定取幂的前n位数(a ^b).

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

Answer 1

通过以下迭代计算^b:

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

你有一个_{i + 1} = a _i ×a.Calcluate每一个_我不完全是.事情是,相对误差一个^b小于Ñ的倍相对误差一个.
您希望最终相对误差小于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，我刚刚展示了您的代码的数学表示。