Быстрое возведение в степень.

Для возведения числа x в степень n, как правило, используют стандартный метод, т. е. число x умножают n раз само на себя. В задачах математического толка, решаемых при помощи бумаги и ручки, такой метод вполне приемлем, ведь степенная функция быстро растет и поэтому сомнительно, что придется производить затруднительные операции вручную.


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

Пусть имеется некоторая степень xn, где x – действительное число, а n – натуральное. Тогда для xn справедливо равенство:

xn = (xm)k

При этом m*k=n. Например: 36=(33)2, 57=(57)1. Это свойство является одним из основных степенных свойств, и именно на нем основывается рассматриваемый метод. Далее, заметим, что в случае, если n является четным числом, то верно следующее равенство:

xn = (xn/2)2 = xn/2 * xn/2

Так, если x=3, а n=6, то имеем 36 = (36/2)2 = 36/2 * 36/2. Используя это свойство, удастся существенно уменьшить число операций необходимых для возведения x в степень n. Теперь адаптируем формулу для случая с нечетным n. Для этого понадобиться просто перейти к степени на единицу меньшей. Например: 57 = 56*5, 125 = 124*12. Общая форма равенства перехода:

xn = xn-1*x

В программе, реализующей алгоритм быстрого возведения в степень, используются указанные свойства: если степень n четная, то переходим к степени вдвое меньшей, иначе заменяем по имеющимся правилам нечетную степень на четную.

Код программы на C++:

Код программы на Pascal:

 


Похожие записи:
1 комментарий
  • Было бы не плохо выложить еще пример кода на ассемблере 🙂 чтобы реализовать конкретно этот «быстрый» алгоритм мне понадобилось оперативки = e * b * 3 (байт), где e — степень, b — длина исходного числа в байтах, не считая стандартных входных проверок исходных данных на 0 и 1 и довольно громоздкого кода перемножения чисел из оперативки с меняющейся по ходу выполнения цикла длиной. Выигрыш можно почувствовать только на больших степенях и то весьма сомнительный..

    Ответить

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *