Does Python optimize low-power functions?
Neil Cerutti
neilc at norwich.edu
Fri Dec 6 14:01:26 EST 2013
On 2013-12-06, John Ladasky <john_ladasky at sbcglobal.net> wrote:
> The following two functions return the same result:
>
> x**2
> x*x
>
> But they may be computed in different ways. The first choice
> can accommodate non-integer powers and so it would logically
> proceed by taking a logarithm, multiplying by the power (in
> this case, 2), and then taking the anti-logarithm. But for a
> trivial value for the power like 2, this is clearly a wasteful
> choice. Just multiply x by itself, and skip the expensive log
> and anti-log steps.
>
> My question is, what do Python interpreters do with power
> operators where the power is a small constant, like 2? Do they
> know to take the shortcut?
It uses a couple of fast algorithms for computing powers. Here's
the excerpt with the comments identifying the algorithms used.
>From longobject.c:
2873 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
2874 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
2875 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
...
2886 else {
2887 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
The only outright optimization of the style I think your
describing that I can see is it quickly returns zero when modulus
is one.
I'm not a skilled or experienced CPython source reader, though.
--
Neil Cerutti
More information about the Python-list
mailing list