|No such thing as a small change|
Re: The golf course looks great, my swing feels good, I like my chances (Part IV)by primo (Scribe)
|on Jun 07, 2013 at 12:26 UTC||Need Help??|
the 1000 Digits of Pi game, where Perl was left far behind (I didn't play that one, so don't know why)
Both the Ruby and Python solutions rely on native support for arbitrary integer precision, essentially calculating π * 101000, and then hacking in the decimal place at the end. While Perl does have libraries for this, unfortunately all types of import statements have been disallowed for all languages. Had bignum been available, the following would have been fairly competitive at 59 strokes:use bignum a,1001;$c=6x4;$_=$_/$c*--$c/2+2while$c-->2;print
which is basically identical to the shortest Ruby and Python solutions.
The final 1989 is unfortunately necessary, because the last few digits don't quite converge.
As of Math::BigFloat v1.87, this would also be valid for 29 strokes:use bignum bpi;print bpi 1001
although Perl 5.8.8 seems to be packaged with Math::BigFloat v1.60, so this wouldn't have worked anyway.
The formula used is this:pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + ...)))))
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:
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:--$h?$%=($f[$h]=$h--/2*$%+$f[$h%=7875]%$h*1e8)/$h:printf$a?"%08d":"3.",$a%1e8+($a=$%)/1e8for@f=(2)x5e5
102 bytes, nearly twice as long as the best Ruby solution. Fortunately, this can be adjusted to a suitable pack u format with very little effort (but at the cost of 4 (3 packed) bytes):
resulting in a code length of 95 bytes, which is where it currently stands.
Wait a minute, wasn't there a Perlgolf digits of Pi post-mortem?Why yes, yes there was. PCLP #5.2, which can be found in the 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:
78, Rick Klement
78, Ton Hospel
Ton later reduced Rick's solution to 77 strokes post-mortem:($c,@0)=map P|($c=$c%($d=10+20*$?).0+$_*$?)/$d,@0while$?-=@0[0,1e3]=3;print@0
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 (2*$?||239 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 codegolf server.
But not all hope is lost. Both solutions abuse the fact that $? 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 string -> int 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 3 with '3.'.
A re-work of Rick's solution, 12 bytes heavier, but 28 times as fast:$a=3322;($c,@0)=map 0|($c=$c%($d=10+20*$a)*10+$_*$a)/$d,@0while$a-=@0[0,1001]='3.';print@0
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.
And finally, my own post mortem to PCLP #5.2:
56, primo ((very) post-mortem)
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.