19
$\begingroup$

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

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

$\endgroup$
5
  • 2
    $\begingroup$ That would be bits. Also you need a ceiling function in the end. $\endgroup$ Commented Jun 19, 2012 at 11:57
  • $\begingroup$ yeah, I meant bits, sorry $\endgroup$
    – TOP KEK
    Commented Jun 19, 2012 at 11:58
  • $\begingroup$ 00110101 00110101 01011110 00110010 00110000 00110000 00110010 are only 56 bits :) $\endgroup$ Commented Jan 27, 2014 at 16:48
  • $\begingroup$ @HagenvonEitzen: It says number, not string. And fact you can store ASCII at 7 bits per character.;-) $\endgroup$ Commented Jan 27, 2014 at 17:52
  • $\begingroup$ @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$? $\endgroup$ Commented Jan 28, 2014 at 19:31

1 Answer 1

30
$\begingroup$

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<k+1$ if and only if $2^k\le n<2^{k+1}$, and that’s exactly the range of integers requiring $k+1$ bits.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .