Nik*_*hil 8 math exponentiation
这实际上是为了编程比赛,但我已经非常努力,甚至没有得到最微弱的线索如何做到这一点.
找到n m的第一个和最后一个k位数,其中n和m可以非常大~10 ^ 9.
对于最后的k位数,我实现了模幂运算.
对于第一个k,我想到使用二项式定理达到某些幂,但这涉及到因子的大量计算,我不知道如何找到n ^ m可以扩展为(x + y)的最佳点米.
那么有没有任何已知的方法来查找前k个数字而不执行整个计算？
更新 1 <= k <= 9并且k将始终<= n m中的数字
不确定，但是恒等式 n m = exp10(m log10(n)) = exp(q (m log(n)/q)) 其中 q = log(10) 浮现在脑海中，以及第一个 K exp10(x) 的数字 = exp10(frac(x)) 的前 K 位数字，其中 frac(x) = x = x - Floor(x) 的小数部分。
更明确地说：n m的前 K 位是其尾数的前 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 之间），以便快速收敛。
（一些示例：假设您想要 2 100的前 5 位数字。这等于 exp((frac(100 log(2)/q)-0.5)*q)*sqrt(10) = 1.267650600228226 的前 5 位数字。根据MATLAB，2 100的实际值为1.267650600228229e+030，我手头没有一个 bignum 库。对于 2 1,000,000,000的尾数，我得到 4.612976044195602 但我真的没有办法检查......有一个关于梅森素数的页面，有人已经完成了艰苦的工作；2 20996011 -1 = 125,976,895,450...我的公式给出了 1.259768950493908 在 MATLAB 中计算，在第 9 位数字后失败。）
我可能会使用泰勒级数（用于 exp和 log，而不是 nm ）及其误差范围，并不断添加项，直到误差范围降至前 K 位以下。（通常我不使用泰勒级数进行函数逼近——它们的误差被优化为在单个点周围最准确，而不是在期望的间隔上——但它们确实有一个优点，那就是它们在数学上很简单，而且你只需添加附加项即可将准确度提高到任意精度）
对于对数，我会使用您最喜欢的近似值。