On 10/16/07, Daniel Stutzbach <daniel.stutzbach@gmail.com> wrote:
On 10/16/07, Mark Dickinson <dickinsm@gmail.com> wrote:
the reverse conversion to get a Decimal result; both of these conversions (tuple of digits <-> integer) take time quadratic in the size of the tuple/integer.
Instead of (or in addition to) porting to C, wouldn't it be better to improve the conversion algorithm?
I certainly wouldn't mind seeing subquadratic integer -> string and string -> integer conversions in core Python. But I guess somebody's got to write them, and then persuade the powers-that-be that the extra code and complexity are worth it... I'm not volunteering right now :). Though I do have Python string <-> integer code that's faster than the builtins from around 8000 decimal digits onwards, if anyone wants to use it as a starting point... The desire for fast integer -> string has also come up on the bug tracker recently: see http://bugs.python.org/issue1746088
Radix conversion can be done in O(n log**2 n) time using a divide and conquer algorithm.
Isn't there a log(log n) missing here? In any case, it seems to me that achieving this sort of complexity is probably best left to GMP and the like. But a basic subquadratic division based on Burnikel and Ziegler's 'Fast Recursive Division' paper seems within reach---this would give division and radix conversion essentially the same complexity as Karatsuba multiplication. Mark