[issue21420] Optimize 2 ** n: implement it as 1 << n

[STINNER Victor]

New submission from STINNER Victor:

The algorithm for 2 ** n (long_pow) is slower than 1 << n algorithm (long_lshift). I propose to compute x**y as 1<<y if x==2 and y >= 0.

Attached patch implements this idea. According to my microbenchmark, it is 4x faster to small power (2**0 .. 2**1024) and up to 340x faster for large power (2**(2**28)).

----------
files: pow2.patch
keywords: patch
messages: 217800
nosy: haypo
priority: normal
severity: normal
status: open
title: Optimize 2 ** n: implement it as 1 << n
type: performance
versions: Python 3.5
Added file: http://bugs.python.org/file35138/pow2.patch

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