computer sciencefloating pointterminology
Using the scientific notation:
$$3.14 = 0.314 \times 10^1$$
From Tanenbaum's Structured Computer Organization, section B.1:
The range is effectively determined by the number of digits in the exponent and the precision is determined by the number of digits in the fraction.
I know how this notation works but I am asking about the meaning of the two words.
Why the book is calling them the range and precision? What do they exactly mean?
I think you are justifiably confused. This is a poorly worded question and an obscure answer.
Let's start with the question. The main problem is the vagueness of this phrase:
every row and every column of the resulting table has an even number of ones and zeros in it.
What does "even number of ones and zeros" mean? It can mean any of these things:
1s is even, and also the number of 0s is even1s + the number of 0s) is evenAfter I thought about it, I realised that none of these options make much sense with the question posed. They all make the opening statement/claim false (even though the question asks us to prove why it is true). It turns out that the question does not mean any of these options but instead means:
every row and every column of the resulting table has an even number of ones in it.
Or in other words, if we add all the digits of a row or a column (of the extended table) we will get an even number. This is made clearer in the answer, where the parity of rows and columns is mentioned. Parity, in general, means whether an integer is even or odd. If we are talking about the parity of a string of bits (as in our case) then parity refers to the parity of the sum of the bits, or in other words whether the number of 1s in the string is even or odd. In computer science, we have the parity bit which is a bit added to a string of bits in order to always make the parity of the (extended) string be even. So in essense this question asks about adding an extra row and an extra column of parity bits.
Also note that the ending question which mentions
has an odd number of binary digits
is clearly wrong. They mean to say:
has an odd number of binary ones
Let's look into the heart of the question. What is the problem here? If I give you a string of bits, it's easy to compute the (even) parity bit. You count the 1s and if they are even the parity bit is $0$, otherwise we set it to $1$. Here are the parity bits (in blue) for every row and column of your example table:
$$ \begin{array}{llllll|l} 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ \hline \color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}& \color{red}? \end{array} $$
They all happen to be $1$ with the table example you gave. The real problem is: What is the bit denoted as a red questionmark? This bit should set the even parity for both the extra row and the extra column. In other words, it is the parity bit of the column of parity bits, as well as the parity bit of the row of parity bits. Since just a single string of bits (either a row or a column) can fully specify a parity bit, our red questionmark bit is overspecified. In our example above we can set it to $\color{red}0$ and satisfy both the extra row and column (i.e., we can set it with no conflict).
Let's see another table. Just take our previous example table and make it non-square by removing the last row. So now we have:
$$
\begin{array}{llllll|l}
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
\hline
\color{blue}{1}&\color{blue}{0}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}& \color{red}1
\end{array}
$$
Again we find that the overspecified bit satisfies the even parity of both the extra row and the extra column. Is this always the case? The question claims that it is, and we need to explain why.
The first observation I made was that if we change a single bit in the $6\times 6$ table of our example (or the truncated $5\times 6$ table), a single bit in the parity column will change, and a single bit in the parity row will also change. This means that the overspecified bit will change too, and both parity row and parity column will be in agreement. So any number of bit changes we make for these table sizes will be ok (no conflict for the overspecified bit). But is there some other table size that produces a conflicted overspecified bit? We could perhaps make an inductive proof for every size table starting with a $1\times 1$ table, but there is a simpler method:
I made this general observation about even parity:
The parity of a concatenation of two strings is equal to the parity of concatenating their parity bits.
This might sound a bit confusing, so let me write it with symbols in order to make it more digestable. I will use the following notation: If $S$ is a string of bits, then $P_e(S)$ is the even parity bit of this string. Also if $S_1, S_2$ are bitstrings, then $S_1\oplus S_2$ is the concatenation of these two strings (in other words "glue" them together to make a bigger string). Finally a parity bit can be considererd a bitstring of length one and can be concatenated with other strings. This is what I claim:
$$P_e(S_1\oplus S_2) = P_e(P_e(S_1)\oplus P_e(S_2))$$
To prove this claim simply consider all four combinations of parity for two strings: (odd, odd), (even, odd), (odd, even), (even, even). Note that when we concatenate two odd strings we get one even string, when we concatenate one odd and one even we get odd, and finally two even strings concatenate in one even. Let $O$ denote odd strings and $E$ denote even strings in the formulas below.
$$ \begin{array}{rlrlrl} P_e(O\oplus O)&= P_e(P_e(O)\oplus P_e(O)) &\iff P_e(E) &= P_e(1\oplus 1)) &\iff 0&=0 \\ P_e(O\oplus E)&= P_e(P_e(O)\oplus P_e(E)) &\iff P_e(O) &= P_e(1\oplus 0)) &\iff 1&=1 \\ P_e(E\oplus O)&= P_e(P_e(E)\oplus P_e(O)) &\iff P_e(O) &= P_e(0\oplus 1)) &\iff 1&=1 \\ P_e(E\oplus E)&= P_e(P_e(E)\oplus P_e(E)) &\iff P_e(E) &= P_e(0\oplus 0)) &\iff 0&=0 \end{array} $$
And more generally: $$P_e(S_1\oplus S_2\oplus \dots \oplus S_n) = P_e(P_e(S_1)\oplus P_e(S_2)\oplus \dots \oplus P_e(S_n)) \qquad (\text{lemma}\; 1)$$
The generalisation is actually crucial for what we want to prove. I will not give a full proof here, but instead provide a sketch and leave the fleshed out proof as an exercise. To prove lemma 1 we need to consider having $i$ odd strings and $k$ even strings. Then examine all four cases were $i,k$ are
(odd, odd), (even, odd), (odd, even), (even, even).
After we have established lemma 1, notice again that the overspecified bit is the even parity of the bits in the parity column. In turn, the bits in the parity column are the even parities of the rows of the table. So, using lemma 1, we can say that the overspecified bit is the even parity bit of all the bits in the table. If this is unclear just set strings $S_1,\dots S_n$ in lemma 1 to be the rows of bits of our table. Moreover, we can have the same argument about the overspecified bit being the parity of the bits in the parity row, and again we end up with the overspecified bit being equal to the parity of all bits in the table (this time we set strings $S_1,\dots S_n$ in lemma 1 to be the columns of bits of our table). In other words, it does not matter if we consider all the bits row-first, or column-first, the overspecified bit is essentially calculated as the even parity bit of all bits in the table. In a picture:
$\hspace{2cm}$
Saying the same thing with formulas: Let $R_1, R_2,\dots R_n$ be the rows of the original (non-extended) table of bits. And let $C_1, C_2,\dots C_n$ be the columns. We have:
$$ P_e(P_e(R_1)\oplus P_e(R_2)\oplus \dots \oplus P_e(R_n)) \stackrel{\text{lemma 1}}= P_e(R_1\oplus R_2\oplus \dots \oplus R_n) = P_e(\text{all the bits in the table}) = P_e(C_1\oplus C_2\oplus \dots \oplus C_n) \stackrel{\text{lemma 1}}= P_e(P_e(C_1)\oplus P_e(C_2)\oplus \dots \oplus P_e(C_n)) $$
I believe that the answer given on the webpage is playing with properties closer to my first observation. The problem is that it describes the "solution" with very few words ("addition of tables (using cell-by-cell xor) preserves even parity") and ends up being obscure. When I first read it, I had no idea what it meant. Now that I've done my analysis I think I understands what it means.
I believe that the general idea is to break the table into "basic" tables where only one cell has a 1 and then you add the parity row and column for each of them to get an extended "basic" table. The parity row and column of an extended "basic" table have only one 1 bit each, and the overspecified bit is always 1. Then you combine these extended basic tables by doing bitwise XOR operations and it is implied that you get your initial extended table. It is further implied that there will always be a valid oversimplified bit. Even though all this is correct, it needs considerably more work to be proven and explained properly. It seems to me that this solution gets messy when you try to explain it properly. I prefer my approach, as I think it's cleaner, but that's a matter of taste.
The question finally asks us what happens if we choose odd parity. Can we always have a valid overspecified bit? It seems that it is nudging us towards a "no". It's easy to find a counterexample. Just look at the truncated table we used before. Let's consider the odd parities this time: $$ \begin{array}{llllll|c} 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ \hline \color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{0}& \color{red}{0/1} \end{array} $$
We see that now the overspecified bit is conflicted. We could stop there as far as the question is concerned (we found a counterexample) but thanks to our earlier analysis we know why this is the case: Odd parity does not have the property that even parity has. More specifically:
$$P_o(S_1\oplus S_2\oplus \dots \oplus S_n) \neq P_o(P_o(S_1)\oplus P_o(S_2)\oplus \dots \oplus P_o(S_n))$$
For example, consider three odd-parity strings: $$P_o(O\oplus O \oplus O) \neq P_o(P_o(O)\oplus P_o(O) \oplus P_o(O)) \iff P_o(O) \neq P_o(0\oplus 0 \oplus 0)) \iff 0 \neq 1$$
I hope you now have a much fuller understanding of the question and the answer. It was certainly rewarding for me to investigate it.
You have to look at the structure of how a floating point number is stored. In IEEE 754 a 64 bit float is defined to have a sign bit $S$, $11$ bits of exponent $E$, and $53$ bits of mantissa $M$. The first bit of the mantissa is always $1$ and not stored, so only $52$ bits are stored. The value is $(-1)^S \cdot 2^{E-1023}\cdot M$ where $M$ is in binary with the radix point after the first (unstored) bit. This gives that there are $2^{52}$ values of $M$, so for each value of exponent we get $2^{52}$ floating point numbers.
To count the numbers between $n_1=0.009999999999999999999999999999$ and $n_2= 0.099999999999999999999999999999$ we first count the full steps of the exponent, then handle the partial steps at the end. $n_1 \lt 2^{-6}=0.015625$ and $n_2\gt 2^{-4}=0.0625$ so we get $3 \cdot 2^{52}$ numbers there. In the step where the exponent part is $2^{-7}$ the $\epsilon$ is $2^{-59}$ so there are $2^{59}(0.015625-n_1)=3242591731706757$. In the step where the exponent is $2^{-3}$ the $\epsilon$ is $2^{-55}$, so there are $2^{55}(n_2-0.0625)=13510798882111487$. If my copy and paste skills are working the total is $30264189495929732$ I think the rounding is correct. I don't care to try to list them all. It is definitely not the same as from $0$ to $0.09$ because that has over $1000$ steps of a factor two, so over $1000 \cdot 2^{52}$ numbers. In floating point the numbers are very dense near zero. You are adding a span near zero, so adding lots of numbers and not deleting nearly as many since the deleted span is "far from zero".
If you have the right tool available, you could just get the binary representation of $n_1$ and $n_2$ and subtract them. As the floating point representations are ordered the same way the corresponding values are, that will give you the count. Remember to subtract one because you shouldn't count either end.
Best Answer
The range is determined by the biggest and smallest (positive) numbers you can represent. Clearly, with two digits in the exponent you can write numbers from approximately $10^0$ (or $10^{-99}$ if you allow signs) to $10^{99}$ (even more by clever choce of mantissa). With one-digit exponents the range is much smaller: from $10^{-9}$ to $10^{9}$.
The precision is determined by the smallest (relative) difference between two representable numbers. The difference between $3.14$ and $3.15$ is about $0.3\%$ of the values (and also the difference between $6.02\cdot 10^{23}$ and $6.03\cdot 10^{23}$ or between $1.60\cdot 10^{-19}$ and $1.61\cdot 10^{-19}$ is of the same - relative - magnitude. On the other hand $3.1415926535897932384626433$, $6.02214129\cdot10^{26}$ and $1.602176565\cdot10^{-19}$ carry a lot more precision. The latter two are numerical values for the Avogadro constant and the elementary charge. Obtaining thes values required very precise measurements. The precision does not depend on the exponent. That is, if the value of $e$ in other unit systems is $1.602176565\cdot10^{6}$, the same careful prcision in the measurements is required to obtain so many digits.