001 Бинарное возведение в степень Binary exponentiation

Бинарное возведение в степень (или метод бинарного возведения в степень, также известный как метод "разделяй и властвуй") — это эффективный алгоритм для вычисления степени числа. Этот метод позволяет вычислить
𝑎
𝑏
a
b
(где
𝑎
a — основание, а
𝑏
b — показатель степени) с помощью логарифмического количества умножений по сравнению с прямым умножением.

Принцип работы:

Инициализация: Начните с результата равного 1. В этой переменной будет храниться конечный результат.

Итерации: Проходите по каждому биту в показателе степени
𝑏
b:

Если текущий бит показателя степени равен 1, умножьте результат на текущее значение основания.
Независимо от значения бита, возведите основание в квадрат (умножьте его само на себя).
Окончание: После обработки всех битов в показателе степени, результат будет содержать значение
𝑎
𝑏
a
b
.

Видео 001 Бинарное возведение в степень Binary exponentiation канала ArgenCoder