Number of Bits for Decimal Integer

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $n$ have $m$ digits when expressed in decimal notation.


Then $n$ may require as many as $\ceiling {\dfrac m {\log_{10} 2} }$ bits to represent it.


Proof

Let $d$ be the number of bits that may be needed to represent $n$.

Let $n$ have $m$ digits.

Then:

$n \le 10^m - 1$

and so:

\(\displaystyle d\) \(=\) \(\displaystyle \ceiling {\map {\log_2} {\paren {10^m - 1} + 1} }\) Number of Digits to Represent Integer in Given Number Base
\(\displaystyle \) \(=\) \(\displaystyle \ceiling {\map {\log_2} {10^m} }\)
\(\displaystyle \) \(=\) \(\displaystyle \ceiling {m \log_2 10}\)
\(\displaystyle \) \(=\) \(\displaystyle \ceiling {\dfrac m {\log_{10} 2} }\) Reciprocal of Logarithm

$\blacksquare$


Examples

$14$ Digits

A positive integer $n \in \Z_{>0}$ which has $14$ digits when expressed in decimal notation may require $47$ bits to represent in binary.