仅需要前 k 位数字时快速求幂？
这实际上是为了一场编程竞赛，但我已经非常努力地尝试了，但仍然没有得到最微弱的线索如何做到这一点。
找到 nm 的前 k 位和后 k 位，其中 n 和 m 可以非常大 ~ 10^9。
对于最后 k 位数字，我实现了模幂运算。
对于第一个 k，我想到使用二项式定理达到一定的幂，但这涉及大量阶乘计算，而且我不确定如何找到 n^m 可以扩展为 (x+y) 的最佳点米。
那么有没有已知的方法可以找到前 k 位数字而不执行整个计算呢？
更新 1 <= k <= 9 并且 k 将始终为 <= nm 中的数字
This is actually for a programming contest, but I've tried really hard and haven't got even the faintest clue how to do this.
Find the first and last k digits of nm where n and m can be very large ~ 10^9.
For the last k digits I implemented modular exponentiation.
For the first k I thought of using the binomial theorem upto certain powers but that involves quite a lot of computation for factorials and I'm not sure how to find an optimal point at which n^m can be expanded as (x+y)m.
So is there any known method to find the first k digits without performing the entire calculation?
Update 1 <= k <= 9 and k will always be <= digits in nm
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
不确定，但是恒等式 nm = exp10(m log10(n)) = exp(q (m log(n)/q)) 其中 q = log(10) 浮现在脑海中，事实上，exp10(x) 的前 K 位 = exp10(frac(x)) 的前 K 位，其中 frac(x) = x = x - Floor(x) 的小数部分。
更明确地说：nm 的前 K 位是其 尾数 = exp(frac(m log(n)/q) * q)，其中 q = log(10)。
或者您甚至可以在这个会计练习中更进一步，并使用 exp((frac(m log(n)/q)-0.5) * q) * sqrt(10)，它也具有相同的尾数（+ 因此第一个 K 相同）数字），以便 exp() 函数的参数以 0 为中心（并且在 +/- 0.5 log 10 = 1.151 之间），以便快速收敛。
（一些示例：假设您想要 2100 的前 5 位数字。这等于 exp((frac(100 log(2)/q)-0.5)*q)*sqrt 的前 5 位数字(10) = 1.267650600228226。根据 MATLAB，2100 的实际值为 1.267650600228229e+030，对于 21,000,000,000 我得到 4.612976044195602 但我真的没有办法检查...... 梅森素数，其中有人已经完成了艰苦的工作 220996011-1 = 125,976,895,450...，我的公式在 MATLAB 中计算出 1.259768950493908，在第 9 个之后失败；数字。）
我可能会使用 泰勒级数 （用于 exp
和 log，不适用于 nm）及其误差范围，并继续添加项，直到误差范围降至前 K 位以下。 （通常我不使用泰勒级数进行函数逼近——它们的误差被优化为在单个点周围最准确，而不是在期望的间隔上——但它们确实有一个优点，那就是它们在数学上很简单，而且你只需添加附加项即可将准确度提高到任意精度）对于对数，我会使用您最喜欢的近似值。
not sure, but the identity nm = exp10(m log10(n)) = exp(q (m log(n)/q)) where q = log(10) comes to mind, along with the fact that the first K digits of exp10(x) = the first K digits of exp10(frac(x)) where frac(x) = the fractional part of x = x - floor(x).
To be more explicit: the first K digits of nm are the first K digits of its mantissa = exp(frac(m log(n)/q) * q), where q = log(10).
Or you could even go further in this accounting exercise, and use exp((frac(m log(n)/q)-0.5) * q) * sqrt(10), which also has the same mantissa (+ hence same first K digits) so that the argument of the exp() function is centered around 0 (and between +/- 0.5 log 10 = 1.151) for speedy convergence.
(Some examples: suppose you wanted the first 5 digits of 2100. This equals the first 5 digits of exp((frac(100 log(2)/q)-0.5)*q)*sqrt(10) = 1.267650600228226. The actual value of 2100 is 1.267650600228229e+030 according to MATLAB, I don't have a bignum library handy. For the mantissa of 21,000,000,000 I get 4.612976044195602 but I don't really have a way of checking.... There's a page on Mersenne primes where someone's already done the hard work; 220996011-1 = 125,976,895,450... and my formula gives 1.259768950493908 calculated in MATLAB which fails after the 9th digit.)
I might use Taylor series (for exp
and log, not for nm) along with their error bounds, and keep adding terms until the error bounds drop below the first K digits. (normally I don't use Taylor series for function approximation -- their error is optimized to be most accurate around a single point, rather than over a desired interval -- but they do have the advantage that they're mathematically simple, and you can increased accuracy to arbitrary precision simply by adding additional terms)For logarithms I'd use whatever your favorite approximation is.
出色地。 我们想要计算
并仅获取 n 个第一位数字。
通过以下迭代计算
： <
img src="https://i.sstatic.net/ECQhX.png “ alt="alt text">
您有
。
。
的相对误差较小
不准确地计算每个
问题是
比n倍相对误差a。
您希望最终的相对误差小于
。
。
因此，每个步骤的相对误差可能是
删除每一步的最后一位数字。
例如，a=2，b=16，n=1。 最终相对误差为 10^{-n} = 0,1。
每一步的相对误差为0.1/16>0.1/16。 0,001。
因此，每一步 3 位数字都很重要。
如果 n = 2，则必须保存 4 位数字。
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)
Well. We want to calculate
and to get only n first digits.
Calculate
by the following iterations:
You have
.
not exactly.
is less
Calcluate each
The thing is that the relative error of
than n times relative error of a.
You want to get final relative error less than
.
.
Thus relative error on each step may be
Remove last digits at each step.
For example, a=2, b=16, n=1. Final relative error is 10^{-n} = 0,1.
Relative error on each step is 0,1/16 > 0,001.
Thus 3 digits is important on each step.
If n = 2, you must save 4 digits.
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).
Answer: 6.
This algorithm has a compexity of O(b). But it is easy to change it to get
O(log b)
假设你在每一步都截断？ 不确定这有多准确，但是，例如，采取
n=11
m=某个大数
并且您想要前 2 位数字。
递归地：
然后取截断值并再次提高
12 x 11 -> 132 截断-> 13
重复，
（132 截断）x 11 -> 143.
...
最后添加相当于您已完成的截断次数的 #0。
Suppose you truncate at each step? Not sure how accurate this would be, but, e.g., take
n=11
m=some large number
and you want the first 2 digits.
recursively:
then take truncated value and raise again
12 x 11 -> 132 truncate -> 13
repeat,
(132 truncated ) x 11 -> 143.
...
and finally add #0's equivalent to the number of truncations you've done.
您看过平方求幂吗？ 您也许能够修改其中一种方法，以便仅计算必要的内容。
在我的上一堂算法课中，我们必须实现与您正在做的类似的东西，我隐约记得该页面很有用。
Have you taken a look at exponentiation by squaring? You might be able to modify one of the methods such that you only compute what's necessary.
In my last algorithms class we had to implement something similar to what you're doing and I vaguely remember that page being useful.