[issue21419] Use calloc() instead of malloc() for int << int (lshift)

[Josh Rosenberg]

Josh Rosenberg added the comment:

While you're doing this, might it make sense to add a special case to long_pow so it identifies cases where a (digit-sized) value with an absolute value equal to a power of 2 is being raised to a positive integer exponent, and convert said cases to equivalent left shifts? 

Identifying powers of 2 can be done in constant time with no memory overhead for register sized values (see http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 ); if you've already handled the case for 0, then checking if it's a power of 2 is just:

    (v & (v - 1)) == 0

It adds a little complexity, but even just handling 2 alone specially would at least make it so the semi-common case of making a large power of 2 doesn't have significantly different performance using 2 ** (numbits - 1) instead of 1 << (numbits - 1).

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21419>
_______________________________________