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

Лекция

Привет, сегодня поговорим про быстрое возведение в степень, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое быстрое возведение в степень , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Для возведения числа 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. Об этом говорит сайт https://intellect.icu . Используя это свойство, удастся существенно уменьшить число операций необходимых для возведения x в степень n. Теперь адаптируем формулу для случая с нечетным n. Для этого понадобиться просто перейти к степени на единицу меньшей. Например: 5⁷ = 5⁶*5, 12⁵ = 12⁴*12. Общая форма равенства перехода:

xⁿ = x^n-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.

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

Из статьи мы узнали кратко, но содержательно про быстрое возведение в степень

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

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

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

Комментарии

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

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов