Heavily fiddled variant of patch #1442927: PyLong_FromString optimization.

``long(str, base)`` is now up to 6x faster for non-power-of-2 bases.  The
largest speedup is for inputs with about 1000 decimal digits.  Conversion
from non-power-of-2 bases remains quadratic-time in the number of input
digits (it was and remains linear-time for bases 2, 4, 8, 16 and 32).

Speedups at various lengths for decimal inputs, comparing 2.4.3 with
current trunk.  Note that it's actually a bit slower for 1-digit strings:

  len  speedup
 ----  -------
   1     -4.5%
   2      4.6%
   3      8.3%
   4     12.7%
   5     16.9%
   6     28.6%
   7     35.5%
   8     44.3%
   9     46.6%
  10     55.3%
  11     65.7%
  12     77.7%
  13     73.4%
  14     75.3%
  15     85.2%
  16    103.0%
  17     95.1%
  18    112.8%
  19    117.9%
  20    128.3%
  30    174.5%
  40    209.3%
  50    236.3%
  60    254.3%
  70    262.9%
  80    295.8%
  90    297.3%
 100    324.5%
 200    374.6%
 300    403.1%
 400    391.1%
 500    388.7%
 600    440.6%
 700    468.7%
 800    498.0%
 900    507.2%
1000    501.2%
2000    450.2%
3000    463.2%
4000    452.5%
5000    440.6%
6000    439.6%
7000    424.8%
8000    418.1%
9000    417.7%

1 files changed, 75 insertions, 0 deletions

diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py
index 48d50d8..ed28153 100644
--- a/Lib/test/test_builtin.py
+++ b/Lib/test/test_builtin.py
@@ -980,6 +980,81 @@ class BuiltinTest(unittest.TestCase):
         self.assertRaises(ValueError, long, '53', 40)
         self.assertRaises(TypeError, long, 1, 12)
 
+        self.assertEqual(long('100000000000000000000000000000000', 2),
+                         4294967296)
+        self.assertEqual(long('102002022201221111211', 3), 4294967296)
+        self.assertEqual(long('10000000000000000', 4), 4294967296)
+        self.assertEqual(long('32244002423141', 5), 4294967296)
+        self.assertEqual(long('1550104015504', 6), 4294967296)
+        self.assertEqual(long('211301422354', 7), 4294967296)
+        self.assertEqual(long('40000000000', 8), 4294967296)
+        self.assertEqual(long('12068657454', 9), 4294967296)
+        self.assertEqual(long('4294967296', 10), 4294967296)
+        self.assertEqual(long('1904440554', 11), 4294967296)
+        self.assertEqual(long('9ba461594', 12), 4294967296)
+        self.assertEqual(long('535a79889', 13), 4294967296)
+        self.assertEqual(long('2ca5b7464', 14), 4294967296)
+        self.assertEqual(long('1a20dcd81', 15), 4294967296)
+        self.assertEqual(long('100000000', 16), 4294967296)
+        self.assertEqual(long('a7ffda91', 17), 4294967296)
+        self.assertEqual(long('704he7g4', 18), 4294967296)
+        self.assertEqual(long('4f5aff66', 19), 4294967296)
+        self.assertEqual(long('3723ai4g', 20), 4294967296)
+        self.assertEqual(long('281d55i4', 21), 4294967296)
+        self.assertEqual(long('1fj8b184', 22), 4294967296)
+        self.assertEqual(long('1606k7ic', 23), 4294967296)
+        self.assertEqual(long('mb994ag', 24), 4294967296)
+        self.assertEqual(long('hek2mgl', 25), 4294967296)
+        self.assertEqual(long('dnchbnm', 26), 4294967296)
+        self.assertEqual(long('b28jpdm', 27), 4294967296)
+        self.assertEqual(long('8pfgih4', 28), 4294967296)
+        self.assertEqual(long('76beigg', 29), 4294967296)
+        self.assertEqual(long('5qmcpqg', 30), 4294967296)
+        self.assertEqual(long('4q0jto4', 31), 4294967296)
+        self.assertEqual(long('4000000', 32), 4294967296)
+        self.assertEqual(long('3aokq94', 33), 4294967296)
+        self.assertEqual(long('2qhxjli', 34), 4294967296)
+        self.assertEqual(long('2br45qb', 35), 4294967296)
+        self.assertEqual(long('1z141z4', 36), 4294967296)
+
+        self.assertEqual(long('100000000000000000000000000000001', 2),
+                         4294967297)
+        self.assertEqual(long('102002022201221111212', 3), 4294967297)
+        self.assertEqual(long('10000000000000001', 4), 4294967297)
+        self.assertEqual(long('32244002423142', 5), 4294967297)
+        self.assertEqual(long('1550104015505', 6), 4294967297)
+        self.assertEqual(long('211301422355', 7), 4294967297)
+        self.assertEqual(long('40000000001', 8), 4294967297)
+        self.assertEqual(long('12068657455', 9), 4294967297)
+        self.assertEqual(long('4294967297', 10), 4294967297)
+        self.assertEqual(long('1904440555', 11), 4294967297)
+        self.assertEqual(long('9ba461595', 12), 4294967297)
+        self.assertEqual(long('535a7988a', 13), 4294967297)
+        self.assertEqual(long('2ca5b7465', 14), 4294967297)
+        self.assertEqual(long('1a20dcd82', 15), 4294967297)
+        self.assertEqual(long('100000001', 16), 4294967297)
+        self.assertEqual(long('a7ffda92', 17), 4294967297)
+        self.assertEqual(long('704he7g5', 18), 4294967297)
+        self.assertEqual(long('4f5aff67', 19), 4294967297)
+        self.assertEqual(long('3723ai4h', 20), 4294967297)
+        self.assertEqual(long('281d55i5', 21), 4294967297)
+        self.assertEqual(long('1fj8b185', 22), 4294967297)
+        self.assertEqual(long('1606k7id', 23), 4294967297)
+        self.assertEqual(long('mb994ah', 24), 4294967297)
+        self.assertEqual(long('hek2mgm', 25), 4294967297)
+        self.assertEqual(long('dnchbnn', 26), 4294967297)
+        self.assertEqual(long('b28jpdn', 27), 4294967297)
+        self.assertEqual(long('8pfgih5', 28), 4294967297)
+        self.assertEqual(long('76beigh', 29), 4294967297)
+        self.assertEqual(long('5qmcpqh', 30), 4294967297)
+        self.assertEqual(long('4q0jto5', 31), 4294967297)
+        self.assertEqual(long('4000001', 32), 4294967297)
+        self.assertEqual(long('3aokq95', 33), 4294967297)
+        self.assertEqual(long('2qhxjlj', 34), 4294967297)
+        self.assertEqual(long('2br45qc', 35), 4294967297)
+        self.assertEqual(long('1z141z5', 36), 4294967297)
+
+
     def test_longconversion(self):
         # Test __long__()
         class Foo0: