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%
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 @@
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: