1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – quicksort Nov 4 '17 at 21:44
  • $\begingroup$ @quicksort Yes, I know $n$, $b1$, $b2$ and the the boundaries of the slice. $\endgroup$ – Ciprum Nov 4 '17 at 22:09
1
$\begingroup$

Partial answer:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.