StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><B>Update</B></p> <p>This program is a purposely obfuscated implementation of a <a href="http://en.wikipedia.org/wiki/Spigot_algorithm" rel="nofollow noreferrer">spigot</a> algorithm <a href="http://www.mathpropress.com/stan/bibliography/spigot.pdf" rel="nofollow noreferrer">for the Digits of Pi</a> from the book <em>Pi - Unleashed</em> and we can find the original version on <a href="http://books.google.com/books?id=QwwcmweJCDQC&pg=PA37&source=gbs_toc_r&cad=4#v=onepage&q&f=false" rel="nofollow noreferrer">page 37 of the book</a> which is as follows:</p> <blockquote> <p>a[52514],b,c=52514,d,e,f=1e4,g,h;main(){for(;b=c-=14;h=printf("%04d", e+d/f))for(e=d%=f;g=--b*2;d/=g)d=d<em>b+f</em>(h?a[b]:f/5),a[b]=d%--g;}</p> </blockquote> <p>the paper <a href="http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf" rel="nofollow noreferrer">Unbounded Spigot Algorithms for the Digits of Pi</a> does a good job in explaining the algorithm. Basically it is an implementation of this expansion:</p> <p><img src="https://imgh.us/preview_2.svg" alt="formula"></p> <p><B>Original</b></p> <p>The reason it was designed this way other than to make the code impossible to comprehend and impress people escapes me but we can break down what is going on, first here:</p> <pre><code>long a[35014],b,c=35014,d,e,f=1e4,g,h; </code></pre> <p>the variables are <em>static</em> since they are global so all variables not explicitly initialized will be initialized to <code>0</code>. Next we have an outer <em>for loop</em>:</p> <pre><code>for(;(b=c-=14); h=printf("%04ld",e+d/f) ^ ^ ^ 1 2 3 </code></pre> <ol> <li>Is an empty initialization and it also a <a href="https://stackoverflow.com/a/19507325/1708801">null statement</a>.</li> <li>Is subtracting <code>14</code> from <code>c</code> and assigning the value back to <code>c</code> and also assigning the same value to <code>b</code>. This loop will execute <code>2500</code> times since <code>35014/14</code> is 2501 and on the <code>2501</code>th iteration the result will <code>0</code> and thus <em>false</em> and the loop will stop.</li> <li><code>h</code> is being assigned the result of <code>printf</code> which is the number of characters printed. What is being printed out is the result of <code>e+d/f</code> and always at least 4 digits and zero padded due to <code>04</code> in the <em>format specifier</em>.</li> </ol> <p>Now we have an inner <em>for loop</em>:</p> <pre><code>for(e=d%=f;(g=--b*2);d/=g) ^ ^ ^ 1 2 3 </code></pre> <ol> <li>Initializes <code>e</code> and <code>d</code> to <code>d modulus f</code>.</li> <li>Due to <a href="http://www.swansontec.com/sopc.html" rel="nofollow noreferrer">operator precedence</a> does a <em>pre-decrement</em> of <code>b</code> and multiples that by <code>2</code> and assigns the result to <code>g</code></li> <li><code>d</code> is being divided by <code>g</code> and assigned the result.</li> </ol> <p>Finally the body of the inner for loop:</p> <pre><code>d=d*b+f*(h?a[b]:f/5), a[b]=d%--g; ^ ^ 1 2 </code></pre> <p>uses both the <A href="http://en.wikipedia.org/wiki/%3F:#C" rel="nofollow noreferrer">conditional operator</a> in <code>1</code> and <a href="http://en.wikipedia.org/wiki/Comma_operator" rel="nofollow noreferrer">comma operator</a> in <code>2</code>. So we could at least split this into:</p> <pre><code>d = d*b+f*(h?a[b]:f/5) ; // (1) a[b] = d%--g; // (2) </code></pre> <p><code>(1)</code> can further be broken down into:</p> <pre><code>long tmp = h ? a[b] : f/5 ; // conditional operator d = (d * b) + f * tmp; </code></pre> <p>The conditional operator only matters during the first iteration since <code>h</code> is intialized to <code>0</code> but will never be <code>0</code> again afterwards since it is always assigned a non-zero value in the outer <em>for loop</em>, so other then the first time <code>h</code> will be assigned <code>a[b]</code>.</p> <p><code>(2)</code> will again due to precedence pre-decrement <code>g</code> first and then evaluate <code>d</code> modulus the result and assign that to <code>a[b]</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload