Эффективный способ вычисления p ^ q (возведение в степень), где q - целое число

Question

Как эффективно вычислить p ^q , где q - целое число?

Answer 1

Вычисление по квадрату использует только умножения O (lg q ).

template <typename T>
T expt(T p, unsigned q)
{
    T r(1);

    while (q != 0) {
        if (q % 2 == 1) {    // q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }

    return r;
}

Это должно работать на любом моноиде (T, operator*) где T, построенный из 1, является единичным элементом.Это включает все числовые типы.

Расширить это до signed q очень просто: просто разделите единицу на результат выше для абсолютного значения q (но, как обычно, будьте осторожны при вычислении абсолютного значения).

Answer 2

Предполагая, что ^ означает возведение в степень и что q является переменной времени выполнения, используйте std::pow(double, int).

РЕДАКТИРОВАТЬ: Для полноты из-за комментариев к этому ответу: я задал вопрос Почемубыл ли std :: pow (double, int) удален из C ++ 11? по поводу отсутствующей функции и фактически pow(double, int) не был удален в C ++ 0x, только язык был изменен.Однако, похоже, что библиотеки могут не оптимизировать его из-за проблем с точностью результатов.

Даже учитывая, что я все еще буду использовать pow, пока измерение не покажет мне, что его нужно оптимизировать.

Answer 3

Я предполагаю, что под ^ вы подразумеваете степенную функцию, а не побитовую xor.

Разработка эффективной степенной функции для любого типа p и любого положительного интеграла q является предметом целый раздел, 3.2, в книге Степанова и МакДжонса Элементы программирования .Язык в книге не C ++, но очень легко переводится на C ++.

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