gmp-discuss Digest, Vol 59, Issue 11

[Paul Zimmermann]

       David,

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

Paul