Вычисление суммы степеней числа по модулю: рекурсивный и итеративный подходы

Delphi , Синтаксис , Математика

В статье рассматривается алгоритм вычисления суммы степеней числа A от 1 до k по модулю m, без использования обратного модульного элемента. Для этого используются рекурсивные и итеративные подходы.

Рекурсивный подход

Сумма степеней числа A от 1 до k по модулю m может быть вычислена рекурсивно следующим образом:

Для чётного k: [ 1 + A + A^2 + ... + A^k = 1 + (A + A^2)(1 + A^2 + (A^2)^2 + ... + (A^2)^{k/2-1}) ]

Для нечётного k: [ 1 + A + A^2 + A^3 + ... + A^k = (1 + A)(1 + A^2 + (A^2)^2 + ... + (A^2)^{(k-1)/2}) ]

Такой подход позволяет уменьшить размерность задачи в два раза на каждом шаге рекурсии, что приводит к сложности алгоритма O(log k).

Пример реализации на Java:

static int modSumAtoAk(int A, int k, int mod) {
    return (modSum1ToAk(A, k, mod) + mod - 1) % mod;
}

static int modSum1ToAk(int A, int k, int mod) {
    long sum;
    if (k < 5) {
        // Если k маленькое, просто перебираем
        sum = 0;
        long x = 1;
        for (int i = 0; i <= k; ++i) {
            sum = (sum + x) % mod;
            x = (x * A) % mod;
        }
        return (int) sum;
    }
    // Если k большое
    int A2 = (int) ((long) A * A % mod);
    if ((k % 2) == 0) {
        // k чётное
        sum = modSum1ToAk(A2, (k / 2) - 1, mod);
        sum = (sum + sum * A) % mod;
        sum = ((sum * A) + 1) % mod;
    } else {
        // k нечётное
        sum = modSum1ToAk(A2, (k - 1) / 2, mod);
        sum = (sum + sum * A) % mod;
    }
    return (int) sum;
}

Итеративный подход

Итеративный подход позволяет вычислить сумму без использования дополнительной памяти для хранения промежуточных результатов. Пример реализации на Java:

static int modSumAtoAk(int A, int k, int mod) {
    // Вычисляем сумму всех чисел от 1 до A^k
    long fac = 1;
    long add = 0;

    // INVARIANT: SUM1 = add + fac*(sum 1...A^k)
    // Это будет верно при изменении k

    while (k > 0) {
        // INVARIANT верен и здесь

        long newmul, newadd;
        if ((k % 2) == 0) {
            // k чётное. sum 1...A^k = 1+A*(sum 1...A^(k-1))
            newmul = A;
            newadd = 1;
            k -= 1;
        } else {
            // k нечётное.
            newmul = A + 1L;
            newadd = 0;
            A = (int) (((long) A) * A % mod);
            k = (k - 1) / 2;
        }
        // SUM1 = add + fac * (newadd + newmul*(sum 1...Ak))
        // SUM1 = add+fac*newadd + fac*newmul*(sum 1...Ak)

        add = (add + fac * newadd) % mod;
        fac = (fac * newmul) % mod;

        // INVARIANT восстановлен
    }

    // k == 0
    long sum1 = fac + add;
    return (int) ((sum1 + mod - 1) % mod);
}

Комментарии

По поводу вопроса о добавлении 'mod' к 'sum1' в итоговом результате: в исходном алгоритме вычисляется сумма чисел от 1 до A^k, включая единицу. Однако, итоговый результат должен не включать эту единицу, поэтому в конце вычитание единицы приводит к ошибке, так как может быть получено отрицательное значение. Вместо этого, для сохранения положительности, вычитается 1 и затем прибавляется модуль, что дает тот же результат, но без риска перехода в отрицательную область.

В данной статье представлены алгоритмы, которые могут быть полезны при работе с криптографическими протоколами и алгоритмами, где требуется вычисление суммы степеней по модулю без использования обратного модульного элемента.

Эти методы также могут быть адаптированы для использования в языках программирования, поддерживающих Object Pascal, например, в Delphi, с соответствующей адаптацией типов данных и синтаксиса.

Создано по материалам из источника по ссылке.

Статья рассматривает алгоритмы для вычисления суммы степеней числа по модулю, используя рекурсивные и итеративные подходы без применения обратного модульного элемента.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::