6
$\begingroup$

How many bits needed to store a number $55^{2002}$ ?

My answer is $2002\;\log_2(55)$; is it correct?

  • 0
    @MarcvanLeeuwen In order to be able to express more, I used UTF-8 ;) - But the answer to the original question should nevertheless depend on the *encoding* to be precise. For example IEEE floats are very well suited to store numbers that are powers of two, or (relatively) small numbers times a power of two. So who stops us from introducing an encoding that is good (and exact) for powers of $55$?2014-01-28

1 Answers 1

9

The number of bits required to represent an integer $n$ is $\lfloor\log_2 n\rfloor+1$, so $55^{2002}$ will require $\lfloor 2002\; \log_2 55\rfloor+1$ bits, which is $11,575$ bits.

Added: For example, the $4$-bit integers are $8$ through $15$, whose logs base $2$ are all in the interval $[3,4)$. We have $\lfloor\log_2 n\rfloor=k$ if and only if $k\le\log_2 n if and only if $2^k\le n<2^{k+1}$, and that’s exactly the range of integers requiring $k+1$ bits.