[Python-Dev] C Decimal - is there any interest?

[Mark Dickinson]

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