# [seqfan] Re: Base conversion question

franktaw at netscape.net franktaw at netscape.net
Tue Jul 21 22:28:39 CEST 2009

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

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

```