Beefy Boxes and Bandwidth Generously Provided by pair Networks
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 ( #1037665=note: print w/replies, xml ) Need Help??

in reply to The golf course looks great, my swing feels good, I like my chances (Part IV)

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.

And this would have taken the lead at 40 strokes, utilizing the built-in atan2 function:

use bignum a,997;print atan2(1,1)*4,1989

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:

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 }

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:


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):

# 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

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
($c,@0)=map P|($c=$c%($d=20*$?+10).0+$_*$?)/$d,@0while@0[0,1e3]=3,--$?;print@0

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)
use bigint;$c=6x4;$_=$_/$c*--$c/2+2e999while$c-->2;print

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.

Replies are listed 'Best First'.
Re^2: The golf course looks great, my swing feels good, I like my chances (Part IV)
by eyepopslikeamosquito (Bishop) on Jun 07, 2013 at 20:54 UTC

    I have no idea how Ton's solution works
    Ha ha! This was a common problem back in the good old days. Eugene van der Pijll, even after defeating Ton with his Mad Dutch algorithm to win the TPR(0,5a) infix-to-postfix tournament, never did understand Ton's third-placed solution. Ton was by far the most inventive golfer of that era, often unearthing astonishing hacks from deep study of perl's C implementation.

    That was terrifically interesting primo, thanks!

Re^2: The golf course looks great, my swing feels good, I like my chances (Part IV)
by teebee (Initiate) on Sep 08, 2013 at 04:38 UTC
    You can save two more strokes by using for instead of while:

    54 strokes
    use bigint;$p=$p/~(2*$_)*~$_+2e999for-3333..-2;print$p

      And two more by using $\

      use bigint;$\=$\/~(2*$_)*~$_+2e999for-3319..-2;print


        Yes, but only if you use a more recent perl, 5.14 or above I think. With perl 5.8 one gets: Can't call method "copy" without a package or object reference at Math/ line 111.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1037665]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2021-04-21 02:54 GMT
Find Nodes?
    Voting Booth?

    No recent polls found