Robert Bradshaw wrote:
> http://trac.cython.org/cython_trac/ticket/127 I only special-cased
> 0-3, the rest is generic (repeated squaring) code.
Here's some code I wrote a while back that uses binary decomposition to
improve performance. I don't know how much it really matters...
Jason
// Use binary decomposition to reduce the number of multiplication
operations
// when calculating x^n. See "Hackers Delight", pp 212-213 for further
// information.
LkmpInline int64_t
LkpIntExp(int64_t x, int64_t n) {
int64_t ret, p;
bool neg = (n < 0);
// The main loop only works for non-negative exponents, so transform
// negative exponents outside the loop, and clean up at the end with a
// division.
if (neg) {
// This can overflow if n is -2^63, but the results are explicitly
// undefined on underflow/overflow, so there is no need to check.
n = -n;
}
for (ret = 1, p = x;
n != 0;
n >>= 1, p *= p) {
if (n & 1) {
ret *= p;
}
}
if (neg) {
ret = 1 / ret;
}
return ret;
_______________________________________________
Cython-dev mailing list
[email protected]
http://codespeak.net/mailman/listinfo/cython-dev
