4
$\begingroup$

While I was reading this one wikipedia page on floating-point arithmetic, I stumbled upon a calculation that I found interesting. So, I decided just for fun to try and work it out. I used a spreadsheet to do the summing.

But following both the text description and the sigma notation verbatim [to the best of my understanding, anyway], I wasn't able to arrive at the same solution that the wikipedia page arrived at.

Before I ask my questions, here is the snippet from that wikipedia page that describes the calculation:

...

The common IEEE formats are described in detail later and elsewhere, but as an example, in the binary single-precision (32-bit) floating-point representation, ${\displaystyle p=24}$, and so the significand is a string of 24 bits. For instance, the number π's first 33 bits are:

$$11001001\phantom{2}00001111\phantom{2}1101101\underline0\phantom{2}10100010 0.$$

If the leftmost bit is considered the 1st bit [the MSB], then the 24th bit is zero and the 25th bit is 1; thus, in rounding to 24 bits, let's attribute to the 24th bit the value of the 25th, yielding:

$$11001001\phantom{2}00001111\phantom{2}1101101\underline1.$$ When this is stored using the IEEE 754 encoding, this becomes the significand ${\displaystyle s}$ with ${\displaystyle e=1}$ (where ${\displaystyle s}$ is assumed to have a binary point to the right of the first bit [the LSB?]) after a left-adjustment (or normalization) during which leading or trailing zeros are truncated should there be any, which is unnecessary in this case; as a result of this normalization, the first bit [the MSB? the LSB?] of a non-zero binary significand is always 1, so it need not be stored, saving one bit of storage. In other words, from this representation, π is calculated as follows:

\begin{align*} &( 1 + \sum _{n=1}^{p-1}bit_{n} \times 2^{-n} ) \times 2^{e}\\ &= ( 1 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-4} + 1 \times 2^{-7} + \cdots + 1 \times 2^{-23}) \times 2^{1}\\ &= 1.5707964 \times 2\\ &=3.1415928\\ \end{align*}

where ${\displaystyle n}$ is the normalized significand's nth bit from the left [the MSB?], where counting starts with 1...

In-lined inside the square brackets "[]" in the above quoted wikipedia page, I'm using MSB to mean "Most Significant Bit"; and LSB to mean "Least Significant Bit".

I've in-lined those remarks to highlight parts of that description that are throwing me off. What's confusing to me is, the description starts off denoting the MSB as "the first bit". Then it starts referring to the LSB as "the first bit".

Looking at the 24 bit binary number given [${\displaystyle11001001\phantom{2}00001111\phantom{2}1101101\underline1.}$], the order of the corresponding bits that appear in the expansion of the summation [${\displaystyle1 + 1 \times 2^{-1} + 0 \times 2^{-2} + \cdots}$] suggest that the calculation starts from the LSB.

So starting at the LSB, the first cell of my spreadsheet (A1) has the value 1. The "first bit".

In the second spreadsheet cell (A2), I have a formula that multiplies the 1 bit in the binary 2s place, by ${\displaystyle 2^{-1}}$.

In the third spreadsheet cell (A3), I multiply the 0 bit in the binary 4s place by ${\displaystyle 2^{-2}}$...and so on consecutively and respectively up to the MSB.

So my spreadsheet has a column of 24 cells that correspond to the 24 bits. The first cell simply has the value 1. The remaining 23 cells have a formula: bit * POWER(2;-n) (where 'bit' is one of '0' or '1'; and 'n' corresponds to the 'nth bit' specification of the above description - having a range of '1-23'). The 25th cell in that column has the formula SUM(A1:A24) * POWER(2;1).

The sum I get with that formula when starting my counting at the LSB, is ${\displaystyle3.436558485}$. The sum I get with that formula when starting my counting at the MSB, is ${\displaystyle3.5707962513}$.

The sum I get with that formula when starting my counting at the LSB, and excluding ${\displaystyle2^{3}+\cdots+2^{5}+\cdots+2^{6}\cdots}$ from the calculation, is ${\displaystyle3.155308485}$.

The sum I get with that formula when starting my counting at the MSB, and excluding ${\displaystyle2^{3}+\cdots+2^{5}+\cdots+2^{6}\cdots}$ from the calculation, is ${\displaystyle3.5082962513}$.

Now, here are my questions:

  1. What is the correct sigma notation for converting the binary representation of pi to its decimal representation?
  2. Why doesn't the example on the wikipedia page include ${\displaystyle2^{3}+\cdots+2^{5}+\cdots+2^{6}\cdots}$ in its calculation?
  3. What do I need to correct in my spreadsheet formula to make it arrive at the same answer that the wikipedia page arrives at?
  4. Does that description need correcting in its confusing reference to both the MSB and the LSB as "the first bit"?
  5. Does the sigma notation in that description need correcting to make it clear that ALL of the bits should be included in the calculation?
  6. Going by what I described of my spreadsheet calculation, what step(s) or what fundamental mathematical concept have I overlooked or misunderstood?

Thanks in advance.

