On 10/16/07, Mark Dickinson <[EMAIL PROTECTED]> 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 _______________________________________________ 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
