# How to convert between bases partially?

I have some large number $n$ in base $b_1$ and I want to convert it to base $b_2$. $n$ is about a million decimal digits long, therefore it's impractical to convert it as a whole. However I don't need the entire $n$, just some arbitrary slice of it when it's converted to $b_2$

For example converting from base 10 to base 3, with a slice from digits 5-10:

n(10) = 2347892347
n(3) = 2000[11212]22021210211
m(3) = 11212 <-- the number I need


note: it doesn't matter if the slice starts from the left or the right of the number

Is there a fast method to get that slice $m$? Any help is very much appreciated.

• I don't understand what you're looking for exactly. Can you assume to know in advance the boundary of the section, e.g. digits from the $n$-th to the $m$-th? – quicksort Nov 4 '17 at 21:44
• @quicksort Yes, I know $n$, $b1$, $b2$ and the the boundaries of the slice. – Ciprum Nov 4 '17 at 22:09

It works for some pairs $b_1$ $b_2$, but may not work for every pair.

Partial solution:

for pairs $b_1$ $b_2$ where there is an $x, p_1, p_2 \in \mathbb{Z}$ such that

\begin{alignat*}{4} x^{p_1} & {}={} & b_1\\ x^{p_2} & {}={} & b_2 \end{alignat*}

you can divide $n$ of $b_1$ into sections of $p_2$ digit sections, which you can then convert into $b_2$.

If you want to query a slice in the result $b_2$, you need to calculate the section number by dividing by $p_1$

3 -> 10 doesn't work with this, but I will give you an example

8 -> 16:

$x = 2, p_1 = 3, p_2 = 4$

8  [....][1][2][3][4][..p2 * x blocks..]
2        001010011100
16 [....][ 2][ 9][ C][..p1 * x blocks..]


3 -> 9:

$x = 3, p_1 = 1, p_2 = 2$

3  [....][1][0][2][1][..p2 * x blocks..]
3          1  0  2  1
9  [....][   3][   7][..p1 * x blocks..]

• What are $m_1$ and $m_2$ supposed to be? – Ciprum Nov 5 '17 at 21:05
• Ignore - fixed. I thought maybe $x^{p_i}=b_i m_i$ would work, but it doesn't. I forgot to take it out. – guest Nov 5 '17 at 21:23