I'm struggling with a math exercise here, and I would gladly appreciate some help.
My problem is that I've encoutered some very big numbers such as $3^{1000}$ and $2^{1000}$ and I want to estimate how many bits are needed to repesent these.
Thank you!
On
A positive integer $n$ has $b$ bits when $2^{b-1}$ ≤ n ≤ $2^b – 1$. so The number of bits required to represent an integer $n$ is : $$\lfloor\log_2 n\rfloor+1$$
On
With a sequence of $0$s and $1$s of length $b$ you can make $2^b$ permutations. Therefore, if you take into account non-negative integers, you can represent numbers up to $2^b - 1$.
It follows that a number $n$ needs $\lfloor \log_2 n \rfloor + 1$ bits to be represented.
In your case: $$\lfloor \log_2 2^{1000} \rfloor + 1 = 1001$$ $$\lfloor \log_2 3^{1000} \rfloor + 1 = \lfloor 1000 \log_2 3 \rfloor + 1 = 1585$$
On
As mentioned by Travis, if all the numbers you wish to represent are of the form $a^b$ then $(a,b)$ format will be shorter for large numbers like in your question. The minimum bits for such a representation will require you to delineate where one of the pair ends and the next begins. For instance, if $3$ is the largest base you will use, then $a$ can be represented in $2$ bits, leaving the number of bits for $b$. Suppose, for your application, that the exponent was always a power of $10$. And suppose it never went above $10^3$. Then you could represent the number as $(a,c)$ with your number being $a^{10^c}$, in which case for this very special representation, the number of bits is $4$. Maybe less than $2$ if you were to employ a very simple arithmetic compression and 3 were as common a number as in your question (it occurs 3 times in this representation).
Why go to all this trouble? Because the number of bits used to represent anything in an actual application may just be dependent on what things get represented, and why and where you are representing them. My final representation might seem absurd, but it wouldn't if it were bits of metadata, or bits in a table in an embedded processor, or bits in a compression scheme, where bits are very valuable. In such cases, the number of bits is dependent on how much information you are conveying by representing them.
The binary representation of a positive integer $n$ has $\lfloor \log_2 n \rfloor + 1$ digits, i.e., requires that many bits to store; so, for example, the number $3^{1000}$ requires
$$\lfloor \log_2 (3^{1000})\rfloor + 1 = \lfloor 1000 \log_2 3 \rfloor + 1 = 1585$$
bits. Of course, if all of the numbers you're working with have the form $a^b$, it's considerably cheaper just to store the pair $(a, b)$; whether this is appropriate obviously depends on what you do with them.