In the 2.5.1 source code, Objects/longobject.c:long_format() is used to convert a long int to a string.  When base is not a power of 2, it is quadratic time in the length of the output string.  Of course, this is fine on small numbers, but is catastrophic on huge numbers.

Suppose base is 10.  The problem is that the algorithm basically does the following: take the number mod 10 to get a digit, stick that digit on the output, divide the number by 10, and repeat.

To print an n digit number, there is an O(n log n) algorithm, using divide-and-conquer.  You break the number into 2 pieces, each n/2 digits long, and iterate on both pieces.

Converting string to long has the same quadratic time problem, in PyLong_FromString().  The solution is the same, in reverse: break the string in half, convert each piece to a long, and combine the two longs into one.


Alternatively, Python could just use GMP (GNU MP Bignum Library, http://gmplib.org/) to provide long integers.  That would make other operations, such as * and /, more efficient, too.  But it would require a much bigger change.