Есть ли какой-нибудь быстрый способ определить первые k цифр на n ^ n - PullRequest
Новая
       1

Есть ли какой-нибудь быстрый способ определить первые k цифр на n ^ n

6 голосов
/ 30 сентября 2011

Я пишу программу, в которой мне нужно знать только первые k (k может быть где-то между 1-5) числами другого большого числа, которое может быть представлено как n ^ n, где n - очень большое число.

В настоящее время я на самом деле вычисляю n ^ n и затем анализирую его как строку. Интересно, существует ли лучший, более быстрый метод?

Ответы [ 2 ]

10 голосов
/ 01 октября 2011

Есть две возможности.

Если вы хотите, чтобы первые 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.

2 голосов
/ 01 октября 2011

если вы имеете в виду наименее значимые или самые правые цифры, это можно сделать с помощью модульного умножения.Это сложность 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, вы можете изменить modularExponentiation для обработки любого N, который может поместиться в int: 

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;
    }
}
...