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

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

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

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

xⁿ = (x^m)^k

При этом m*k=n. Например: 3⁶=(3³)², 5⁷=(5⁷)¹. Это свойство является одним из основных степенных свойств, и именно на нем основывается рассматриваемый метод. Далее, заметим, что в случае, если n является четным числом, то верно следующее равенство:

xⁿ = (x^n/2)² = x^n/2 * x^n/2

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

xⁿ = x^n-1*x

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

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

#include "stdafx.h"
#include <iostream>
using namespace std;
//быстрое возведение в степень
float bpow(float x, int n)
{
float count=1;
if (!n) return 1;
while (n)
{
if (n%2==0)
{
n/=2;
x*=x;
}
else
{
n--;
count*=x;
}
}
return count;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
float x; int n;
cout<<"Основание > "; cin>>x;
cout<<"Степень > "; cin>>n;
cout<<x<<"^"<<n<<"="<<bpow(x, n);
system("pause>>void");
}

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

program Exponentiation;
uses crt;
var x: real; n: integer;
{быстрое возведение в степень}
function bpow(x: real; n: integer): real;
var count: real;
begin
if n=0 then
begin
bpow:=1; exit;
end;
count:=1;
while n>0 do
begin
if n mod 2=0 then
begin
n:=n div 2;
x:=x*x;
end
else
begin
n:=n-1;
count:=count*x;
end;
end;
bpow:=count;
end;
{основной блок программы}
begin
write('Основание > '); read(x);
write('Степень > '); read(n);
write(x, '^', n, '=', bpow(x, n));
end.