[seqfan] Re: Base conversion question

[franktaw at netscape.net]

What happens if you use the Fast Fourier Transform simply on the number 
to be converted, and then convert back using the new radix for your 
arithmetic?

Franklin T. Adams-Watters


-----Original Message-----
From: Robert Gerbicz <robert.gerbicz at gmail.com>

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?

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.