# Calculate digits of Pi

This is a somewhat different task. Calculate 1024 hexadecimal digits of π, beginning at the 1024th hexadecimal place.

Formally: Your program should complete in less then 1 minute and produce the following output:

The program with the shortest length wins. You have to calculate all the digits at runtime. You do not have to implement the algorithm that computes π; if your language already provides that functionality, you can use it.

• Hah, should be easy. (+1, still) I bet I can make it execute in less than a few seconds. – Mateen Ulhaq Mar 11 '11 at 18:32
• @muntoo: And? Where is your solution? – FUZxxl Mar 16 '11 at 17:28
• I forgot to do it. :) BTW, speed != code-golf. – Mateen Ulhaq Mar 16 '11 at 17:29
• @muntoo: I know. But I also think, that 5 days is a good time for such an easy task. – FUZxxl Mar 16 '11 at 17:33

Sage, 29 char

This isn't technically cheating, since the digits are computed at runtime. That said, it's still cheap as hell.

hex(floor(pi*2^8192))[1025:]

• Definitly not cheating. – FUZxxl Jul 8 '11 at 18:43
• Mmmm, floor pi. – breadbox May 12 '12 at 18:50

# Shell Utilities: 48

curl -sL ow.ly/5u3hc|grep -Eom 1 '[a-f0-9]{1024}'

• All output is "calculated" at runtime. (thanks to OP posting the solution)
• Runs in under a minute. (may be dependent on your internet connection speed)
• Usually I downvote that kind of solutions, because they are a common abuse of the rules and no longer funny. But just because you are so sneaky to take the provided reference solution and write All output is "calculated" at runtime. (thanks to OP posting the solution), I give you an upvote ;) – FUZxxl Jun 30 '11 at 17:14
• Golfed version: curl -sL ow.ly/shKGY|grep -Po \\w{99,} (37). Works in Dash. Bash would need an additional byte. – Dennis Jan 5 '14 at 18:39

## JavaScript, 536

(Linebreaks and indentation for legibility only)

var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length';d=d+d;
function $(n,r){return n[e]<=r?0:d.indexOf(n[r])} function g(a,b){for(i=0,t='',s=16;i<l;i++,t+=d[~~(s/b)],s=(s%b)*16); for(;a--;t=_(t,t,1));return t} function _(a,b,s){for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;r=(s? function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c): function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r} for(i=0;i<l;i++,p+='2'); for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++); console.log(p.slice(1024,2048))  It takes about 25 seconds, on Google Chrome 14 on my lap-top using Intel i5 core. Can someone else golf this code? I can't golf well.. :( Below is non-golfed. I just remove all comments and changed for loop to golfing. Don't mention about for(;s>=b;s-=b);s*=16;. I changed it to s=(s%b)*16. :P /** Calculate PI-3 to 3000 (3e3) digits. a : a b : b c : carry d : digits e : length f : get from d g : calculate (2^a)/b. i,j, : for looping l : length to calculate p : pi r,t : return value */ var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length'; d=d+d;//for carring function$(n,r){return n[e]<=r?0:d.indexOf(n[r])}
/*
Calculate (2^a)/b. Assume that 2^a < b.
*/
function g(a,b){
for(i=0,t='',s=16;i<l;i++){t+=d[~~(s/b)];for(;s>=b;s-=b);s*=16;}
for(;a--;t=_(t,t,1));return t}
/*
Calculate a±b. (+ when s=1, - when s=0) When calculating minus, assume that 1>b>a>0.
*/
function _(a,b,s){
for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;
r=(s?function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c):
function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r;
}
/*
Using BBP formula. Calc when j=0...
4/1 - 2/4 - 1/5 - 1/6 = 3.22222222.... (b16)
*/
for(i=0;i<l;i++,p+='2');
//Calc when j>0
for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++);
console.log(p.slice(1024,2048));


EDIT : Removed totally unused function. (Why did I keep that? :/ )

PS. First 100 digits of PI

243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89452821e638d01377be5466cf34e90c6cc0ab

• @FUZxxl : Was the non-golfed code not enough? ..:( – JiminP Jul 7 '11 at 17:29
• It was indeed. But IMHO it looks better, if you use the code formatting instead of using the backtick syntax. As I wrote, feel free to revert if you dislike. – FUZxxl Jul 7 '11 at 17:36
• d='0123456789abcdef',l=3e3,p=Array(l+1).join(2),o='',c=0,e='length';d+=d;function _(a,b,s){for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i+1;r=d[Z=F(b,i,1)+c,k=F(a,i,1)+(s?Z:16-Z),c=s?k>15:k<16,k]+r,i--);return r}function F(a,b,f){if(f)f=a[e]>b?d.indexOf(a[b]):0;else{for(i=0,f='',s=16;i++<l;f+=d[~~(s/b)],s=(s%b)*16);while(a--)f=_(f,f,1)}return f}for(j=0;++j<l;p=_(p,(o+='0')+_(_(_(F(2,z=8*j+1),F(1,z+3)),F(0,z+4)),F(0,z+5)),1));console.log(p.slice(1024,2048)) – Peter Taylor May 14 '12 at 15:03
• That's really all micro-optimisations, although some of them look quite large. The biggest saving comes from eliminating the two anonymous functions in the middle of _ in favour of the , operator. The trickiest one is the merging of $ and g into one function, with an optional argument to select between them. function and return are both quite expensive, so an if(f)...else and a couple of ,1 is a reasonable tradeoff. – Peter Taylor May 14 '12 at 15:09 ## PHP 116 114 bytes <?for(;$g?$d=0|($$g=g--/2*d+($$g?:2)%$g*$f)/$g--:4613^printf($i++>257?'%04x':'',$e+$d/$f=4*$g=16384)^$e=$d%$f;);


