5
$\begingroup$

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

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

  • 2
    That would be bits. Also you need a ceiling function in the end.2012-06-19
  • 0
    yeah, I meant bits, sorry2012-06-19
  • 0
    `00110101 00110101 01011110 00110010 00110000 00110000 00110010` are only 56 bits :)2014-01-27
  • 0
    @HagenvonEitzen: It says number, not string. And fact you can store ASCII at 7 bits per character.;-)2014-01-27
  • 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

8

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.