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.
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"); } |
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. |
Comments
To leave a comment
Algorithms
Terms: Algorithms