给定常数 $b$ 和 $B$，要把一个 $b$ 进制 $n$ 位的高精度数转成 $B$ 进制。

普通方法每一位需要做一次 $O(n)$ 的高精度乘法，所以时间复杂度是 $O(n^2)$。

有 $O(n\log^2 n)$ 的算法：每轮循环对所有 $k$ 将 $2k-1$ 位与 $2k$ 位合并放到第 $k$ 位上，这样一共进行 $O(\log n)$ 轮。第 $i$ 轮要计算 $O(\frac{n}{2^i})$ 个 $O(2^i)$ 位数乘以同样是 $O(2^i)$ 位的 $b^{2^i}$，所以时间是 $O(\frac{n}{2^i})\cdot O(2^ii)=O(ni)$。于是总复杂度 $O(n\log^2 n)$。

有没有复杂度更低或常数更小的算法？