This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author dbenbenn
Date 2007-07-01.15:42:45
SpamBayes Score
Marked as misclassified
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, to provide long integers.  That would make other operations, such as * and /, more efficient, too.  But it would require a much bigger change.
Date User Action Args
2007-08-23 14:58:15adminlinkissue1746088 messages
2007-08-23 14:58:15admincreate