"pow" (power) function

[Russ]

I have a couple of questions for the number crunchers out there:

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

Thanks,
Russ

[Paul Rubin]

"Russ" <uy*******@snea kemail.com> writes:

I just did a little time test (which I should have done *before* my
original post!), and 2.0**2 seems to be about twice as fast as
pow(2.0,2). That seems consistent with your claim above...>
I just did another little time test comparing 2.0**0.5 with sqrt(2.0).
Surprisingly, 2.0**0.5 seems to take around a third less time.

I think the explanation is likely here:

Python 2.3.4 (#1, Feb 2 2005, 12:11:53)

import dis
from math import sqrt
def f(x): return x**.5 ... dis.dis(f) 1 0 LOAD_FAST 0 (x)
3 LOAD_CONST 1 (0.5)
6 BINARY_POWER
7 RETURN_VALUE
8 LOAD_CONST 0 (None)
11 RETURN_VALUE

See, x**.5 does two immediate loads and an inline BINARY_POWER bytecode.
def g(x): return sqrt(x) ... dis.dis(g) 1 0 LOAD_GLOBAL 0 (sqrt)
3 LOAD_FAST 0 (x)
6 CALL_FUNCTION 1
9 RETURN_VALUE
10 LOAD_CONST 0 (None)
13 RETURN_VALUE

sqrt(x), on the other hand, does a lookup of 'sqrt' in the global
namespace, then does a Python function call, both of which likely
are almost as expensive as the C library pow(...) call.

If you do something like

def h(x, sqrt=sqrt):
return sqrt(x)

you replace the LOAD_GLOBAL with a LOAD_FAST and that might give a
slight speedup:
dis.dis(h)

2 0 LOAD_FAST 1 (sqrt)
3 LOAD_FAST 0 (x)
6 CALL_FUNCTION 1
9 RETURN_VALUE
10 LOAD_CONST 0 (None)
13 RETURN_VALUE

[David M. Cooke]

"Russ" <uy*******@snea kemail.com> writes:

Ben Cartwright wrote:

Russ wrote:

> Does "pow(x,2)" simply square x, or does it first compute logarithms
> (as would be necessary if the exponent were not an integer)?

The former, using binary exponentiation (quite fast), assuming x is an
int or long.

If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow()
function is called. This function calls libm's pow(), which in turn
uses logarithms.

I just did a little time test (which I should have done *before* my
original post!), and 2.0**2 seems to be about twice as fast as
pow(2.0,2). That seems consistent with your claim above.

I'm a bit surprised that pow() would use logarithms even if the
exponent is an integer. I suppose that just checking for an integer
exponent could blow away the gain that would be achieved by avoiding
logarithms. On the other hand, I would think that using logarithms
could introduce a tiny error (e.g., pow(2.0,2) = 3.9999999996 <- made
up result) that wouldn't occur with multiplication.

It depends on the libm implementation of pow() whether logarithms are
used for integer exponents. I'm looking at glibc's (the libc used on
Linux) implementation for Intel processors, and it does optimize
integers. That routine is written in assembly language, btw.

> Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
> other (perhaps less efficient) algorithm based on logarithms?

The latter, and that algorithm is libm's pow(). Except for a few
special cases that Python handles, all floating point exponentation is
left to libm. Checking to see if the exponent is 0.5 is not one of
those special cases.

I just did another little time test comparing 2.0**0.5 with sqrt(2.0).
Surprisingly, 2.0**0.5 seems to take around a third less time.

None of these differences are really significant unless one is doing
super-heavy-duty number crunching, of course, but I was just curious.
Thanks for the information.

And if you are, you'd likely be doing it on more than one number, in
which case you'd probably want to use numpy. We've optimized x**n so
that it does handle n=0.5 and integers specially; it makes more sense
to do this for an array of numbers where you can do the special
manipulation of the exponent, and then apply that to all the numbers
in the array at once.

--
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)phy sics(dot)mcmast er(dot)ca