This solution calculates all of pi up to 2048 hex digits, four hex digits at a time, and outputs the last half of them. Execution time is less than 5 seconds. The formula used for the calculation is the following:

pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + 6/13*(2 + 7/15*(2 + ... )))))))


The precision is obtained storing the remainders in an array, and continuing each of the 2^14 divisions incrementally.

## Python 64 bytes

x=p=16385
while~-p:x=p/2*x/p+2*2**8192;p-=2
print('%x'%x)[1025:]


Same method as above. Runs in about 0.2s.

Or as a one-liner in 73 bytes:

print('%x'%reduce(lambda x,p:p/2*x/p+2*2**8192,range(16387,1,-2)))[1025:]


## PARI/GP-2.4, 141

forstep(d=1024,2047,8,y=frac(apply(x->sum(k=0,d+30,16^(d-k)/(8*k+x)),[1,4,5,6])*[4,-2,-1,-1]~);for(i=0,7,y=16*frac(y);printf("%X",floor(y))))


Using the Bailey–Borwein–Plouffe formula (of course).

Runs in well under a minute.

C code:

long ki,k,e,d=1024;
int  dig,tD=0,c,Co=0,j,js  ={1,4,5,6};
double res=0.0,tres=0.0,gT,ans ={0.0};
while(tD < 1024)
{while(Co<4){ j= js[Co],gT=0.0,ki= 0;
for(; ki < d+1;ki++){ k = 8*ki+j,e= d-ki,c=1; while(e--) c = 16*c % k; gT+=((double)(c)/(double)k);}
ans[Co] = (gT - (int)gT),++Co;}
double gA = 4*ans-2*ans-ans-ans;
gA = (gA<0) ? gA + -1*(int)gA +1 : gA -(int)gA;
dig=0;while(dig++ < 6 && tD++ < 1024) gA *=16, printf("%X",gA),gA -= (int)gA;
d+=6,Co = 0;}


runtime = 8.06 seconds on a intel Quad core

• This is code golf. Try to compress your code as much as possible by using short variable names and avoiding whitespace. For instance, you could save a lot of chars by using printf("%X",(int)gA) instead of that long list. – FUZxxl Jun 30 '11 at 17:13

## PARI/GP - 40 bytes

This version 'cheats' by using \x to display the hexadecimal digits of the result.

\p8197
x=Pi<<4^6;x-=x\1;x=(x<<4^6)\1
\xx


This version takes 87 bytes to convert to hexadecimal in the usual way.

\p8197
x=Pi<<4^6;x-=x\1;concat([Vec("0123456789abcdef")[n+1]|n<-digits((x<<4^6)\1,16)])


Both versions run in a small fraction of a second.

# Perl - 59

use ntheory"Pi";say substr int(Pi(3000)<<8192)->as_hex,1027


Less than 0.1s.

## Shell 68

### tools: bc -l, tr, cut

echo "scale=2468;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|cut -c1027-2051


### Shell 64, tools: bc -l, tr, tail, differs in the rounding of the last place

echo "scale=2466;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|tail -c1024


Might be considered cheating, since the knowledge how to compute PI is in 4*a(1), and that 1 have to use scale=2466 was iteratively investigated.

Thanks to breadbox for the idea to use cut.

• I don't see how it could be considered cheating; the digits are computed at runtime. Although I should note that when I run it, it output differs on the last digit (7 instead of A). BTW, I think you can replace the dd command with tail -c1024 to save a few chars. – breadbox May 12 '12 at 22:17
• Yes, I observed the difference too (and spend half an hour on it :) ). If I tell bc to use a scale of x digits, it rounds to that digit in decimal mode, and does hex conversion afterwards. So if I take one more digit, it produces a 69, not a 7. However - rounding style or truncation wasn't specified in the question. And thanks for the tail idea. :) – user unknown May 12 '12 at 22:28
• The question specifies: terminate and produce an output identically to what is specified. – FUZxxl May 13 '12 at 10:59
• @FUZxxl: "should...", not "must..." - I thought it should be a help to check, whether the hex conversion is doing well, and the count of characters to skip, not as part of the specification, to conform to the last digit of 1024. But I gave in and added 16 chars to replace one. – user unknown May 13 '12 at 11:19
• Given that the sentence starts with the word "Formally", I would agree that the OP probably meant it in the RFC sense of the word. Also, you can still improve your new solution by replacing the use of dd with cut -c1027-2051. (The shell has many tools for manipulating text streams.) – breadbox May 13 '12 at 18:31