[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 

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: 
an e integer for that 10^(2*e) is about x, you can do this because from 
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 
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 

More information about the SeqFan mailing list