7
\$\begingroup\$

This question already has an answer here:

Task

Given an input n, calculate the n-th decimal digit of pi

Rules

  • Answer can be a full program or a function.
  • Input must be taken from stdin or from function arguments.
  • Output must be either sent to stdout, the return value of a function, or written to a file.
  • all n values between 0 and 20000 must be supported (can be between 1 and 20001 for 1-indexed languages).
  • Built-ins to calculate pi cannot be used. This includes pi constants (e.g. math.pi in Python) and built-in functions that return either the value of pi, or the n-th digit of pi. This means that an algorithm which calculates pi, or the n-th digit of pi must be implemented in your answer.
  • Digits must be calculated at runtime.

First digit (0-th or 1-th, depending on the language) is 3.

This is code-golf, so shortest code in bytes wins.

EDIT:

This is not a duplicate of 'Find the n-th decimal of pi', since that challenge allowed built-ins. This one is focused around actually implementing an algorithm to find the digits, rather than relying on built-ins.

\$\endgroup\$

marked as duplicate by Peter Taylor code-golf Oct 28 '16 at 20:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ The ban of built ins probably makes this different enough. \$\endgroup\$ – Jonathan Allan Oct 25 '16 at 11:34
  • 6
    \$\begingroup\$ linking for the sake of completeness. In my opinion it's a dupe, because a lot of those answers can be copy pasted to this challenge. But not voting to close just yet. \$\endgroup\$ – Bassdrop Cumberwubwubwub Oct 25 '16 at 12:21
  • \$\begingroup\$ base16 allowed? \$\endgroup\$ – dwana Oct 25 '16 at 12:31
  • 1
    \$\begingroup\$ This is a completely different challenge without the use of builtins. From what I can see all of the answers to the other question are using builtins and don't apply here. \$\endgroup\$ – cleblanc Oct 25 '16 at 14:11
  • 2
    \$\begingroup\$ @cleblanc, it seems to me that five of the (undeleted) answers to the other question use series expansions such as the Leibniz series, and one uses an built-in for arctan which isn't technically in violation of the spec of this question. That makes 6 out of 13 answers which could be copied across unmodified. \$\endgroup\$ – Peter Taylor Oct 25 '16 at 15:21
7
\$\begingroup\$

Python 2, 182 65 bytes

a=p=2*10**20004
i=3
while a:a=i/2*a/i;p+=a;i+=2
print`p`[input()]

repl.it

Uses the Leibniz formula to calculate 20000 correct digits (plus a handful to allow the algorithm to maintain accuracy) then prints the requested digit.


Previous (182):
"The Spigot Algorithm For Pi" of Stanley Rabinowitz and Stan Wagon has the added bonus that it will work for any n when implemented as a generator

p=lambda n,r=3,a=0,b=1,c=1,d=1,e=3,f=3,i=0:i>n and r or p(n,e,*[((2*b+a)*f,b*d,c*f,d+1,(b*(7*d)+2+(a*f))/(c*f),f+2,i),(10*(a-e*c),10*b,c,d,((10*(3*b+a))/c)-10*e,f,i+1)][4*b+a-c<e*c])

repl.it Reaches Python's default recursion limit for the 117th digit.

Here is a non-recursive version for 198 bytes:

def p(n):
 a=i=0;b=c=d=1;e=f=3
 while i<=n:
     r=e
     if 4*b+a-c<e*c:g=10*(a-e*c);e=((10*(3*b+a))/c)-10*e;b*=10;i+=1
     else:g=(2*b+a)*f;h=(b*(7*d)+2+(a*f))/(c*f);b*=d;c*=f;f+=2;d+=1;e=h
     a=g
 print r

repl.it

(first indent space, second indent tab), the digits could, of course, be generated by yielding e at the start of the if clause instead of tracking the last digit with r.

\$\endgroup\$
  • \$\begingroup\$ Nice implementation of that algorithm, but by using a different algorithm it can be more than 110 bytes shorter in Python 2, as shown by the two Python 2 algorithms here. \$\endgroup\$ – Kevin Cruijssen Oct 25 '16 at 12:44
  • \$\begingroup\$ Yeah, I know, am implementing arctan... \$\endgroup\$ – Jonathan Allan Oct 25 '16 at 12:45
  • \$\begingroup\$ link is broken... fascinating implementation. the explanations that i found dont look like that. they use arrays and vectors, which you dont \$\endgroup\$ – don bright Jul 25 '18 at 2:11
  • \$\begingroup\$ @donbright Thanks I have updated the broken link to point to a stable link at jstor.org \$\endgroup\$ – Jonathan Allan Jul 25 '18 at 7:47
1
\$\begingroup\$

Java 7, 260 258 bytes

import java.math.*;int c(int n){BigInteger p,a=p=BigInteger.TEN.pow(20010).multiply(new BigInteger("2"));for(int i=1;a.compareTo(BigInteger.ZERO)>0;p=p.add(a))a=a.multiply(new BigInteger(i+"")).divide(new BigInteger((2*i+++1)+""));return(p+"").charAt(n)-48;}

Copy from my answer here. Java's built-in Math.PI has a precision of 15 decimal points, so I was already forced to use an algorithm for the other challenge anyway..

Used @LeakyNun's Python 2 algorithm.

Ungolfed & test code:

Try it here. (The ideone can't handle the last two test cases, but it works within 2 sec in the Eclipse IDE.)

import java.math.*;
class M{
  static int c(int n){
    BigInteger p, a = p = BigInteger.TEN.pow(20010).multiply(new BigInteger("2"));
    for(int i = 1; a.compareTo(BigInteger.ZERO) > 0; p = p.add(a), i++){
      a = a.multiply(new BigInteger(i+"")).divide(new BigInteger((2 * i++ + 1)+""));
    }
    return (p+"").charAt(n) - 48;
  }

  public static void main(String[] a){
    System.out.print(c(0)+", ");
    System.out.print(c(1)+", ");
    System.out.print(c(2)+", ");
    System.out.print(c(3)+", ");
    System.out.print(c(4)+", ");
    System.out.print(c(11)+", ");
    System.out.print(c(101)+", ");
    System.out.print(c(600)+", ");
    System.out.print(c(761)+", ");
    System.out.print(c(1001)+", ");
    System.out.print(c(10001)+", ");
    System.out.print(c(20001));
  }
}

Output:

3, 1, 4, 1, 5, 8, 8, 2, 4, 3, 5, 2
\$\endgroup\$

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