note
primo
<blockquote><i>the 1000 Digits of Pi game, where Perl was left far behind (I didn't play that one, so don't know why)</i></blockquote>
<p>Both the Ruby and Python solutions rely on native support for arbitrary integer precision, essentially calculating π * 10<sup>1000</sup>, and then hacking in the decimal place at the end. While Perl does have libraries for this, unfortunately all types of <code>import</code> statements have been disallowed for all languages. Had <code>bignum</code> been available, the following would have been fairly competitive at 59 strokes:</p>
<code>use bignum a,1001;$c=6x4;$_=$_/$c*--$c/2+2while$c-->2;print</code>
<p>which is basically identical to the shortest Ruby and Python solutions.</p>
<p><b><<UPDATE;</b><br>
And this would have taken the lead at 40 strokes, utilizing the built-in <code>atan2</code> function:</p>
<code>use bignum a,997;print atan2(1,1)*4,1989</code>
<p>The final <code>1989</code> is unfortunately necessary, because the last few digits don't quite converge.</p>
<p>As of Math::BigFloat v1.87, this would also be valid for 29 strokes:</p>
<code>use bignum bpi;print bpi 1001</code>
<p>although Perl 5.8.8 seems to be packaged with Math::BigFloat v1.60, so this wouldn't have worked anyway.<br>
<b>UPDATE</b></p>
<p>The formula used is this:</p>
<code>pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + ...)))))</code>
<p>When doing this challenge, I spent a long time comparing formulas for calculating π (of which there are dozens), but this seems to be the only one to converge in any reasonable amount of time (and after conversing with several golfing maestros (specifically flagitious, hallvabo and leonid), they all came to use the same formula). In order to compute this without support for arbitrary precision, each division needs to be broken into stages, storing the modulo in an array, and continuing down until the desired precision is reached. I originally submitted in PHP before Perl, but the general algorithm I ended up with is this:</p>
<code>for($c=3429;$b=$c-=27;$e=$d%1e8){
for(;--$b;){
$d=$d*$b+($e?$f[$b]:2)*1e8;
$f[$b]=$d%($g=2*$b-1);
$d=0|$d/$g
}
printf$e?'%08d':'%d.',$e+$d/1e8
}</code>
<p>which calculates 8 digits at a time, and then carries on to the next chunk. It's also quite fast. After literally years of on-and-off golfing, my final Perl revision looked like this:</p>
<code>--$h?$%=($f[$h]=$h--/2*$%+$f[$h%=7875]%$h*1e8)/$h:printf$a?"%08d":"3.",$a%1e8+($a=$%)/1e8for@f=(2)x5e5</code>
<p>102 bytes, nearly twice as long as the best Ruby solution. Fortunately, this can be adjusted to a suitable [id://995190|pack u] format with very little effort (but at the cost of 4 (3 packed) bytes):</p>
<code># 1 2 3 4 5 6
#234567890123456789012345678901234567890123456789012345678901
m_;--$h?$%=($f[$h]=$h--/2*$%+$f[$h%=7875]%$h*1e8)/$h:+printf$
a?"%08d":"3.",$a%1e8+($a=$%)/1e8for@f=(2)x5e5</code>
<p>resulting in a code length of 95 bytes, which is where it currently stands.</p>
<p><h3>Wait a minute, wasn't there a Perlgolf digits of Pi post-mortem?</h3>
Why yes, yes there was. PCLP #5.2, which can be found in the [http://terje2.frox25.no-ip.org/|perlgolf history book]. The winning solutions were submitted by (no surprise) Rick Klement and Ton Hospel, both at 78 bytes. Their solutions were as follows:</p>
<p><i>78, Rick Klement</i><br>
<code>($c,@0)=map P|($c=$c%($d=20*$?+10).0+$_*$?)/$d,@0while@0[0,1e3]=3,--$?;print@0</code></p>
<p><i>78, Ton Hospel</i><br>
<code>print!s!\w+!$\=($z=$&.0+$?--*$\)/++($b=2*$?||239)|0;$z%$b!egfor(-48x65536)x1e3</code></p>
<p>Ton later reduced Rick's solution to 77 strokes post-mortem:</p>
<code>($c,@0)=map P|($c=$c%($d=10+20*$?).0+$_*$?)/$d,@0while$?-=@0[0,1e3]=3;print@0</code>
<p>I'm going to focus on Rick's solution for two reasons. First, because he uses the same algorithm I do, and second, because I have no idea how Ton's solution works. I suspect he might be using the same algorithm, but I honestly can't be sure (<code>2*$?||239</code> seems rather bizarre, for example). If these two solutions do have anything in common, however, it's that they're both horrendously slow. Ricks solution takes approximately 47s on my computer, while Ton's clocks in at 136s. In my experience, anything that takes more than ~1.3s locally will timeout on the [http://codegolf.com|codegolf] server.</p>
<p>But not all hope is lost. Both solutions abuse the fact that <code>$?</code> is stored internally as an unsigned short, meaning that decrementing it will result in 65535, eliminating the need for initialization. However, only ~3322 iterations are necessary (each deeper iteration produces one more binary bit of π. Crazy, I know). There's also a lot of unnecessary <code>string -> int</code> conversion going on, which slows things down a bit as well. Rick's solution is also particularly nice to work with, because the decimal place can be hacked in simply by changing the literal <code>3</code> with <code>'3.'</code>.</p>
<p>A re-work of Rick's solution, 12 bytes heavier, but 28 times as fast:</p>
<code>$a=3322;($c,@0)=map 0|($c=$c%($d=10+20*$a)*10+$_*$a)/$d,@0while$a-=@0[0,1001]='3.';print@0</code>
<p>and... it times out. Almost fast enough at 1.67s locally, but not quite fast enough. Still fairly impressive though, considering that it calculates 1 digit at a time, instead of 8. If this could somehow be made ~25% faster, it could take the lead.</p>
<p>And finally, my own post mortem to PCLP #5.2:</p>
<p><i>56, primo ((very) post-mortem)</i><br>
<code>use bigint;$c=6x4;$_=$_/$c*--$c/2+2e999while$c-->2;print</code></p>
<p>As far as I can tell this should be entirely compliant with the rules, with a very acceptable run time as well at ~1.15s.</p>
763105
763105