我如何确定指数的前 n 位 (ab)。
eg: for a = 12, b = 13 & n = 4, the first 4 digits are 1069.
最佳答案
通过以下迭代计算 ab:
a1 = a1,
a2 = a2,
...
ai = ai,
...
ab = ab
你有 ai+1 = ai×a。不准确地计算每个 ai。问题是 ab 的相对误差小于 n 的 a 相对误差。
您希望获得小于 10-n 的最终相对误差。因此每一步的相对误差可能是 .在每一步中删除最后一位数字。
例如,a=2、b=16、n=1。最终相对误差为 10-n = 0.1。每一步的相对误差为 0.1/16 > 0.001。因此 3 位数字在每一步都很重要。如果 n = 2,则必须保存 4 位数字。通用规则:每一步保存 [n+log10 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)
关于c++ - 指数的前 n 位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3873298/