# Q：利用动态规划pow函数计算

I know that pow(base, power) is a built-in function in C with complexity O(power). Can I reduce the complexity of it by dynamic programming?

You can calculate it in O(logn)

``````int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
``````

Details in Here

``````int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
``````

If your input arguments are non-negative integers, then you can implement your own pow.

Iteratively, with running time = O(n):

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
unsigned long long res = 1;
while (n--)
res *= x;
return res;
}
``````

Recursively, with running time = O(n):

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
return pow(x,n/2)*pow(x,n-n/2);
}
``````

Efficiently, with running time = O(log(n)):

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
unsigned long long res = 1;
while (n > 0)
{
if (n & 1)
res *= x;
n >>= 1;
x *= x;
}
return res;
}
``````

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
unsigned long long res = 1;
while (n--)
res *= x;
return res;
}
``````

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
return pow(x,n/2)*pow(x,n-n/2);
}
``````

``````unsigned long long pow(unsigned long long x,unsigned int n)
{
unsigned long long res = 1;
while (n > 0)
{
if (n & 1)
res *= x;
n >>= 1;
x *= x;
}
return res;
}
``````
c++  dynamic-programming