[seqfan] Re: Base conversion question

[Robert Gerbicz]

2009/7/21 David Wilson <dwilson at gambitcomm.com>

> I suppose this question is better addressed to math-fun, however, I do
> not think my work self belongs to math-fun.
>
> At any rate, does anyone know anything about the efficiency of base
> conversion between non-homomorphic bases, e.g., 2 and 10?
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

Say you want to convert x represented in base 2 to base 10. The idea: choose
an e integer for that 10^(2*e) is about x, you can do this because from the
base 2 represenatation you can find quickly f for that 2^f<=x<2^(f+1), so a
good choice is e=round(f*log(2)/(2*log(10))). By (FFT) division calculate
x=a*10^e+b. Repeat this process for a and b recursively. By this I think the
conversion costs about O(M(n)*log(n)) time for an n bits number, where
M(n)=is the cost to multiple/divide two at most n bits numbers. As I
remember this is the fastest method, the gmp using this to output a decimal
number.