It's maybe stupid question, but I can't find any function in C++ for square and higher orders, like x^2, x^3 ....

Printable View

- 10-17-2002skibbersquare and cubic functions in C++
It's maybe stupid question, but I can't find any function in C++ for square and higher orders, like x^2, x^3 ....

- 10-17-2002Sebastiani
/*whew*/ ... man, I've spent hours perfecting this code for you! :p

Code:

template <typename number>

number squared( number n ) {

return (n*n);

}

template <typename number>

number cubed( number n ) {

return (n*n*n);

}

- 10-17-2002Sebastiani
For higher orders, use:

Code:

template <typename number>

number exponential( number n, int order ) {

if( order == 0 ) {

return 0;

}

number value = n;

while(--order) {

value *= n;

}

return value;

}

- 10-17-2002skibber
Thanx! But that the easiest way??? It seems to me very complicated for simple function like that...

- 10-17-2002skibber
That was what I was looking for! It works with float's too ;o)

- 10-17-2002Nick
This should be pretty fast for positive integer exponents.

You can make it even faster by taking out the recursion.

It takes advantage of the fact that (a ^ (n/2))^2 = a^n.

Code:`int exp(int a, int n)`

{

int r;

if (n == 0)

{

r = 1;

}

else

{

if (n % 2 == 0)

{

r = exp(a, n/2);

r *= r;

}

else

{

r = exp(a, n-1) * a;

}

}

return r;

}

- 10-17-2002Sebastiani
Hmm, nice code, Nick. And I wasn't aware of that fact either. I spotted a place where you could speed it up even more, though, by shifting n once to the right instead of dividing by two.

Code:

int exp(int a, int n)

{

int r;

if (n == 0)

{

r = 1;

}

else

{

if (n % 2 == 0)

{

r = exp(a, (n >> 1) );

r *= r;

}

else

{

r = exp(a, n-1) * a;

}

}

return r;

}

And I think making this solution non-recursive would slow down the algorithm due to the additional manipulations, not to mention making it far more unreadable (of course, if you were using it for graphics, readability would be a non-issue...). - 10-17-2002moi
use pow() -- it will be faster and more versatile than anything you can come up with

- 10-17-2002Nick
You could also

take out n % 2 == 0 with !(n & 0x00000001). I think

most compilers would see these optimizations if I had used

unsigned int. Another way to speed it up would be

to store maybe the first 200 or so in a table. - 10-17-2002SebastianiQuote:

You could also take out n % 2 == 0 with !(n & 0x00000001).

Let's time the following:

number exponential( number n, int order );

int exp(int a, int n); //..v1.0, v2.0, v.3.0, and the table lookup version.

Sound like fun? - 10-17-2002Sebastiani
The template won!

I didn't use the table lookup, but you can easily add it:

printout:

Quote:

Looping Template: 8 seconds to run 10, 000, 000 iterations...

Recursive #1: 12 seconds to run 10, 000, 000 iterations...

Recursive #2: 9 seconds to run 10, 000, 000 iterations...

Recursive #3: 10 seconds to run 10, 000, 000 iterations...

- 10-17-2002Nick
I think for mine to be faster than yours I think n would

have to be pretty large. In which case

the results would overflow an integer.

You could try this version that uses long double.

Code:`#include <iostream>`

using namespace std;

long double exp(long double a, unsigned int n);

int main(void)

{

long double a = 1.5;

int n = 300;

cout << a << "^" << n << " = " << exp(a, n) << endl;

return 0;

}

long double exp(long double a, unsigned int n)

{

unsigned int mask = 0xffffffff;

unsigned int t = n;

long double r = a;

if (n == 0)

return 1.0;

// this finds mask such

// that if n = 0x00001010

// mask = 0x00000100

// there's probably a faster way to do

// it but it shouldn't matter much if n is large

while(t != 0)

{

mask <<= 1;

t &= mask;

}

mask = ~mask;

mask ^= (mask >> 1);

mask >>= 1;

while(mask != 0)

{

r *= r;

if (n & mask)

{

r *= a;

}

mask >>= 1;

}

return r;

}

- 10-17-2002Sang-draxQuote:

*Originally posted by Sebastiani*

Looping Template: 8 seconds to run 10, 000, 000 iterations...

Recursive #1: 12 seconds to run 10, 000, 000 iterations...

Recursive #2: 9 seconds to run 10, 000, 000 iterations...

Recursive #3: 10 seconds to run 10, 000, 000 iterations...

At first glance, I thought the more advanced function would win.

I decided to test it for myself

I got the result:

Quote:

Looping Template: 0 seconds to run 10,000,000 iterations...

Recursive #1: 0 seconds to run 10,000,000 iterations...

Recursive #2: 0 seconds to run 10,000,000 iterations...

Recursive #3: 0 seconds to run 10,000,000 iterations...

So I had to increase the iterations:

Quote:

Looping Template: 6 seconds to run 100,000,000 iterations...

Recursive #1: 8 seconds to run 100,000,000 iterations...

Recursive #2: 8 seconds to run 100,000,000 iterations...

Recursive #3: 7 seconds to run 100,000,000 iterations...

*Keep the code simple!* - 10-17-2002SebastianiQuote:

So I had to increase the iterations:

What are you running, anyway - 2 GHZ??

But yeah, I was surprised by the results too, thinking the last recursive would be faster. I think it's wierd that the ratios were so different on our machines, too. Strange... - 10-17-2002Nick
I change the test so that it

works for larger n. This is what

I get

1.5^300 = 6.72013e+052

Looping Template: 46.06 seconds to run 10000000 iterations...

1.5^300 = 6.72013e+052

Recursive #1: 8.111 seconds to run 10000000 iterations...

1.5^300 = 6.72013e+052

Recursive #2: 8.033 seconds to run 10000000 iterations...

1.5^300 = 6.72013e+052

Recursive #3: 11.265 seconds to run 10000000 iterations...

1.5^300 = 6.72013e+052

Iterative #4: 4.414 seconds to run 10000000 iterations...

And the winner is Iterative #4 coming in at 4.414 seconds.