fast power function

Chris Forone

hello group,

is there some reference implementation of a fast power function? how
fast is the power function in <cmath>?

thanks & hand, chris

Jan 21 '08 #1

=?iso-8859-1?q?Tom=E1s_=D3_h=C9ilidhe?=

Chris Forone:

hello group,

is there some reference implementation of a fast power function? how
fast is the power function in <cmath>?

thanks & hand, chris

Very probably the fastest method of calculating powers for that platform.
--
Tomás Ó hÉilidhe

Jan 21 '08 #2

Juha Nieminen

Tomás Ó hÉilidhe wrote:

Very probably the fastest method of calculating powers for that platform.

Not necessarily in all cases.

For example in intel architectures pow() is rather slow because
there's no such FPU opcode in 387. We are probably talking about many
hundreds, if not even over a thousand clock cycles even on a Pentium.
While compilers may try to optimize the pow() call away if they can,
they often can't.

In some cases it may be faster to "open up" a calculation than
calling pow(). For example, in many cases it may be slower to perform a
"pow(x, 1.5)" than a "x*sqrt(x)" (many compilers are unable to optimize
the former into the latter).

But of course this is more related to architectures and compilers than
to C++, and thus slightly off-topic.

Jan 21 '08 #3

=?iso-8859-1?q?Tom=E1s_=D3_h=C9ilidhe?=

Would it not make sense for the standard library to have a pow function
that deals only with integer exponents?

unsigned pow_int(unsigned const x,unsigned exp)
{
unsigned retval = 1;

while ( ; exp; --exp) retval *= x;

return retval;
}

--
Tomás Ó hÉilidhe

Jan 21 '08 #4

Pete Becker

On 2008-01-21 11:25:39 -0500, "Tomás Ó hÉilidhe" <to*@lavabit.comsaid:

>
Would it not make sense for the standard library to have a pow function
that deals only with integer exponents?

It has three: pow(float, int), pow(double, int), and pow(long double, int).

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jan 21 '08 #5

Juha Nieminen

Tomás Ó hÉilidhe wrote:

Would it not make sense for the standard library to have a pow function
that deals only with integer exponents?

Compilers do have specialized pow() functions when the exponent is
integer.

unsigned pow_int(unsigned const x,unsigned exp)
{
unsigned retval = 1;

while ( ; exp; --exp) retval *= x;

return retval;
}

That's *not* the fastest way of calculating pow(x, integer).

Jan 21 '08 #6

Jerry Coffin

In article <47***********************@news.tdc.fi>,
no****@thanks.invalid says...

[ ... ]

For example in intel architectures pow() is rather slow because
there's no such FPU opcode in 387. We are probably talking about many
hundreds, if not even over a thousand clock cycles even on a Pentium.
While compilers may try to optimize the pow() call away if they can,
they often can't.

I don't know of any processor that would let you implement pow in a
single instruction -- but Intel floating point includes instructions for
logarithm and inverse logarithm, which make pow pretty easy to
implement.

As far as speed goes, you should be looking at about 150-190 CPU cycles
on a reasonably modern CPU (depending somewhat on data). I haven't found
any data for which it takes 200 cycles on my machine, and it's a few
years old -- I believe current CPUs are typically at least 20-30% faster
at the same clock speed.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jan 22 '08 #7

Jerry Coffin

In article <fn**********@newsreader1.xoc.utanet.at>, 4o**@gmx.at says...

hello group,

is there some reference implementation of a fast power function? how
fast is the power function in <cmath>?

The implementation in the library is likely to be oriented more toward
being general purpose than the fastest for a given situation. You can
probably do substantially better if (and only if) you know a fair amount
about the data you're working with, so you can write something more
specialized.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jan 22 '08 #8

James Kanze

On Jan 21, 11:09 pm, Juha Nieminen <nos...@thanks.invalidwrote:

Tomás Ó hÉilidhe wrote:

Would it not make sense for the standard library to have a pow function
that deals only with integer exponents?

Compilers do have specialized pow() functions when the exponent is
integer.

unsigned pow_int(unsigned const x,unsigned exp)
{
unsigned retval = 1;

while ( ; exp; --exp) retval *= x;
return retval;
}

That's *not* the fastest way of calculating pow(x, integer).

Nor the most accurate.

--
James Kanze (GABI Software) mailto:ja*********@gmail.com
Conseils en informatique orient�e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S�mard, 78210 St.-Cyr-l'�cole, France, +33 (0)1 30 23 00 34

Jan 22 '08 #9

Lionel B

On Tue, 22 Jan 2008 05:50:47 -0800, James Kanze wrote:

On Jan 21, 11:09 pm, Juha Nieminen <nos...@thanks.invalidwrote:

>Tomás Ó hÉilidhe wrote:

Would it not make sense for the standard library to have a pow
function
that deals only with integer exponents?

> Compilers do have specialized pow() functions when the exponent is
integer.

unsigned pow_int(unsigned const x,unsigned exp) {
unsigned retval = 1;

while ( ; exp; --exp) retval *= x;
return retval;
}

> That's *not* the fastest way of calculating pow(x, integer).

It may or may not be...

Nor the most accurate.

Surely it's guaranteed 100% accurate* - it's integer arithmetic.

*provided retval doesn't overflow.

--
Lionel B

Jan 22 '08 #10

Chris Forone

Thaks a lot!

yours sincerely, chris

Jan 23 '08 #11

James Kanze

On Jan 22, 3:49 pm, Lionel B <m...@privacy.netwrote:

On Tue, 22 Jan 2008 05:50:47 -0800, James Kanze wrote:

On Jan 21, 11:09 pm, Juha Nieminen <nos...@thanks.invalidwrote:

Tomás Ó hÉilidhe wrote:
Would it not make sense for the standard library to have a pow
function
that deals only with integer exponents?

Compilers do have specialized pow() functions when the exponent is
integer.

unsigned pow_int(unsigned const x,unsigned exp) {
unsigned retval = 1;

while ( ; exp; --exp) retval *= x;
return retval;
}

That's *not* the fastest way of calculating pow(x, integer).

It may or may not be...

It's not, by far.

Nor the most accurate.

Surely it's guaranteed 100% accurate* - it's integer arithmetic.

Oops. I missed that; I read the line "Compilers do have
specialized pow() functions when the exponent is integer", and
didn't look at the actual function parameters.

Using this function if the base is a floating point type, of
course, will result in very poor accuracy.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jan 23 '08 #12