«

»

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

Для возведения числа 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++:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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.

1 комментарий

  1. Tony

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

Добавить комментарий

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

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *