🔒 Locked

A better integer power function

Started by bioagentX Dec 26, 2003 at 2:57 PM 14 replies 900+ views

Original Post

Dec 26, 2003 at 2:57 PM

I heard that there is a faster method of creating an integer power function that the function I am using right now shown below:


int IntPower(int x, int n)
{
    if(n==0)
      return 1;

   return ( x * IntPower( x, n-1))

}

The method that was suggested to be faster said that you should use the equation x^n = (x^(n/2))^2 for even values of n and x^n = x * (x^(n/2))^2 for odd values of n. I just don't know how I could use these equations in an algorithm that made the function faster and recursive. If someone thinks they know what I'm talking about and that they can help me, I'd greatly appreciate it. --BioX [edited by - BioagentX on December 26, 2003 4:00:07 PM]

Eric Lengyel

108

Eric Lengyel

Dec 26, 2003 at 3:38 PM

It sounds like you want to use binary exponentiation.

To calculate z = x^n, start with z = 1. Then go through the bits of n from most significant to least significant. For each bit, square the value of z. If the bit is 1, then also multiply by x. For example:

z = x^22

The exponent in binary is 10110. Begin with z = 1.

First bit is 1: z = z * z * x = x.
Second bit is 0: z = z * z = x^2
Third bit is 1: z = z * z * x = x^5
Fourth bit is 1: z = z * z * x = x^11
Fifth bit is 0: z = z * z = x^22

Puzzler183

Dec 26, 2003 at 3:38 PM

Uhm, that''s scary that you are using recursive functions for that. Like REALLY scary. Like OH SHIT scary.

This is very poorly written but still faster than what you have:


int pow(int x, int n)
{
  int k = 1;

  for (int i = 0; i < n; i++)
    k *= x;

  return k;
}

I''d even bet converting to floats and back is faster than what you are doing...

idinkin

Dec 26, 2003 at 4:10 PM

quote:
Original post by Puzzler183
for (int i = 0; i < n; i++)
k *= x;

You can optimise this by writing ++i in the place of i++.

It does not matter what you will reach in your life, but the way you will reach it

Puzzler183

Dec 26, 2003 at 4:20 PM

They both result in:

inc cx

Don''t they? O_o

hplus0603

Mod

3,014

hplus0603

Dec 26, 2003 at 4:30 PM

idinkin: that's a pretty funny joke, although anyone who disassembles the code will see that it doesn't matter.

The binary exponentiation is written something like this:


// a to the power of b (within reasonable limits)
long int_pow( int a, int b ) {
  long v = 1; // current value
  int s = 1; // current bit
  while( b ) {
    if( b & s ) {
      v = v * a;
      b = b & ~s;
    }
    // move on to next bit
    a = a * a;
    s = s << 1;
  }
  return v;
}

Of course, this code has overflow problems if you give it ill-conditioned input values.

Edit: added types for "a" and "b".

[edited by - hplus0603 on December 26, 2003 5:31:04 PM]

bioagentX

Author

bioagentX

Dec 26, 2003 at 5:11 PM

I know that most people probably wouldn''t use recursion for that type of function, but I''m doing these excercises out of a c++ book to learn the basics. I just want to become fairly comfortable w/ recursion. One of the excercises asks if you can write the function using the two formulas I mentioned above in a recursive fashion, but I can''t comprehend how to do it.

Promit

Mod

1,082

Promit

Dec 26, 2003 at 5:27 PM

C++ books, courses, etc will show you the fastest method of doing something about...hmm...maybe 0% of the time or so.

If you want the fastest method of doing things, you''re not going to do it recursively. Incidentally, it''s possible to write any recursive algorithm iteratively, and vice versa.

Beer Hunter

122

Beer Hunter

Dec 26, 2003 at 5:38 PM

Recursion, like anything else, should be used when it''s the best way to represent your intention. A power function, then, is a bad example.

Better exercise: write a function which outputs the solution to the Towers of Hanoi, given the number of initial rings, the number of the source tower and the number of the destination tower.

bioagentX

Author

bioagentX

Dec 26, 2003 at 6:34 PM

Yea, that''s what I''m looking for, thanks!

--BioX

bioagentX

Author

bioagentX

Dec 26, 2003 at 6:40 PM

Actually, the function doesn''t seem to work. No results appear when I try to display the value of the function. Maybe it goes into infinite recursion. Are you sure your code works?

--BioX

Krumble

Dec 27, 2003 at 1:34 AM


//n >= 1

int IntPower(int x, int n) {
  if (n == 1) return x;
  int t = IntPower(x, n>>1);
  return t*t*(n&1?x:1);
}

alvaro

1,980

alvaro

Dec 30, 2003 at 8:23 PM

There are faster methods for exponentiation. Here''s a fun example.

X power(X x, unsigned n){
  if(n==0)
    return ONE;
  if(!(n%2))
    return power(x*x,n/2);
  if(!(n%3))
    return power(x*x*x,n/3);
  if(!(n%5)){
    X t=x*x;
    return power(t*t*x,n/5);
  }
  if(!(n%17)){
    X t=x*x;
    t*=t;
    t*=t;
    return power(t*t*x,n/17);
  }
  return x*power(x,n-1);
}

Depending on how long it takes to multiply two objects of type X, the inefficiency of using recursion may not be an issue at all, and it makes the function understandable.

YoshiN

Dec 31, 2003 at 4:02 PM

quote:
Original post by idinkin
quote:
Original post by Puzzler183
for (int i = 0; i < n; i++)
k *= x;

You can optimise this by writing ++i in the place of i++.

It does not matter what you will reach in your life, but the way you will reach it

That''s only an optimization if you are using a really bad compiler. Of course, I always use ++i instead of i++ unless I need the functionality of i++ in case my code is ever compiled on a really bad compiler.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.