On 2013-12-06 19:01, Neil Cerutti wrote:
On 2013-12-06, John Ladasky <john_lada...@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) */
It's worth noting that the *interpreter* per se is not doing this. The
implementation of the `long` object does this in its implementation of the
`__pow__` method, which the interpreter invokes. Other objects may implement
this differently and use whatever optimizations they like. They may even (ab)use
the syntax for things other than numerical exponentiation where `x**2` is not
equivalent to `x*x`. Since objects are free to do so, the interpreter itself
cannot choose to optimize that exponentiation down to multiplication.
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
--
https://mail.python.org/mailman/listinfo/python-list
