有没有快速的方法来确定 n^n 上的前 k 位数字

Question

我正在编写一个程序，我只需要知道另一个大数字的前 k 个（k 可以是 1-5 之间的任意数字），该大数字可以表示为 n^n，其中 n 是一个非常大的数字。

目前我实际上正在计算 n^n ，然后将其解析为字符串。我想知道是否有更好更快的方法存在。

Answer 1

有两种可能性。

如果您想要前 k 个前导数字（例如：12345 的前导数字是 1），那么您可以使用以下事实来

n^n = 10^(n*Log10(n))

计算 n*Log10( n)，然后 10^f 的前 k 位数字就是你的结果。如果您使用双精度，则这适用于在舍入误差开始出现之前达到约 10^10 的数字。例如，对于 n = 2^20、f = 0.57466709...、10^f = 3.755494... 所以你的前 5 个位数为 37554。对于 n = 4、f = 0.4082...、10^f = 2.56 所以你的第一个数字是 2。

如果你想要前 k 个尾随数字（例如：12345 的尾随数字是 5），那么你可以使用模算术。我会使用平方技巧：

factor = n mod 10^k
result = 1
while (n != 0) 
    if (n is odd) then result = (result * factor) mod 10^k
    factor = (factor * factor) mod 10^k
    n >>= 1

再次以 n=2^20 为例，我们发现 result = 88576。对于 n=4，我们有 factor = 1, 4, 6 和 result = 1, 1, 6，所以答案是 6。

Answer 2

如果您指的是最低有效数字或最右边的数字，则可以通过模乘法来完成。它的复杂度为 O(N)，并且不需要任何特殊的 bignum 数据类型。

#include <cmath>
#include <cstdio>

//returns ((base ^ exponent) % mod)
int modularExponentiation(int base, int exponent, int mod){
    int result = 1;
    for(int i = 0; i < exponent; i++){
        result = (result * base) % mod;
    }
    return result;
}

int firstKDigitsOfNToThePowerOfN(int k, int n){
    return modularExponentiation(n, n, pow(10, k));
}

int main(){
    int n = 11;
    int result = firstKDigitsOfNToThePowerOfN(3, n);
    printf("%d", result); 
}

这将打印 611，即 11^11 = 285311670611 的前三位数字。

此实现适用于小于 sqrt(INT_MAX) 的 N 值，该值会有所不同，但在我的机器和语言上它超过 46,000。

此外，如果您的 INT_MAX 小于 (10^k)^2，您可以更改 modularExponentiation 来处理可以适合 int 的任何 N：

int modularExponentiation(int base, int exponent, int mod){
    int result = 1;
    for(int i = 0; i < exponent; i++){
        result = (result * (base % mod)) % mod; //doesn't overflow as long as mod * mod < INT_MAX
    }
    return result;
}

如果 O(n) 时间对您来说不够，我们可以利用求幂的性质 A^(2*C) = (A^C)^2，并得到对数效率。

//returns ((base ^ exponent) % mod)
int modularExponentiation(int base, int exponent, int mod){
    if (exponent == 0){return 1;}
    if (exponent == 1){return base % mod;}
    if (exponent % 2 == 1){
        return ((base % mod) * modularExponentiation(base, exponent-1, mod)) % mod;
    }
    else{
        int newBase = modularExponentiation(base, exponent / 2, mod);
        return (newBase * newBase) % mod;
    }
}