Today I thought I'd implement a way to compute pi using continued fractions

I was trying to get 1000 decimals for codegolf.com , but I was only able to get 10 correct decimals(yes, I know..pathetic) in 6 seconds(codegolf limits this to 4 seconds).

I used the formula here(the one in the middle),and wrote code that weighs at about 140 bytes , but the 1st entry in codegolf.com for this problem has 54 bytes or so.

Anyone care to divulge their (partial) solution to this ?

Maybe they treat the problem as one of compressing those 1000 digits rather than computing them? And if so, I think there were some theoretical bounds to compressing data, I do not remember what those were ... I'm pretty sure codegolf doesn't allow use of modules and implementing your own compression algo would jump over 54bytes for sure , or not ?

use bignum qw/p -20/;
my ($pi,$n) = ('3+1/(X)',1500);
$pi =~ s{X}{
    '6'.
    (
        $_!=$n
        ?'+'.((2*$_+1)**2).'/(X)'
        :''
    ) 
}e for(1..$n);
print eval $pi;

[download]

Replies are listed 'Best First'.
Re: pi and some continued fractions
by snoopy (Curate) on Nov 08, 2009 at 21:06 UTC
    Btw, if you could use bignum here, its bpi function would make this easy: 
     perl -Mbignum=bpi -e 'print bpi(1000)'

    [download]
[reply]
[d/l]
[select]
Re: pi and some continued fractions
by eyepopslikeamosquito (Archbishop) on Nov 09, 2009 at 13:18 UTC

    I was most surprised to notice -- as pointed out in The golf course looks great, my swing feels good, I like my chances (Part IV) in the "Which Language Produced the Shortest codegolf Code?" section -- that the shortest Perl solution in the 1000 Digits of Pi codegolf game of 102 strokes was far behind both Ruby (54 strokes) and Python (62 strokes). This is unusual in the extreme because in the other 26 games Perl was consistently well ahead of Python, yet here was 40 strokes behind! Why? I'm afraid I don't know because I didn't play that game ... though I bet "primo" does since he holds the lowest score in all four languages. :) A wild guess is that Python has native bignums and that is crucial for this game.

    The code golf forum for this game may provide some useful tips. In particular, the Rabinowitz method was recommended by "hendrik" (see for example this page) -- and hendrik solved this problem in Python in 67 strokes, just five behind the Python leading pack. Also, "hallvabo" suggested (if your solution is "close" to the 4 second time limit) submitting your solution at different times of day because the codegolf server load apparently varies considerably and your solution only need pass once to be accepted.

[reply]
Re: pi and some continued fractions
by grizzley (Chaplain) on Nov 09, 2009 at 13:44 UTC
    Exactly, as eyepopslikemosquito said: Spigot algorithm. And here or here is ready to use program in C, which can be easily converted to Perl (but kudos for those, who can optimize it significantly for Perl golf): 
    /* Calculation of pi to 32372 decimal digits */
/* Size of program: 152 characters */
/* After Dik T. Winter, CWI Amsterdam */
unsigned a=1e4,b,c=113316,d,e,f[113316],g,h,i;
main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d-g*h;}

    [download]
[reply]
[d/l]
Re: pi and some continued fractions
by goibhniu (Hermit) on Nov 09, 2009 at 21:00 UTC

    I implemented the spigot algorithm already mentioned in 266 strokes (for a start) but never got it to run in the required 4 seconds. It's plenty fast on my local machine, but not on the codegolf server. Since I couldn't submit the baseline, I never got around to shortening it.

    #my sig used to say 'I humbly seek wisdom. '. Now it says:
    use strict;
    use warnings;
    I humbly seek wisdom.
[reply]
[d/l]

Back to Meditations