Intereting Posts
Что такое возвращаемое значение int plus uint? C | Разделить четные и нечетные узлы в связанном списке Является ли scanf («% d% d», & x, & x) четко определенным? Где будет храниться постоянная строка в памяти? Шаблон, чтобы предотвратить постоянную проверку ошибки? Как масштабировать число / диапазон чисел в c При привязке клиентского TCP-сокета к конкретному локальному порту с Winsock SO_REUSEADDR не имеет никакого эффекта В то время как (1) {} выполняет то же самое, что и (1); Аутентификация или другое подписание кода для Mac и Linux измененный массив в области файлов в C Получите количество элементов, которые имеют значение в массиве Socket uneclared, когда я использую -std = c99 Как остановить мой процесс, если я найду список в отсортированном в любом промежуточном пункте IN IN BUBBLE SORT? Единичный тест C с ключевыми словами для компилятора Ubuntu рекурсивно перечисляет файлы, обнаруживая sym-ссылки

Оптимизированный способ обработки чрезвычайно большого количества без использования внешней библиотеки

Оптимизированный способ обработки значения n ^ n (1 ≤ n ≤ 10 ^ 9)

Я использовал long long int но это недостаточно хорошо, поскольку значение может быть (1000 ^ 1000)

Искал и нашел GMP library http://gmplib.org/ и BigInt class но не хочу их использовать. Я ищу некоторый численный метод для этого.

Мне нужно напечатать первую и последнюю k (1 ≤ k ≤ 9) цифры n^n

Для первых k цифр я получаю это, как показано ниже (это немного уродливый способ сделать это)

 num = pow(n,n); while(num){ arr[i++] = num%10; num /= 10; digit++; } while(digit > 0){ j=digit; j--; if(count<k){ printf("%lld",arr[j]); count++; } digit--; } в num = pow(n,n); while(num){ arr[i++] = num%10; num /= 10; digit++; } while(digit > 0){ j=digit; j--; if(count<k){ printf("%lld",arr[j]); count++; } digit--; } 

и для последних k цифр, используя num % 10^k как показано ниже.

 findk=pow(10,k); lastDigits = num % findk; enter code here 

максимальное значение k равно 9., поэтому мне нужно всего 18 цифр при макс. Я думаю о том, чтобы получить эти 18 цифр без реального решения полного n ^ n выражения.

Любая идея / предложение?

Поиск наименее значимых цифр (последние k цифр) легко из-за свойства модульной арифметики, в котором говорится: (n*n)%m == (n%m * n%m)%m , поэтому код, показанный BLUEPIXY который следовал за возведением в степень методом квадратизации, будет хорошо работать для нахождения k LSD.

Теперь наиболее значимые цифры (1-го числа) N^N можно найти следующим образом:

  We know, N^N = 10^(N log N) 

Поэтому, если вы вычислите N log (N) вы получите номер этого формата xxxx.yyyy , теперь мы должны использовать это число как мощность 10, легко понять, что xxxx или целая часть числа добавят нули xxxx после 10, что не важно для вас! Это означает, что если вы подсчитаете 10^0.yyyy , вы получите эти значащие цифры, которые вы ищете. Таким образом, решение будет примерно таким:

 double R = N * log10 (N); R = R - (long long) R; //so taking only the fractional part double V = pow(10, R); int powerK = 1; for (int i=0; i 
 // note: Scope of use is limited. #include  long long powerMod(long long a, long long d, long long n){ // a ^ d mod n long long result = 1; while(d > 0){ if(d & 1) result = result * a % n; a = (a * a) % n; d >>=1; } return result; } int main(void){ long long result = powerMod(999, 999, 1000000000);//999^999 mod 10^9 printf("%lld\n", result);//499998999 return 0; } 

Почему вы не хотите использовать библиотеки bigint ?

bignum арифметика очень трудно сделать правильно и эффективно. Вы все еще можете получить степень доктора философии, работая над этим вопросом.

Арифметика Fist, bigint имеет нетривиальную алгоритмику

Тогда для реализации bigint обычно требуются некоторые машинные инструкции (например, add with carry), которые нелегко доступны на обычном C.

Для вашей конкретной проблемы (первая и последняя несколько цифр N N ) вам лучше также обосноваться на бумаге (используя арифметические теоремы), чтобы снизить сложность. Я не эксперт, но, я думаю, это все еще остается неразрешимым, возможно, со сложностью, чем O (N)