Fastest way to convert between two bases in arbitary precision floating point arithmetic for over a billion digits -

which fastest way convert between base 2 ^ 64 other base? "any other base", mean any base less 2 ^ 64 itself. think it's using divide-and-conquer based methods bernstein scaled remainder trees?
more details: want convert on 1 billion digits of famous constants in different bases future version of isitnormal. there 2 approaches can use:
1. calculate billion digits of constant in every base wish.
2. digits somewhere (e.g. y-cruncher) , convert every base wish.
plan use approach #2 seems faster.

as far know can done in o(n*log(n)) operation using fft big-integer multiplication , fast sqrt algorithm. basic idea follow.

step 1. large integer x of k digits in base b1, found 2 integers y & z, such y & z both have no more k/2 digits, , x=y*y+z. (notice z can negative). can done doing sqrt(x) operation, let y nearest integer of sqrt(x) , z remainder.

step 2. convert y & z base b1 base b2, recursively using step 1.

step 3. compute x in base b2 using formula x=y*y+z again;

then remaining part how sqrt(x) in o(n*log(n)) time, here's method:

let x0 = estimation of sqrt(x); keep doing x0 = (x/x0 + x0)/2 until converge;

and here problem arises: how compute 1/x in o(n*log(n)) time ? method is:

let x0 = estimation of 1/x; keep doing x0 = (2-x*x0)*x0 until converge;

using fft compute big number multiplication in o(nlog(n)) whole algorithm can optimized o(nlog(n)).