gmp-discuss Digest, Vol 59, Issue 11
Paul.Zimmermann at loria.fr
Tue Jul 29 13:43:10 CEST 2008
> From: David Harvey <dmharvey at math.harvard.edu>
> Date: Tue, 29 Jul 2008 07:22:55 -0400
> > from a theoretical point of view, as far as I know, the complexity
> > of computing
> > a single digit (say the middle one) in a base that is not
> > commensurable to the
> > internal base (for example in base 10 when numbers are represented
> > in radix 2)
> > is the same as converting the whole number, i.e., O(n log n).
> How do you do a full base conversion in O(n log n)? I only know how
> to get O(n log(n)^2), i.e. divide-and-conquer, with O(log(n)) layers,
> each layer costs O(n log(n)).
sorry, I meant O(M(n) log n).
> But to get the k-th base-b digit, assuming b is fixed, you need to
> compute b^k, which costs O(k log(k)) = O(n log(n)) by repeated
> squaring, and then a single division costing O(n log n), and a single-
> precision division to get the last digit. So I agree you can get a
> single digit in O(n log n).
you're right, this gives indeed O(M(n)), thus I was wrong above, since
I meant O(M(n) log n).
> (Of course, because of GMP's non-optimal division in 4.2.1, there's
> an extra factor of log(n) in all of that.)
that extra log(n) factor should disappear in GMP 5.
More information about the gmp-discuss