Bugs item #1746088, was opened at 2007-07-01 11:42 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1746088&group_id=5470
Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: Python Library Group: Python 2.5 Status: Open Resolution: None Priority: 5 Private: No Submitted By: David Benbennick (dbenbenn) Assigned to: Nobody/Anonymous (nobody) Summary: long.__str__ is quadratic time Initial Comment: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1746088&group_id=5470 _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
