仅要求前k位数字时快速求幂? [英] Fast exponentiation when only first k digits are required?

问题描述

这实际上是一场编程比赛，但是我已经非常努力，甚至没有最微妙的线索来做到这一点.

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.

找到n ^m 的前k位和后k位，其中n和m可能很大〜10 ^ 9.

Find the first and last k digits of n^m where n and m can be very large ~ 10^9.

对于最后k位，我实现了模幂运算.

For the last k digits I implemented modular exponentiation.

对于第一个k，我想到了将二项式定理用于某些幂，但是这涉及到阶乘的大量计算，而且我不确定如何找到n ^ m可扩展为(x的最优点+ y) ^m .

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.

那么有什么已知的方法可以在不执行整个计算的情况下找到前k个数字吗?

So is there any known method to find the first k digits without performing the entire calculation?

更新 1< = k< = 9，并且k始终是n ^m

Update 1 <= k <= 9 and k will always be <= digits in n^m

推荐答案

不确定，但是身份n ^m = 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).

not sure, but the identity n^m = 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).

更明确地说:n ^m 的前K位数字是其

To be more explicit: the first K digits of n^m are the first K digits of its mantissa = exp(frac(m log(n)/q) * q), where q = log(10).

或者您甚至可以在此会计练习中更进一步，并使用exp((frac(m log(n)/q)-0.5)* q)* sqrt(10)，它的尾数也相同(因此+相同的前K位数字)，以便快速收敛.exp()函数的参数以0为中心(且在+/- 0.5 log 10 = 1.151之间).

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.

(某些示例:假设您想要2 ¹⁰⁰ 的前5位数字.这等于exp((frac(100 log(2)/q)-0.5)* q的前5位数字)* sqrt(10)= 1.267650600228226.根据MATLAB，2 ¹⁰⁰ 的实际值为1.267650600228229e + 030，我没有bignum库，对于2 ^{1,000,000,000的尾数}我得到4.612976044195602，但是我真的没有办法检查....

(Some examples: suppose you wanted the first 5 digits of 2¹⁰⁰. This equals the first 5 digits of exp((frac(100 log(2)/q)-0.5)*q)*sqrt(10) = 1.267650600228226. The actual value of 2¹⁰⁰ is 1.267650600228229e+030 according to MATLAB, I don't have a bignum library handy. For the mantissa of 2^{1,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; 2^20996011-1 = 125,976,895,450... and my formula gives 1.259768950493908 calculated in MATLAB which fails after the 9th digit.)

我可能会使用泰勒系列(用于exp and log ，而不是n ^m )及其错误范围，并继续添加项，直到错误范围降到前K个数字以下. (通常我不使用泰勒级数进行函数逼近-他们的误差已优化为在单个点附近而不是在所需的时间间隔内最精确-但它们确实具有数学上简单的优势，并且您只需添加其他项就可以将精度提高到任意精度)

I might use Taylor series (for exp and log, not for n^m) 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.

这篇关于仅要求前k位数字时快速求幂?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！