On 10/16/07, Daniel Stutzbach <daniel.stutzbach at gmail.com> wrote: > On 10/16/07, Mark Dickinson <dickinsm at 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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4