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

[Daniel Stutzbach]

On 10/16/07, Mark Dickinson <dickinsm at gmail.com> wrote:
> > 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?

Possibly, but who's counting?  :-)

> 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.

I agree.  A basic subquadratic radix conversion algorithm isn't much
more complex than the existing quadratic code.  I just whipped
together a Python prototype and it's only 15 lines.

The quadratic algorithm is basically a divide-and-conquer algorithm,
too, except it's the bad kind that  breaks the input into pieces of
size O(1) and size O(n) instead of pieces of size O(n/2). :-)
(where n is number of digits)

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC