The power of an integer in C ++

Question

I need to get the result from pow(a,b) as an integer (both a and b are also integers). Currently, calculations in which (int) pow( (double)a, (double)b) are turned on are incorrect. Maybe someone can help with a function that performs the function pow (a, b) with integers and returns an integer?

But here is the odd part: I made my Linux script with Geany (and the g ++ / gcc compiler) and only had the pow(a,b) script compiled and working fine. But at university I have Dev-C ++ (and MS Windows). In Dev-C ++, the script did not compile with the error [Warning] converting to int 'from double'

I need to make this script work under Windows (and the Mingw compiler) too.

Thanks in advance,

-skazhy

Answer 1

A good recursive approach that you can show:

 int myPow(int x, int p) { if (p == 0) return 1; if (p == 1) return x; return x * myPow(x, p-1); } 

Answer 2

Better recursive approach than Zed's, I don't know why you closed so Zed: x

 int myPow(int x, int p) { if (p == 0) return 1; if (p == 1) return x; int tmp = myPow(x, p/2); if (p%2 == 0) return tmp * tmp; else return x * tmp * tmp; } 

It is much more complicated there O (log² (p)) instead of O (p). I must add that this is really a classic ...

Answer 3

Or you could use a little metaprogramming of the template :)

 template<int X, int P> struct Pow { enum { result = X*Pow<X,P-1>::result }; }; template<int X> struct Pow<X,0> { enum { result = 1 }; }; template<int X> struct Pow<X,1> { enum { result = X }; }; int main() { std::cout << "pow(3,7) is " << Pow<3,7>::result << std::endl; return 0; } 

This code has better complexity, O (1), because the evaluation will be performed at compile time. Of course, this will only work with integer values. However, this feature is provided only for completeness (and fun).

Answer 4

Mostly in response to simple Zeds recursion ...

Why is recursion considered better than iteration? Especially in C ++. What happened with...

 int myPow (int x, int p) { int i = 1; for (int j = 1; j <= p; j++) i *= x; return i; } 

I am not saying that your answer is incorrect or somehow worse - it’s just that I got the impression that you think it is good, because it is recursive. IMO, especially in C ++, that biasing can lead to slow and even broken programs. Slow programs because you grow a huge stack, causing cache and virtual memory. Broken programs because you get a stack overflow where an iterative solution will work.

Some will look at your answer and consider the tail recursive and in any case will be optimized for iteration. Of course, this is not so - after the exit of each recursive call, there are many more times to do it, so it is not tail recursive. The fact is that in C ++ there are many more subtle things that prevent tail recursion optimization - even if the compiler does them at all. For example...

 void myrecurse (plan *p) { plan i; i.prev = p; // more plan setup, checks, and special case handling myrecurse (&i); } 

In this case, all instances of the "plan" should remain on the stack. Therefore, stack frames cannot be discarded. Therefore, this is not optimized in the iteration, although after a recursive call exactly zero operations are performed. Not even hidden operations, such as cleaning destructors, since it is assumed that the plan is a POD structure.

By the way, this is based on what I did in real code - the data structure operation, which was planned during the recursion, but nothing changes in the source nodes until the recursion reaches the root / sheet, all the necessary new nodes were successfully distributed All locks have been acquired and there are no changes to get worse. At this point, iteration is performed through a linked list of plan instances to commit changes — the logic was more clear as an iteration than broken down into fragments related to the deployment of recursive calls.

Here, obviously, one should not say that recursion is automatically bad. It just makes me nervous when people seem to think that recursion is better than default iteration.

Answer 5

I assume your homework is to write an exponential integral function. First, look at what a metric is:

http://en.wikipedia.org/wiki/Exponent

Then take a look at the tutorial to multiply the numbers by C. You want to use the for loop.

Answer 6

Would the tailing dump function be better? Something like:

 int myPow_helper(int x, int p, int result) { if (p == 0) { return result; } else { return myPow_helper(x, p-1, result*x); } } int myPow(int x, int p) { return myPow_helper(x, p, 1); } 

Answer 7

Instead of inserting double into int in the string (int) pow((double)a, (double)b) , try to round the results of pow, and then translate to int if necessary.

This is probably one of the problems with floating point when you are truncating, especially if your result is disabled by one.

Answer 8

The C ++ standard does not have int pow(int, int) (it has double pow(double, int) , float ... ). Microsoft cmath uses C math.h, which does not have ipow. Some cmath headers define the pow template version.

 $ cat main.cpp #include <cmath> int main() { std::pow(2,2); } $ gcc main.cpp # this cmath has template pow ...snip... std::pow<int, int>(int, int)]+0x16): undefined reference to `pow' collect2: ld returned 1 exit status 1 ;( user@host: $ gcc main.cpp -lm 

Find : ipow lang: C ++ in Google Code.

Here is an example from the first link:

 template <typename Type1, typename Type2> Type1 ipow(Type1 a, Type2 ex) // Return a**ex { if ( 0==ex ) return 1; else { Type1 z = a; Type1 y = 1; while ( 1 ) { if ( ex & 1 ) y *= z; ex /= 2; if ( 0==ex ) break; z *= z; } return y; } } 

See the calculation of integer degrees (squares, cubes, etc.) in C ++ code .

Answer 9

Binary nutrition, aka squaring .

 int powi (int base, unsigned int exp) { int res = 1; while (exp) { if (exp & 1) res *= base; exp >>= 1; base *= base; } return res; } 

Note that this returns 1 for powi (0,0).

Answer 10

Why linear? Try it logarithmically !!

 long long powx( int val, int exp ) { long long actual = val; long long prod = 1; int i; for ( i = 0; i < 32; i++ ) { if ( exp & 0x1 ) { prod *= actual; } exp >>= 1; actual *= actual; } return prod; } 

Answer 11

There are two alternatives here: when we want to calculate the power (a, n), we can write code that is very short and works in O (logn), but recursively and therefore requires the creation of a new stack frame for each call and takes a little longer than repeating the cycle. So the short code is:

 int power(int a, int n){ if(n == 0) return 1; int keep = power(a,n/2); if(n & 1) return keep*keep*a; // (n & 1) is and operation of 1 and the return keep*keep; // last bit of n } 

and for faster code, the while loop is used here:

 int power(int a, int n) { int res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; }