Метод быстрого вычисления натуральной степени п вещественного числа

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

Рассмотрим метод быстрого вычисления натуральной степени п вещественного числа х, описанный в Древней Индии ещё до нашей эры.

1. Запишем n в двоичной системе счисления.

2. Заменим в этой записи каждую единицу парой букв КХ, а каждый ноль — буквой К.

3. Вычеркнем крайнюю левую пару КХ.

4. Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X — как операцию умножения результата на х. Вначале результат равен х.

Воспользуемся этим алгоритмом для того, чтобы возвести х в степень n = 100.

1. 100 = 11001002.
2. Строим последовательность: КХКХКККХКК.
3. Вычёркиваем крайнюю левую пару КХ: КХКККХКК.
4. Вычисляем искомое значение:
К: возвести х в квадрат (х2);
X: умножить результат на х (x3);
К: возвести результат в квадрат (х6);
К: возвести результат в квадрат (х12);
К: возвести результат в квадрат (х24);
X: умножить результат на х (х25);
К: возвести результат в квадрат (х50);
К: возвести результат в квадрат (х100).

Мы вычислили сотую степень числа х за 8 умножений. Это значительно эффективнее «прямолинейного» алгоритма возведения в степень, требующего 99 операций умножения.
Я не особо понимаю, как это реализовать. Сразу говорю спасибо.

Добавлено через 1 час 58 минут
Если вы знаете как это сделать, пожалуйста, можете мне помочь.

0

3

Спасибо большое

0

papa78191, пожалуйста)

0