Which is the currently the fastest way to convert between base 2 ^ 64 to any other base? By "any other base", I mean any base less than 2 ^ 64 itself. I think it's using Divide-and-Conquer based methods with Bernstein scaled remainder trees?
Some more details: I specifically want to convert over 1 billion digits of some famous constants in different bases for a future version of IsItNormal.
There are two approaches I can use:
1. Calculate billion digits of that constant in every base I wish.
2. Get digits from somewhere (e.g. y-cruncher) and then convert to every base I wish.
I plan to use approach #2 as it seems faster.
As far as I know it can be done in O(N*log(N)) operation using FFT for big-integer multiplication and fast sqrt algorithm. The basic idea is as follow.
step 1. For large integer X of k digits in base b1, found two integers Y & Z, such that Y & Z both have no more than k/2 digits, and X=Y*Y+Z. (Notice that Z can be negative). This can be done simply by doing a sqrt(X) operation, then let Y to be nearest integer of sqrt(X) and Z be the remainder.
step 2. Convert Y & Z from base b1 into base b2, recursively using step 1.
step 3. compute X in base b2 using formula X=Y*Y+Z again;
Then the remaining part is how to sqrt(X) in O(N*log(N)) time, here's the method:
let x0 = estimation of sqrt(X); keep doing x0 = (X/x0 + x0)/2 until it converge;
And here another problem arises: how to compute 1/X in O(N*log(N)) time ? The method is:
let x0 = estimation of 1/X; keep doing x0 = (2-X*x0)*x0 until it converge;
using FFT to compute big number multiplication in O(Nlog(N)) then the whole algorithm can be optimized to O(Nlog(N)).