Реализация простого и быстрого возведения в степень на C/C++

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

Но прежде, чем начать, почему бы не реализовать обычное возведение? Правильно, нет причин себе в этом отказывать, поехали!

Функция возведения числа в степень

Методом «в лоб», пробежимся в цикле и перемножим число само на себя сколько нужно раз. Работает за O(deg) где deg степень.

//Возводит число num в степень deg простым циклом
long power(long num, long deg) {
    long result = 1;

    for(long i = 0; i < deg; i++) {
        result *= num;
    }

    return result;
}

Для возведения по модулю достаточно будет передать этот модуль в функцию и на каждой итерации брать результат по модулю.

Функция возведения числа в отрицательную степень

Небольшое улучшение, добавим возможность возводить число в отрицательную степень. Реализуется легко, изменяем возвращаемое значение и рассматриваем два случая: для положительной степени делаем все как обычно, а для отрицательной возвращаем 1 / result.

//Возводит число num в степень deg простым циклом(степень может быть отрицательной)
double power(long num, long deg) {
    double result = 1;

    if(deg < 0) {
        deg = -deg;
        for(long i = 0; i < deg; i++) {
            result *= num;
        }

        return 1 / result;
    }
    else {
        for (long i = 0; i < deg; i++) {
            result *= num;
        }

        return result;
    }
}

Функция быстрого возведения числа в степень

Ее еще называют бинарным возведением. Алгоритм построен на очевидной формуле

Aⁿ = (A^n/2)² = A^n/2 * A^n/2

То есть для четного n можно получить результат выполнив всего log₂n перемножений, что уже дает логарифмическую сложность. А в случае, когда n нечетно, приведем его к четному виду с помощью еще одной очевидной формулы

Aⁿ = A^n-1 * Aⁿ

Реализация выглядит следующим образом.

//Быстрое возведение числа num в степень deg
long powerFast(long num, long deg) {
    long result = 1;
    while(deg) {
        if (deg % 2 == 0) {
            deg /= 2;
            num *= num;
        }
        else {
            deg--;
            result *= num;
        }
    }

    return result;
}

Функция быстрого возведения в отрицательную степень

Можно реализовать воспользовавшись аналогичным приемом, как и в простом умножении — делим алгоритм на две ветки.

//Быстрое возведение числа num в степень deg(в том числе может быть отрицательной)
double powerFast(long num, long deg) {
    double result = 1;
    if(deg < 0) {
        deg = -deg;

        while(deg) {
            if (deg % 2 == 0) {
                deg /= 2;
                num *= num;
            }
            else {
                deg--;
                result *= num;
            }
        }

        return 1 / result;
    }
    else {
        while(deg) {
            if (deg % 2 == 0) {
                deg /= 2;
                num *= num;
            }
            else {
                deg--;
                result *= num;
            }
        }

        return result;
    }
}

Заключение

Таким образом мы научились возводить число в степень с логарифмической скоростью, что пригодится для реализации умножения и деления больших чисел(кстати, сложение и вычитание уже готовы). А на сегодня у меня все, спасибо за внимание!