16
\$\begingroup\$

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:

25d479d8f6e8def7e3fe501ab6794c3b976ce0bd04c006bac1a94fb6409f60c45e5c9ec2196a246368fb6faf3e6c53b51339b2eb3b52ec6f6dfc511f9b30952ccc814544af5ebd09bee3d004de334afd660f2807192e4bb3c0cba85745c8740fd20b5f39b9d3fbdb5579c0bd1a60320ad6a100c6402c7279679f25fefb1fa3cc8ea5e9f8db3222f83c7516dffd616b152f501ec8ad0552ab323db5fafd23876053317b483e00df829e5c57bbca6f8ca01a87562edf1769dbd542a8f6287effc3ac6732c68c4f5573695b27b0bbca58c8e1ffa35db8f011a010fa3d98fd2183b84afcb56c2dd1d35b9a53e479b6f84565d28e49bc4bfb9790e1ddf2daa4cb7e3362fb1341cee4c6e8ef20cada36774c01d07e9efe2bf11fb495dbda4dae909198eaad8e716b93d5a0d08ed1d0afc725e08e3c5b2f8e7594b78ff6e2fbf2122b648888b812900df01c4fad5ea0688fc31cd1cff191b3a8c1ad2f2f2218be0e1777ea752dfe8b021fa1e5a0cc0fb56f74e818acf3d6ce89e299b4a84fe0fd13e0b77cc43b81d2ada8d9165fa2668095770593cc7314211a1477e6ad206577b5fa86c75442f5fb9d35cfebcdaf0c7b3e89a0d6411bd3ae1e7e4900250e2d2071b35e226800bb57b8e0af2464369bf009b91e5563911d59dfa6aa78c14389d95a537f207d5ba202e5b9c5832603766295cfa911c819684e734a41b3472dca7b14a94a

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.

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

9 Answers 9

Reset to default
13
\$\begingroup\$

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:]
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Definitly not cheating. \$\endgroup\$
    – FUZxxl
    Commented Jul 8, 2011 at 18:43
  • 11
    \$\begingroup\$ Mmmm, floor pi. \$\endgroup\$
    – breadbox
    Commented May 12, 2012 at 18:50
13
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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 ;) \$\endgroup\$
    – FUZxxl
    Commented Jun 30, 2011 at 17:14
  • \$\begingroup\$ Golfed version: curl -sL ow.ly/shKGY|grep -Po \\w{99,} (37). Works in Dash. Bash would need an additional byte. \$\endgroup\$
    – Dennis
    Commented Jan 5, 2014 at 18:39
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ @FUZxxl : Was the non-golfed code not enough? ..:( \$\endgroup\$
    – JiminP
    Commented Jul 7, 2011 at 17:29
  • \$\begingroup\$ 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. \$\endgroup\$
    – FUZxxl
    Commented Jul 7, 2011 at 17:36
  • \$\begingroup\$ 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)) \$\endgroup\$
    – Peter Taylor
    Commented May 14, 2012 at 15:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – Peter Taylor
    Commented May 14, 2012 at 15:09
4
\$\begingroup\$

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:]
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C code: 

long ki,k,e,d=1024;
int  dig,tD=0,c,Co=0,j,js[4]  ={1,4,5,6};
double res=0.0,tres=0.0,gT,ans[4] ={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[0]-2*ans[1]-ans[2]-ans[3];
 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

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – FUZxxl
    Commented Jun 30, 2011 at 17:13
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl - 59

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

Less than 0.1s.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$
    – breadbox
    Commented May 12, 2012 at 22:17
  • \$\begingroup\$ 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. :) \$\endgroup\$
    – user unknown
    Commented May 12, 2012 at 22:28
  • \$\begingroup\$ The question specifies: terminate and produce an output identically to what is specified. \$\endgroup\$
    – FUZxxl
    Commented May 13, 2012 at 10:59
  • \$\begingroup\$ @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. \$\endgroup\$
    – user unknown
    Commented May 13, 2012 at 11:19
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – breadbox
    Commented May 13, 2012 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.