$\endgroup$
1
  • $\begingroup$ Instead of describing the spreadsheet, you should post a simple version which shows the problem, as with any computer code. The question is not helped by repeating every link to the same URL. $\endgroup$ Commented Nov 5, 2017 at 18:58

3 Answers 3

Reset to default
2
$\begingroup$

The sigma notation is correct, and maybe the best one as it is non-ambiguous.

The Wikipedia page excluded $2^{-3}$, $2^{-5}$ and $2^{-6}$ because their corresponding bits were 0's: $0 × 2^{-3} = 0$, etc. However, this could be confusing.

I also agree that "the first bit" was a poor choice, because bits can be read left-to-right or right-to-left (both can be useful, depending on the context).

I think that the various issues on the Wikipedia page have now been solved with the corrections you and I did.

Moreover, be careful that in addition to the fact that the truncated binary expansion is an approximation to the real value, the binary-to-decimal conversion is also approximated (unless you take into account all the decimal digits of the powers of two).

Note that for better understanding, you may also be interested in:

$\endgroup$
4
  • $\begingroup$ Ahh! I see. Thx vinc17. I don't know why the corresponding 0 bits for ${\displaystyle 2^{-3}, 2^{-5}, 2^{-6}}$ didn't occur to me. No wait. I do know why. It's because I'm not a professional mathematician, and you are Haha ;¬) The reason I was thrown off by that is because my naive understanding of sigma notation is that it's meant to represent a generally-applicable calculation that could be applied to any arbitrary sequence of numbers. Whereas the intention of the notation in the FP pi example, was written specifically to be applicable to only one particular number with that set of bits. $\endgroup$ Commented Nov 10, 2017 at 2:27
  • $\begingroup$ Before our edits @vinc17, the corresponding ${\displaystyle 0 \times 2^{-2}}$ term for the ${\displaystyle0}$ three digits in from the left was included in the original sequence of additions. So they counted one ${\displaystyle0}$, but not others? To me, it looks like the original contributor was applying some arbitrary rules of notation that only s/he knew in their own head. But hey! It stood the test of time; unchallenged since 2009. So I guess I'm the only one who was confused by it. I'd better get cracking boning up on those links you posted vinc17. Thanks for those. $\endgroup$ Commented Nov 10, 2017 at 18:09
  • $\begingroup$ Yes, the $0×2^{-2}$ term was confusing. FYI, it was added in revision 284569155 (diff). It seems that the contributor didn't really know what he was doing. $\endgroup$ Commented Nov 11, 2017 at 0:13
  • $\begingroup$ HaHa! You spotted that too, huh @vinc17? HaHa! I love their use of the technical jargon, "Oops!", to explain the rationale behind their abuse of notation. $\endgroup$ Commented Nov 11, 2017 at 18:17
2
$\begingroup$

What a difference a day makes :¬)

It turns out that the Wikipedia page's sigma notation was correct after all. It's just that their worked-out calculation is in fact wrong. Misleading, at best. Plus the textual explanation isn't as clear as it should be.

The key to working out the calculation correctly — and keeping it aligned with the sigma notation in the wiki — is in the last sentence of the snippet in my original post...

...where ${\displaystyle n}$ is the normalized significand's nth bit from the left [the MSB?], where counting starts with 1...

They're not using ${\displaystyle n}$ to denote the ordinal position of the bits. They're using ${\displaystyle n}$ simply as an index for iterating over the sequence of bits. If I'm not mistaken, that is precisely what the common usage of sigma notation expects.

The crucial snippet I just re-quoted is telling the reader that the first bit to count is the MSB (the left-most bit). And that the iteration index ${\displaystyle n}$ that will be used in the calculation — ${\displaystyle bit_{n} \times 2^{-n}}$ — needs to start at 1.

Once the penny dropped, I was able to correct my spreadsheet accordingly. Now it calculates the correct answer for pi. And the formulas I use are exactly what is prescribed by the original sigma notation.

I've learned enough in the last 24 hours to take a stab at answering my own questions...

  1. What is the correct sigma notation for converting the binary representation of pi to its decimal representation?

The original sigma notation is actually correct after all.

  1. Why doesn't the example on the wikipedia page include ${\displaystyle2^{3}+\cdots+2^{5}+\cdots+2^{6}\cdots}$ in its calculation?

The Wikipedia page excluding ${\displaystyle2^{3}+\cdots+2^{5}+\cdots+2^{6}\cdots}$ out of its calculation was not simply "abuse of notation" as I first suspected. It is just plain wrong. Probably a typo.

  1. What do I need to correct in my spreadsheet formula to make it arrive at the same answer that the wikipedia page arrives at?

The formulas I was using in my original spreadsheet were correct all along. I did need to correct which cell my calculation was starting from, however.

  1. Does that description need correcting in its confusing reference to both the MSB and the LSB as "the first bit"?

The original description most certainly does need to be edited to be made clearer in regards to its confusingly calling both the MSB and the LSB "the first bit".

  1. Does the sigma notation in that description need correcting to make it clear that ALL of the bits should be included in the calculation?

