Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This is a somewhat different task. Calculate1024 hexadecimal digits of pi, 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.

share|improve this question
    
Hah, should be easy. (+1, still) I bet I can make it execute in less than a few seconds. –  muntoo 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. –  muntoo 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
add comment

8 Answers 8

up vote 11 down vote accepted

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:]
share|improve this answer
    
Definitly not cheating. –  FUZxxl Jul 8 '11 at 18:43
7  
Mmmm, floor pi. –  breadbox May 12 '12 at 18:50
add comment

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)
share|improve this answer
    
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 at 18:39
add comment

J, 156, 140, 137 127

d=:3 :'1|+/4 _2 _1 _1*+/(y&(16^-)%1 4 5 6+8*])"0 i.y+9'
,1([:}.'0123456789abcdef'{~[:|.[:<.[:(],~16*1|{.)^:8 d)"0\1024x+8*i.128

Using BBP formula.

Does NOT run in under a minute (but we have a J answer :p)

Example for the first 104 digits of π (this runs fast):

,1([:}.'0123456789abcdef'{~[:|.[:<.[:(],~16*1|{.)^:8 d)"0\8*i.13x

243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89
452821e638d01377be5466cf34e90c6cc0ac29b7
share|improve this answer
    
Why don't you use #: to convert the numbers to hexadecimal? –  FUZxxl Dec 5 '11 at 20:48
    
I'm not sure what you mean. #: will not output hex digits. –  Eelvex Dec 5 '11 at 21:16
    
IMHO it's easier to use #: and a reshape to generate hex-digits than your current approach. –  FUZxxl Dec 5 '11 at 21:31
    
You mean something like (... 16 #:) Pi? I think we don't have enough digits so we have to generate them anyway. –  Eelvex Dec 5 '11 at 21:48
1  
BTW, I found out that there is the verb hfd to convert numbers to hexadecimal. –  FUZxxl Dec 6 '11 at 13:52
show 3 more comments

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

share|improve this answer
    
I edited your answer for legibility. Please accept my edit if you like it. –  FUZxxl Jul 7 '11 at 16:19
    
@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;functi‌​on _(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
add comment

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:]
share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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