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