4
$\begingroup$

I asked a question a couple days ago about floating point precision on stackoverflow called, "Is floating point precision mutable or invariant?" and I received the following response.

The formula is mantissa_bits / log_2 10 where the log base two of ten is 3.321928095.

I'm trying to understand why this simple formula works. I tried to derive it, but I'm failing miserably. I searched for ways logarithm can be used to compare number systems with a different base, and the best I could find was this change of base formula.

$$\log_b (x) = \frac {\log_d (x)} {\log_d (b)}$$

But substituting this formula for $\log_2 (10)$ in the former equation above didn't help me much. I think I may be lacking an understanding of what the variable mantissa_bits represents, or my understanding of logarithm in general. As far as I know, mantissa_bits is just a value in base $2$, and

$\log_b (x) = y$

is just

$b^y = x$

Will someone explain and/or derive this formula for me in a way I can understand?

$\endgroup$
2
$\begingroup$

This formula makes more sense when you write it like this.

$\log_{10} (2^{24}) \approx 7.225$

or

${10}^{7.224719896} \approx 2^{24}$

What this is doing is asking how many decimal digits I can multiply together to get $2^{24}$ or $16\text{’}777,216$ possible values of $24$ binary digits.

If you wanted to do this in reverse, it would look like this.

$\log_2 ({10}^{7.224719896}) \approx 24$

or

$2^{24} \approx {10}^{7.224719896}$

This way is asking how many binary digits I can multiply together to get ${10}^{7.224719896}$ or $16\text{’}777,216$ possible values of about $7.225$ decimal digits.

The key variable that remains invariant is the number of possible values our number can have. Also known as permutations. More specifically, a permutation where repetition is allowed. This is represented by the following formula.

$n \times n \times \ldots$ ($r$ times) ${}= n^r$

Therefore, the former formula in the most general case would look like this.

$\log_\text{(base_to_convert_to)} (\text{permutations_of_number}) \approx \text{number_of_digits_of_base_to_convert_to}$

By using this formula, you can convert the number of digits from any base number system to any other base number system while keeping the number of possible permutations constant. Thus, maintaining base precision. However, there may be a loss/gain of significance depending on the magnitude and range of the floating point number.

$\endgroup$
0
$\begingroup$

The formula can be derived the following way:

We are dealing with numbers of the form $$ \hspace{120pt} z = z_1,z_2\dots z_p \cdot 10^m \hspace{100pt} (1)$$ where $z_1,z_p \in \{1,\dots,9\}$ and $z_i \in \{0,\dots,9\}$ for $1<i<p$, so $z$ is in the interval $(10^m, 10^{m+1})$. Moreover, there is an integer $n$ such that $z\in[2^n, 2^{n+1})$.
When we store the number in a computer, it is converted to binary floating-point format, that is, to a number $$ \hspace{120pt} y = y_1,y_2\dots y_q \cdot 2^n \hspace{100pt} (2)$$ close to $z$, where $y_1=1$ and $y_i \in \{0,1\}$ for $i>1$. Since the $n$ in this formula is the specific $n$ from above, we need to consider that this $y$ can also be $1\cdot 2^{n+1}$. Since $y$ is closer to $z$ than any other such number in $[2^n,2^{n+1}]$, we follow that $y$ and $z$ have at most half the distance between these numbers: $$ |y-z| \le \tfrac12 2^{-(q-1)}2^n $$

Now, in order to deduce that the stored number $y$ must have come from the number $z$, this $z$ must lie closer to $y$ than any other number of that form, that is $$ |y-z| < \tfrac12 10^{-(p-1)}10^m $$ We would like to have this as a sufficient condition.

The case $z=10^m$ is special, as $z$ could be rounded down to a $y<z$. That would mean $y\in(10^{m-1},10^m]$, where it would have to satisfy $|y-z| < \tfrac12 10^{-(p-1)}10^{m-1}$. It is therefore appropriate to consider $z$ as an element of $(10^{m-1},10^m]$.

We conclude that $z$ can be stored exactly if $$ \tfrac12 2^{-(q-1)}2^n < \tfrac12 10^{-(p-1)}10^m $$ or, equivalently, $$ p < (q-1-n)\log_{10}2 + (m+1) $$

To see how $n$ and $m$ play into this, imagine the real line divided by powers of $2$ resp. $10$ into segments of either of the forms $(10^m, 2^n]$, $(2^n, 2^{n+1}]$, $(2^n, 10^m]$. For example, the interval $(10^3,10^4]$ consists of five segments: $$ (10^3,2^{10}],\ (2^{10},2^{11}],\ (2^{11},2^{12}],\ (2^{12},2^{13}],\ (2^{13},10^4] $$ In each segment, $m$ and $n$ have a certain value, for example, in the first segment above, $m=3$ and $n=9$, while in the last segment, $m=3$ and $n=13$. When $q$ is a fixed number, the numbers of the form $(2)$ divide an interval $(2^n,2^{n+1}]$ into $2^{q-1}$ steps. The larger $q$ and the smaller $n$, the smaller the steps are, and the better can $z$ be approximated. However, the larger $p$ is, the closer the approximation $y$ lies to a value different from $z$. This is reflected by the condition above being easier to satisfy when $p$ is small, $q$ is large, and $n$ is small. $p$ must be the smallest for numbers in an interval of the form $(2^n,10^{m+1}]$.

Let's fix $q=24$. The condition above can be written as $$ p < 23\log_{10}2 - n\log_{10}2 + (m+1) $$ Since $n$ can only have values such that $\tfrac12 10^m < 2^n < 10^{m+1}$, we see that the middle summand satisfies $$ m - \log_{10}2 < n\log_{10}2 < m+1 $$ Thus, the right-hand side takes values in $$ (23\log_{10}2,\ \ 23\log_{10}2 + \log_{10}2 + 1) $$ Since $\log_{10}2$ is irrational, $n\log_{10}2$ frequently comes arbitrarily close to $m+1$, so these values come close to $23\log_{10}2 \approx 6.92$. That means every now and then, $p$ must be as low as $6$. This is the case, for example, when $m=9$ and $n=33$, where $p$ must be smaller than $6.9897$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.