Как я могу вычислить целочисленное возведение в степень по модулю постоянной в C - PullRequest
Новая
       19

Как я могу вычислить целочисленное возведение в степень по модулю постоянной в C

4 голосов
/ 08 февраля 2020

Я хочу вычислить a b mod c, где a, b и c - целочисленные значения. Есть ли эффективный способ сделать это?

pow(a, b) % c, похоже, не работает.

1 Ответ

5 голосов
/ 08 февраля 2020

Для этой задачи функция pow, определенная в <math.h>, не является правильным инструментом по нескольким причинам:

  • вычисление больших чисел с помощью функции pow() может привести к переполнению величины, представляемой тип double и точность не обеспечат младшие разряды, необходимые для операции модуля.
  • В зависимости от его реализации в библиотеке C, pow() может давать нецелые значения для целочисленные аргументы, преобразование которых в int может обрезать до неправильных значений.
  • операция % не определена для типа double.
  • , чтобы избежать потери битов младшего разряда, нужно выполнять операцию модуля на каждом шаге.
  • для теста, это не то, чего ожидает экзаменатор.

Вместо этого следует итерационно вычислять мощность и модуль в al oop: 

unsigned exp_mod(unsigned a, unsigned b, unsigned c) {
    unsigned p = 1 % c;
    while (b-- > 0) {
        p = (unsigned long long)p * a % c;
    }
    return p;
}

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

unsigned exp_mod_fast(unsigned a, unsigned b, unsigned c)) {
    unsigned p;

    for (p = 1 % c; b > 0; b = b / 2) {
        if (b % 2 != 0)
            p = (unsigned long long)p * a % c;
        a = (unsigned long long)a * a % c;
    }
    return p;
}

Как предложено rici , использование типа unsigned long long для промежуточного продукта позволяет избежать проблем величины при больших значениях a. Вышеуказанные функции должны давать правильные результаты для всех 32-битных значений a, b и c, кроме c == 0.

Начальный шаг p = 1 % c необходим для получения результат 0 для c == 1 && b == 0. Явный тест if (c <= 1) return 0; может быть более читабельным и позволит избежать неопределенного поведения на c == 0. Вот окончательная версия с тестом для особых случаев и одним меньшим шагом: 

unsigned exp_mod_fast(unsigned a, unsigned b, unsigned c)) {
    unsigned p;

    if (c <= 1) {
        /* return 0 for c == 1, which is the correct result */
        /* also return 0 for c == 0, by convention */
        return 0;
    }
    for (p = 1; b > 1; b = b / 2) {
        if (b % 2 != 0) {
            p = (unsigned long long)p * a % c;
        }
        a = (unsigned long long)a * a % c;
    }
    if (b != 0) {
        p = (unsigned long long)p * a % c;
    }
    return p;
}

Более общий анализ доступен в статье Википедии под названием Модульное возведение в степень .

...