Quick exponentiation

Lecture



To raise the number x to the power n, as a rule, the standard method is used, that is, the number x is multiplied n times by itself. In mathematical problems solved with paper and pens, this method is quite acceptable, because the power function is growing rapidly and therefore it is doubtful that it will be necessary to perform difficult manual operations.

Another thing is programming, where it is important not only to solve the problem posed, but also to create an optimal solution that satisfies the intended range of input data. So, in particular, for the operation of raising a number to a power, there is an algorithm that allows to significantly reduce the number of required operations. It is quite simple and is based on the mathematical properties of degrees.

Let there be some power x n , where x is a real number, and n is a natural number. Then for x n the equality is true:

x n = (x m ) k

Moreover, m * k = n. For example: 3 6 = (3 3 ) 2 , 5 7 = (5 7 ) 1 . This property is one of the main power properties, and the method in question is based on it. Further, note that if n is an even number, then the following equality holds:

x n = (x n / 2 ) 2 = x n / 2 * x n / 2

So, if x = 3, and n = 6, then we have 3 6 = (3 6/2 ) 2 = 3 6/2 * 3 6/2 . Using this property, it will be possible to significantly reduce the number of operations necessary for raising x to the power n. Now we adapt the formula for the case with odd n. To do this, you just need to go to the degree on the unit less. For example: 5 7 = 5 6 * 5, 12 5 = 12 4 * 12. The general form of equality of transition:

x n = x n-1 * x

In the program that implements the algorithm of rapid exponentiation, these properties are used: if the degree n is even, then we go to the degree twice as low, otherwise we replace the odd degree by even the existing ones.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32
33
#include "stdafx.h"
#include <iostream>
using namespace std;
// quick exponentiation
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;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
float x; int n;
cout << "Foundation>"; cin >> x;
cout << "Degree>"; cin >> n;
cout << x << "^" << n << "=" << bpow (x, n);
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32
33
program Exponentiation;
uses crt;
var x: real; n: integer;
{quick exponentiation}
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;
{main program block}
begin
write ('Foundation>'); read (x);
write ('Degree>'); read (n);
write (x, '^', n, '=', bpow (x, n));
end.
created: 2014-11-30
updated: 2021-03-13
132646

Rating 9 of 10. count vote: 2
Are you satisfied?:

Comments

To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms