[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?
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.
More information about the SeqFan
mailing list