Getting x raised to the nth power
-
18-06-2021 - |
문제
I'm a newbie and I know that this C program which I got somewhere on the Internet (credits: http://www.geeksforgeeks.org/archives/28) works properly.
#include<stdio.h>
float power(float x, int y)
{
float temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
{
if(y > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}
}
/* Program to test function power */
int main()
{
float x=2;
int y=5;
printf("%f", power(x, y));
getchar();
return 0;
}
I'm just wondering how and why. I made my questions/remarks a comment after the line of my the code in this function...
float temp;
if( y == 0)
return 1;
//this I understand because for instance 2^0 is 1
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
//if y is even, eg. 2^4 then 2^2 * 2^2 is still equal to 16
else
{
if(y > 0)
//this part I don't get anymore. eg. 2^5, then temp=2^(5/2)
return x*temp*temp;
//2 * 2^(5/2) * 2^(5/2) how? this will become 64 but the answer is 32.
//but when I run the program it halts the right answer ie, 32
else
return (temp*temp)/x;
}
Kindly explain to me what happened. Maybe I just missed something. And also how it became a O(lg n) running time. Thank you very much!
해결책
Note that the y/2
used to calculate temp is integer division. So in your commented questions, the result of 5/2 will be 2, not 2.5.
다른 팁
It is hard to compete with Wikipedia's explanation of exponentiation by squaring, but here is my take.
The key to the answer is in this formula:
a^(b*c) == ((a^b)^c)
This immediately answers the "what to do when the power is even" question: if y=2*k
, then you could first square x
, and then raise the result to the power of k
.
The case of the odd power is a bit more complex: let's rewrite
x ^ (2*k+1)
as
(x ^ 2*k) * x
Now you see what happens in that else
branch: they subtract one from the odd number making it even, get x ^ (y-1)
, and multiply it by x
in the end.*
Now for the time complexity: each step reduces the y
by half, so the number of times the recursive call is made is O(Log2(N))
.
* The implementation does not subtract
1
from y
explicitly. Rather, it performs an integer division of y/2
, which discards the remainder of the division.
/* if y is even and positive, e.g., 5, then floor of y/2 is (y-1)/2, e.g. 4/2
then x^((y-1)/2 + (y-1)/2 + 1) = x^y, e.g., x * x^2 * x^2 = x^(1+2+2) = x^5) */
if(y > 0)
return x*temp*temp;
/* if y is even and negative, e.g., -5, then floor of y/2 is (y+1)/2, e.g. -4/2
then x^((y+1)/2 - (y+1)/2 - 1) = x^y, e.g., x^-1 * x^-2 * x^-2 = x^(-1-2-2) = x^-5) */
else
return (temp*temp)/x;
As for the complexity O(lgn), since you are dividing by 2 before each recursive power call, you will do lg(n) calls at most.
This is a somewhat-clunky implementation of the usual xn algorithm, which repeatedly squares x while halving n. Odd n
takes extra handling: At every step, you check if n is odd, and multiply another factor.
Alexander Stepanov's1 very nice lecture series on generic/templated algorithms explains the origin of this one:
It's from the ancient Egyptian algorithm for multiplying by repeated addition while halving n
.
The first lecture starts of with pretty easy stuff, but get good. He has fun asides and stories. He starts with a recursive algo for multiplication by repeated addition, and refines it in various ways. He gets to the point of replacing + with * to make this exponentiation algo near the end of lecture 2 (of 4).
1: Stepanov designed and implemented much of C++'s STL. He was one of the very early inventors / pioneers of generic programming. I enjoyed his lectures, and would recommend them.
This particular implementation doesn't look great to me.
I haven't thought about it, but surely there's a better way to handle negative odd n
than division. This may be a quirk of the rounding direction for C's integer division? (It's different from an arithmetic right shift, even on C implementations which do an arithmetic shift at all for >>
on a signed operand. The C standard doesn't require that, but on some specific C implementations it does have defined behaviour.)
Also, the variable names are misleading: usually you'd expect y
to have the same type as x
. If you're mixing integer and FP variables, use names like n
for the integers.
private int nthPower(int num, int power)
{
int [] arr = new int[power+1];
arr[0] = 1; // Any number to the power '0' is '1'
arr[1] = num; // Any number to the power '1' is num itself.
int i =2;
//Now in the for loop you just fill the next element in the array
// by multiplying the num with its previous result. Once you are out
// of loop you have the desired answer in 'i-1' th index.
for (i =2; i<=power;i++)
{
arr[i] = num*arr[i-1];
}
return arr[i-1]; //This is your answer
}