algorithm - n^nの最初のk桁をすばやく判別する方法はありますか

Question

私は、n ^ nとして表すことができる別の大きな数の最初のk（kは1〜5の間のどこでもかまいません）の数だけを知る必要があるプログラムを書いています。ここで、nは非常に大きな数です。

現在、私は実際にn ^ nを計算し、それを文字列として解析しています。もっと速い方法があるのだろうか。

Answer 1

2 つの可能性があります。

最初の k 桁が必要な場合 (例: 12345 の先頭桁は 1)、次の事実を使用できます。

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

fの小数部分を計算するn*Log10(n)と、 の最初の k 桁が10^f結果になります。これは、倍精度を使用する場合に丸め誤差が発生し始める前に、約 10^10 までの数値に対して機能します。たとえば、 の場合、n = 2^20最初のf = 0.57466709...510^f = 3.755494...桁は 37554 です。の場合n = 4、最初の桁は 2 です。f = 0.4082...10^f = 2.56

最初の 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); 
}

これにより、11^11 = 285311670611 の最初の 3 桁である 611 が出力されます。

この実装は、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;
    }
}