Number of digits in a number (i.e. log), based solely on the known number of digits in a different base?

Question

I'm in a weird situation, with a cryptography system I'm working on.
I have very large binary integers, non-negative, thousands of bits long.

I cannot compute the actual value of the number (too big), but I DO know exactly how many bits are used.
(i.e. the leftmost non-zero bit)

So if I have an integer $x$ that is, let's say $10000$ bits long, I can safely assume:
$9999\leq\log_2(x)\lt10000$

Using that information alone, I need to determine the maximum possible number of digits required in a different base $b$. (which could be any base, e.g. $10$, $200$, $16$, $64$, $62$, $50$, etc.)

Normally, the simplest formula would be:
$\lceil\log_b(2^n-1)\rceil$ where $n=10000$

As an example with smaller numbers, let's say $n=12$, meaning my huge integer value $x$ is 12 bits long.
That means $11\leq\log_2(x)\lt12$
Using the previous formula $\lceil\log_b(2^n-1)\rceil$ where $n=12$ and $b=10$
results in the value $4$, which is correct, since a 12-bit integer is between $2048$ and $4095$ in base 10.
(4 digits long)

However, obviously this is impractical for end-user devices to compute in real-time, due to the CPU resources required when $n$ gets larger.

Is there a sneaky shortcut method to get (or even approximate) the result, without having to compute the huge value $2^n$?

Answer 1

Clearly $\lceil\log_b2^n\rceil$ is a good upper bound. And $\log_bx=\frac{\log_2x}{\log_2b}$, so

$$\lceil\log_b2^n\rceil=\left\lceil\frac{\log_22^n}{\log_2b}\right\rceil=\left\lceil\frac{n}{\log_2b}\right\rceil$$

gives you a decent bound pretty easily.

Answer 2

So if you have $2^x=b^y$ and take logs to base $2$ you get $x=y\log_2 b$ where. $x$ is constrained and $b$ is known (or you can take logs to your favourite base $c$).

I find, with these $\log$ problems, that going back to the exponential form helps me.