The actual sigma notation is correct. But the expanded calculation certainly does need to be corrected.

  1. Going by what I described of my spreadsheet calculation, what step(s) or what fundamental mathematical concept have I overlooked or misunderstood?

The placement of bits in incorrect cells of my spreadsheet was a result of my confusion over the ${\displaystyle n}$ index variable prescribed in the Wikipedia page. Once I remembered the role of the index variable in sigma notation, I understood then what I was doing wrong.

Here's some Java code based on the Wikipedia page's sigma notation...

import static java.lang.System.out; class Q2506277Converter { private static strictfp float binary32ToDecimal( String s /* the significand */ ) { byte n = 1; /* the 'n' in the sigma notation */ byte p = 24; /* the 'p' in the sigma notation */ byte bitN = 0; /* the 'bit_n' in the sigma notation */ byte e = 1; /* the 'e' in the sigma notation */ float sum = 0.0f; /* the summation in the sigma notation */ for(; n <= p-1; n++ ){ bitN = Byte.parseByte( s.substring( n, n+1 ) ); sum += (float)(bitN * Math.pow(2, -n) ); /* the '2^-n' in the sigma notation */ } return (1 + sum) * (float)Math.pow( 2, e ); /* the '2^1' in the sigma notation */ } public static void main( String[] args ){ /* IEEE 754 encoding significand */ String significand = "110010010000111111011011"; out.printf( "%.9f%n", binary32ToDecimal( significand ) ); } }

I don't know Python well enough to write one-liners. But here's some Python code based on the Wikipedia page's sigma notation...

sum = 0 e = 1 result = 0.0 for n, bitN in enumerate("110010010000111111011011"[1::1]): n = n+1 sum = sum + int(bitN) * 2**(-n) result = ( 1 + sum ) * 2**(e) print( result )
$\endgroup$
2
  • $\begingroup$ I haven't checked the details here, but it does look right. If as you say, something on wikipedia "does need to be corrected" then please take the time to correct it there! $\endgroup$ Commented Nov 7, 2017 at 2:22
  • $\begingroup$ Thanks @EthanBolker. I'll get on that. Probably tomorrow sometime. $\endgroup$ Commented Nov 7, 2017 at 2:36
0
$\begingroup$

Using Python to replicate your calculations, and enumerating the bit string from left-to-right,

sum(int(b)*2**(1-k) for k,b in enumerate("110010010000111111011011"))

correctly returns 3.1415927410125732. However, enumerating the bit string in the wrong direction (from right-to-left)

sum(int(b)*2**(1-k) for k,b in enumerate("110010010000111111011011"[-1::-1]))

indeed delivers the same incorrect 3.436558485031128 result mentioned in the OP.

The enumeration in the Wikipedia citation is indeed somewhat in conflict with the common notation. For example, in $$ \sum b_n2^{-n}\cdot 2^e $$ the index starts on the left with $n=0$ enumerating the most significant bit. That is to say, that notation instructs you to read the bit string from left-to-right as $b_0,b_1,...,b_{23}$.

In the more common notation, however, bit counting is usually oriented on the dyadic powers (the powers of 2) that make up the binary integers. So bit0 would be the right-most bit. The bit string would, therefore, be read from left-to-right as $bit_{23},bit_{22},...,bit_0$ and the corresponding formula should be $$ \sum_{n=0}^{23} bit_n\cdot 2^{n-23} $$

So the WP formula is in accordance with the usual array indexing idiom where elements are read left-to-right starting with index 0 or 1.

$\endgroup$
3
  • $\begingroup$ Thanks @LutzL. I can see how your int(b) corresponds to your ${\displaystyle bit_{n}}$. Unfortunately though, I'm struggling to grok how your 2**(1-k) corresponds to your ${\displaystyle 2^{n-23}}$. For example, when ${\displaystyle n = 0}$, ${\displaystyle 2^{n-23} = 1.19209289551e-07}$. But 2**(1-0) = 2. I'm not seeing how those two terms equate to one another, I'm afraid. Please can you break that down, just a teensy bit closer to first principles, for me? Please? Thanks. $\endgroup$ Commented Nov 5, 2017 at 22:15
  • $\begingroup$ Also, @LutzL. You're addressing my Q1 and Q5 nicely. Thanks again for that. What are your thoughts on any of my other questions (Q2, Q3, Q4 and Q6)? $\endgroup$ Commented Nov 5, 2017 at 22:21
  • $\begingroup$ Do you know what would really help drive your answer home for me @LutzL? Did you see how the wikipedia page elaborated out its calculation? e.g. ${\displaystyle = ( 1 + 1 \times 2^{-1} + \cdots + 1 \times 2^{-7} + \cdots + 1 \times 2^{-23})}$ If you could illustrate — like the wikipedia page does — how your Python calculation works out the summation bit by bit, that would be a huge help. Thanks. $\endgroup$ Commented Nov 5, 2017 at 23:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.