«

hello group,

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

thanks & hand, chris

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

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.

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

On 2008-01-21 11:25:39 -0500, "Tomás Ó hÉilidhe" <> said:

>
> 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)

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).

In article <4794bdad$0$23838$>,
lid 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.

In article <fn1ra4$4qp$>, 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.

Jerry Coffin wrote:
> 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.

Actually it's not "pretty easy", as there's a twist.

pow(x, y) = pow(2, y*log2(x)), and the 387 happens to have both an
opcode for calculating y*log2(x), fyl2x, and one for calculating
pow(2, x)-1, f2xm1. The twist is, however, that with the latter x must
be inside the range from -1.0 to +1.0. This means that the x in the
original pow(x, y) cannot be used as it is with f2xm1, but it must be
split using the property 2^(a+b) = 2^a*2^b.

The complete asm code for calculating pow(x, y), assuming x and y have
already been loaded into the FPU, is something like (with reported clock
cycles for the pentium):

fyl2x ; 22-111
fld st ; 1
frndint ; 9-20
fsub st(1), st ; 3
fxch st(2) ; 0-1
f2xm1 ; 13-57
fld1 ; 2
fadd ; 3
fscale ; 20-31
fstp st(1) ; 1

I suppose the absolute best case scenario is a total of 74 clock
cycles, and the worst is 230 clock cycles, with possible stalls.

I suppose I overestimated the required clock cycles.

On Jan 21, 11:09 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
> 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) private.php?do=newpm&u=
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