Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени.

Алгоритм не всегда оптимален: например, быстрое возведение в степень n = 15 потребует 6 умножений, хотя возведение в 15-ю степень можно выполнить и за 5 умножений.

Описание

Пусть  — двоичное представление степени n, то есть,

где . Тогда

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера:

Вычислительная сложность

Количество умножений, требуемое для возведения числа x в степень n алгоритмом быстрого возведения в степень, даётся формулой: , где H — количество нулей, а E — количество единиц в двоичной записи числа n. Таким образом, количество умножений равно .

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 умножений.

Обобщения

Пусть пара (S, *) — полугруппа, то есть S — произвольное множество, на котором задана бинарная операция * такая, что:

• Для любых элементов a и b из S справедливо: (a * b) так же из S. (замкнутость)
• Для любых элементов a, b и c из S справедливо: ((a * b) * c) = (a * (b * c)). (ассоциативность)

Мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

Для вычисления значений aⁿ можно использовать алгоритм быстрого возведения в степень.

Ссылки

• Валицкас А. И. Конспект лекций по дисциплине: Элементы абстрактной и компьютерной алгебры. // Тобольск, ТГПИ им. Д. И. Менделеева, 2004.