On 10/16/07, Daniel Stutzbach <[EMAIL PROTECTED]> wrote: > On 10/16/07, Mark Dickinson <[EMAIL PROTECTED]> 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 _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
