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

Question

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

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

Answer 1

有两种可能性。

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

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

所以你计算 的小数部分f，n*Log10(n)然后 的前 k 位10^f将是你的结果。如果您使用双精度，这适用于大约 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 的前三位。

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

此外，如果碰巧您的 INT_MAX 小于 (10^k)^2，您可以更改 modulesExponentiation 以处理任何可以放入 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;
    }
}