code-golf - Code Golf: Pi のライプニッツ公式

Question

私は最近、ライプニッツの公式を使用して Pi を計算する関数を作成することである、" What's you more物議を醸しているプログラミングの意見"に私のお気に入りのインタビューホワイトボードコーディングの質問の 1 つを投稿しました。

さまざまな方法でアプローチでき、終了条件は少し考えなければならないので、興味深いコードゴルフの質問になるのではないかと思いました。最短コードが勝つ！

関数 4 * (1 - 1/3 + 1/5 - 1/7 + ...) を使用して Pi を推定できることを考えると、項が多いほど精度が高くなり、Pi を 0.00001 以内で計算する関数を作成します。

編集: 2008 年 1 月 3 日

コメントで示唆されているように、私は終了条件を 0.00001 以内に変更しました。それが私が本当に意味したことです (小数点以下 5 桁の精度は丸めのためにはるかに難しいため、インタビューでそれを尋ねたくはありませんが、0.00001 以内は終了条件の理解と実装が容易になります)。

また、コメントに答えるために、私の意図は、ソリューションが反復回数を計算するか、十分に完了したかを確認することだったと思いますが、反復回数を事前に計算してその数を使用することを妨げるものは何もありません。人々が何を思いつくかを見るために、私は本当に興味を持って質問をしました。

score 61 · Accepted Answer

J、14文字

4*-/%>:+:i.1e6

説明

1e61の後に6つのゼロ（1000000）が続きます。
i.y最初のy非負の数を生成します。
+:list引数の各要素を2倍にする関数です。
>:list引数の各要素を1つずつインクリメントする関数です。

したがって、式>:+:i.1e6は最初の100万個の奇数を生成します。

1 3 57..。

%は逆数演算子です（分子「1」は省略できます）。
-/list引数の各要素の代替合計を実行します。

したがって、この式-/%>:+:i.1e6は、最初の100万個の奇数の逆数の交互の合計を生成します。

1-1/3 + 1/5-1/7+..。

4*4の掛け算です。前の合計の4を掛けると、πになります。

それでおしまい！Jは数学のための強力な言語です。

編集：9を生成してから！（362880）代替合計の項は、小数点以下5桁の精度を得るのに十分であり、ライプニッツの公式は次のようにも記述できるため、次のようになります。

4-4/3 + 4/5-4/7+..。

...プログラムのより短い12文字バージョンを書くことができます：

-/4%>:+:i.9!

score 36 · Accepted Answer

言語：Brainfuck、文字数：51/59

これは重要ですか？=]

Brainfuckには浮動小数点数がないため、除算を適切に機能させることはかなり困難でした。Grr。

改行なし（51）：

+++++++[>+++++++<-]>++.-----.+++.+++.---.++++.++++.

改行（59）の場合：

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.

score 24 · Accepted Answer

パール

26文字

26 は関数のみ、27 は計算、31 は出力です。コメントからこの回答へ。

sub _{$-++<1e6&&4/$-++-&_}       # just the sub
sub _{$-++<1e6&&4/$-++-&_}_      # compute
sub _{$-++<1e6&&4/$-++-&_}say _  # print

28文字

28 は計算するだけで、34 は印刷するだけです。コメントから。このバージョンでは「say」を使用できないことに注意してください。

$.=.5;$\=2/$.++-$\for 1..1e6        # no print
$.=.5;$\=2/$.++-$\for$...1e6;print  # do print, with bonus obfuscation

36文字

36 は計算するだけで、42 は印刷するだけです。コメントからのハドソンのドリーブスの再配置に対する見解。

$/++;$\+=8/$//($/+2),$/+=4for$/..1e6
$/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print

反復回数について: 私の数学の記憶に関する限り、0.00001 まで正確であるには 400000 で十分です。しかし、100 万 (または 8e5 と同じくらい低い) では、実際には 10 進展開が実際には 5 つの小数桁に一致し、同じ文字数なので、それを維持しました。

score 23 · Accepted Answer

23

ルビー、33文字

(0..1e6).inject{|a,b|2/(0.5-b)-a}

于 2009-01-03T03:20:46.213 に答える

score 20 · Accepted Answer

別の C# バージョン:

(60文字)

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159

score 14 · Accepted Answer

Pythonで 52 文字:

print 4*sum(((-1.)**i/(2*i+1)for i in xrange(5**8)))

(51 xrange から 'x' を削除します。)

Octave (または Matlab) で 36 文字:

l=0:5^8;disp((-1).^l*(4./(2.*l+1))')

(「format long;」を実行して、すべての有効数字を表示します。) 「disp」を省略すると、30 文字に達します。

octave:5> l=0:5^8;(-1).^l*(4./(2.*l+1))'
ans = 3.14159009359631

score 13 · Accepted Answer

13

Oracle SQL 73 文字

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6

于 2009-01-03T14:52:29.330 に答える

score 10 · Accepted Answer

言語: C、文字数: 71

float p;main(i){for(i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

言語: C99、文字数: 97 (必要な改行を含む)

#include <stdio.h>
float p;int main(){for(int i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

上記のバージョン (同じもの) は、余分な反復が結果に影響を与えるかどうかを追跡していることに注意してください。したがって、最小数の操作を実行します。さらに数字を追加するには1E6、1E(num_digits+1)または4E5に置き換えます4E(num_digits)(バージョンによって異なります)。完全なプログラムの%g場合、交換が必要になる場合があります。 floatに変更する必要がある場合もありdoubleます。

言語: C、文字数: 67 (注を参照)

double p,i=1;main(){for(;i<1E6;i+=4)p+=8/i/(i+2);printf("%g\n",p);}

このバージョンは、他のいくつかの回答で使用されているように、投稿されたアルゴリズムの修正バージョンを使用しています。また、反復が無意味になるタイミングを検出する代わりに、100 000 回の反復を強制するため、最初の 2 つのソリューションほどクリーン/効率的ではありません。

言語: C、文字数: 24 (チート)

main(){puts("3.14159");}

ただし、桁数 > 6 では機能しません。

score 10 · Accepted Answer

ハスケル

私はそれを34文字に減らしました：

foldl subtract 4$map(4/)[3,5..9^6]

この式を評価すると、3.141596416935556 が得られます。

編集: ここでは、foldl の代わりに foldl1 を使用するやや短いバージョン (33 文字) を示します。

foldl1 subtract$map(4/)[1,3..9^6]

編集 2: 10^6 ではなく 9^6。経済的でなければなりません;）

編集 3: 編集 2 の結果として、foldl' と foldl1' がそれぞれ foldl と foldl1 に置き換えられ、オーバーフローしなくなりました。これに気づいてくれた ShreevatsaR に感謝します。

score 10 · Accepted Answer

10

MATLAB では 23 文字:

a=1e6;sum(4./(1-a:4:a))

于 2009-01-22T19:47:57.427 に答える

score 9 · Accepted Answer

F# :

試み #1:

let pi = 3.14159

浮気？いいえ、そのスタイルで勝ちます!

試み #2:


let pi =
    seq { 0 .. 100 }
    |> Seq.map (fun x -> float x)
    |> Seq.fold (fun x y -> x + (Math.Pow(-1.0, y)/(2.0 * y + 1.0))) 0.0
    |> (fun x -> x * 4.0)

可能な限りコンパクトではありませんが、かなり慣用的な F# です。

score 7 · Accepted Answer

7

Common lisp、55文字。

(loop for i from 1 upto 4e5 by 4 sum (/ 8d0 i (+ i 2)))

于 2009-01-05T03:53:43.917 に答える

score 6 · Accepted Answer

Mathematica、27文字（おそらく26文字から33文字まで）

NSum[8/i/(i+2),{i,1,9^9,4}]

最初の「N」を削除すると、答えが（巨大な）分数として返されます。

Mathematicaが結果を出力するためにprintステートメントを必要としないのがごまかしている場合は、「Print@」の前に合計33文字を追加します。

注意：

用語の数をハードコーディングするのが不正だとしたら、まだこれを正しく理解している答えはないと思います。現在の用語があるしきい値を下回っている場合にチェックすることは、用語の数をハードコーディングすることよりも優れています。現在の用語が6桁目または7桁目を変更しているだけだからといって、後続の十分な用語の合計が5桁目を変更しないという意味ではありません。

score 5 · Accepted Answer

交代級数の誤差項の式を使用する（したがって、目的の精度を達成するために必要な反復回数は、プログラムにハードコーディングされていません）。

public static void Main(string[] args) {
    double tolerance = 0.000001;
    double piApproximation = LeibnizPi(tolerance);
    Console.WriteLine(piApproximation);
}

private static double LeibnizPi(double tolerance) {
    double quarterPiApproximation = 0;

    int index = 1;
    double term;
    int sign = 1;
    do {
        term = 1.0 / (2 * index - 1);
        quarterPiApproximation += ((double)sign) * term;
        index++;
        sign = -sign;
    } while (term > tolerance);

    return 4 * quarterPiApproximation;
}

score 4 · Accepted Answer

C#:

public static double Pi()
{
    double pi = 0;
    double sign = 1;
    for (int i = 1; i < 500002; i += 2)
    {
        pi += sign / i;
        sign = -sign;
    }
    return 4 * pi;
}

score 4 · Accepted Answer

Ruby、41 文字 (irb を使用):

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};s

または、この少し長い非 irb バージョン:

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};p s

これは修正されたライプニッツです:

用語のペアを結合します。これにより、2/3 + 2/35 + 2/99 + ... が得られます。
円周率は 8 * (1/(1 * 3) + 1/(5 * 7) + 1/(9 * 11) + ...) になります。

score 4 · Accepted Answer

F# (インタラクティブモード) (59 文字)

{0.0..1E6}|>Seq.fold(fun a x->a+ -1.**x/(2.*x+1.))0.|>(*)4.

(警告を生成しますが、キャストを省略します)

score 4 · Accepted Answer

4

パール:

$i+=($_&1?4:-4)/($_*2-1)for 1..1e6;print$i

合計 42 文字。

于 2009-01-02T18:30:27.080 に答える

score 3 · Accepted Answer

Javascript：

a=0,b=-1,d=-4,c=1e6;while(c--)a+=(d=-d)/(b+=2)

javascriptで。51文字。明らかに勝つつもりはありませんが、ええ。：P

編集-Stragerのおかげで、46文字に更新されました。:)

更新 （2010年3月30日）

David Murdochによるより高速な（小数点以下5桁までの正確さ）43文字バージョン

for(a=0,b=1,d=4,c=~4e5;++c;d=-d)a-=d/(b-=2)

score 3 · Accepted Answer

記録のために、このスキームの実装には、不要な空白を無視して 95 文字があります。

(define (f)
  (define (p a b)
    (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (p (+ a 4) b))))
  (* 8 (p 1 1e6)))

score 3 · Accepted Answer

これがMUMPSのソリューションです。

pi(N)
 N X,I
 S X=1 F I=3:4:N-2 S X=X-(1/I)+(1/(I+2))
 Q 4*X

パラメータ N は、使用する反復分数の数を示します。つまり、5 を渡すと、4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11) と評価されます。

いくつかの実験的テストでは、N=272241 が最小値であり、小数点以下 5 桁に切り捨てられた場合に正しい値 3.14159 が得られることが示されました。3.14159 に丸められる値を取得するには、N=852365 に移動する必要があります。

score 3 · Accepted Answer

イテレータブロックを使用する C#:

static IEnumerable<double> Pi()
{
    double i = 4, j = 1, k = 4;
    for (;;)
    {
        yield return k;
        k += (i *= -1) / (j += 2);
    }
}

score 2 · Accepted Answer

現在の回答のほとんどは、いくつかの反復回数で5桁の精度が得られることを前提としており、この数値はプログラムにハードコードされています。質問についての私の理解は、プログラム自体が、5桁の正確な答えが得られたときにそれを理解し、そこで停止することになっているということでした。その仮定に基づいて、これが私のC＃ソリューションです。すでに出回っている答えのいくつかと競合する方法がないので、文字数を最小限に抑えることを気にしなかったので、代わりに読みやすくしたいと思いました。:)

    private static double GetPi()
    {
        double acc = 1, sign = -1, lastCheck = 0;

        for (double div = 3; ; div += 2, sign *= -1)
        {
            acc += sign / div;

            double currPi = acc * 4;
            double currCheck = Math.Round(currPi, 5);

            if (currCheck == lastCheck)
                return currPi;

            lastCheck = currCheck;
        }
    }

score 2 · Accepted Answer

C# を使用した再帰的な回答を次に示します。これはリリースモードで x64 JIT を使用する場合にのみ機能します。これは、テールコールの最適化を適用する唯一の JIT であり、シリーズの収束が非常に遅いため、x64 JITStackOverflowExceptionなしで発生するためです。

関数を無名ラムダとして持つのはいいことですが、IteratePi自己再帰的であるため、Y コンビネータであらゆる種類の恐ろしいことを開始する必要があるため、別の関数として残しました。

public static double CalculatePi()
{
    return IteratePi(0.0, 1.0, true);
}

private static double IteratePi(double result, double denom, bool add)
{
    var term = 4.0 / denom;
    if (term < 0.00001) return result;    
    var next = add ? result + term : result - term;
    return IteratePi(next, denom + 2.0, !add);
}

score 2 · Accepted Answer

2

言語: DC、文字数: 35

dc -e '9k0 1[d4r/r2+sar-lad274899>b]dsbxrp'

于 2009-01-02T21:49:37.677 に答える

score 2 · Accepted Answer

言語: C99 (暗黙のリターン 0)、文字数: 99 (95 + 必要なスペース 4 つ)

終了条件は、固定カウントではなく、現在の値に依存します

#include <stdio.h>

float p, s=4, d=1;
int main(void) {
  for (; 4/d > 1E-5; d += 2)
        p -= (s = -s) / d;
  printf("%g\n", p);
}

圧縮版

#include<stdio.h>
float
p,s=4,d=1;int
main(void){for(;4/d>1E-5;d+=2)p-=(s=-s)/d;printf("%g\n",p);}

score 1 · Accepted Answer

#!/usr/bin/env python
from math import *
denom = 1.0
imm = 0.0
sgn = 1
it = 0
for i in xrange(0, int(1e6)):
    imm += (sgn*1/denom)
    denom += 2
    sgn *= -1    
print str(4*imm)

score 1 · Accepted Answer

1

Java

    double pi=0,s=-1,i=1;
    for (;i<1E6;i+=2)pi+=((1d/i)*(s=-s)); 
    pi*=4;

于 2010-09-14T16:51:59.767 に答える

score 1 · Accepted Answer

C＃の不正行為-50文字：

static single Pi(){
  return Math.Round(Math.PI, 5));
}

それは「式を考慮に入れて関数を書く...」とだけ言っていますが、プログラムで式を再現することは言いません:)箱の外で考えてください...

C＃LINQ-78文字：

static double pi = 4 * Enumerable.Range(0, 1000000)
               .Sum(n => Math.Pow(-1, n) / (2 * n + 1));

C＃代替LINQ-94文字：

static double pi = return 4 * (from n in Enumerable.Range(0, 1000000)
                               select Math.Pow(-1, n) / (2 * n + 1)).Sum();

そして最後に、これは前述のアルゴリズムを採用し、数学的に凝縮するため、符号を変更し続けることを心配する必要はありません。

C＃ロングハンド-89文字（不要なスペースはカウントされません）：

static double pi()
{
  var t = 0D;
  for (int n = 0; n < 1e6; t += Math.Pow(-1, n) / (2 * n + 1), n++) ;
  return 4 * t;
}

score 1 · Accepted Answer

double d = 1;
double s = 1;
double pi = 0;

while(4.0 / d > 0.000001){
    pi += s*4.0/d;
    d+=2;
    s = -s;        
}
printf("%f\n", pi);

score 1 · Accepted Answer

ルビー:

irb(main):031:0> 4*(1..10000).inject {|s,x| s+(-1)**(x+1)*1.0/(2*x-1)}
=> 3.14149265359003

score 1 · Accepted Answer

1

AWK で 64 文字:

~# awk 'BEGIN {p=1;for(i=3;i<10^6;i+=4){p=p-1/i+1/(i+2)}print p*4}'
3.14159

于 2009-01-03T14:02:16.340 に答える

score 1 · Accepted Answer

C++

double LeibnizPi( double tolerance )
{
    double sum = 1.0;
    for( int plus_div = 5, minus_div = -3, limit = 10 / tolerance; plus_div < limit ; plus_div += 4, minus_div -= 4 )
        sum += 1./plus_div + 1./minus_div;
    return 4 * sum;
}

score 1 · Accepted Answer

と注意した上で

(= (- (/ 4 n)
      (/ 4 (+ n 2)))
   (/8n(+n2)))

または、より使い慣れた表記法で:

4 4 8
------ = ------
n n+2 n(n+2)

Common Lisp、do*ループあり (62 の必須文字):

(do* ((n 1 (+ n 4))
      (p 8/3 (+ p (/ 8 n (+ n 2)))))
     ((< (- pi p) 1e-6)
      p)

末尾の再帰関数 (70 の必須文字) を使用:

(defun l (n p)
  (if (< (- pi p) 1e-6)
      p
      (l (+ n 4)
          (+ p (/ 8 n (+ n 2))))))
(l 1 0)

拡張ループ (86 個の必須文字) を使用すると、次のようになります。

(loop for n from 1 by 4
      sum (/ 8 n (+ n 2)) into p
      until (< (- pi p) 1e-6)
      finally (return p))

必要な精度を得るためにどこまで行かなければならないかを予備的にチェックすることは、ごまかしているという仮定の下ですべてです。

score 0 · Accepted Answer

0

ルア、46文字

p=4 for i=3,9^6,4 do p=p-8/i/(i+2)end print(p)

于 2010-02-16T17:47:31.780 に答える

score 0 · Accepted Answer

VB 117 文字:

Function Pi()
  Dim t = 0D
  For n = 0 To 1000000
    t += Math.Pow(-1, n) / (2 * n + 1)
  Next
  Return 4 * t
End Function

VB LINQ 115 文字 (不要な行の継続を省略) :

Function Pi()
  Return 4 * Enumerable.Range(0, 1000000) _
             .Sum(Function(n) Math.Pow(-1, n) / (2 * n + 1))
End Function

そして、次のように呼び出します。

Sub Main()
  Console.WriteLine("{0:n5}", Pi)
End Sub

score 0 · Accepted Answer

これがC++での私のもので、おそらくそれを行う最も長い方法です:P

double pi(){
   bool add = true;
   double rPi = 0;
   for(long i = 1; i < 99999999; i=i+2)
   {
            double y = (double) i;
            double x = (double) 1;
            if(add)
            {
                   rPi = rPi + (x/y);
                   add = false;
            }
            else
            {
                    rPi = rPi - (x/y);
                    add = true;
            }
   }
            return (rPi * (double) 4);
   }

score 0 · Accepted Answer

ええと....数値処理の一般的なルールとして、精度の損失による問題を回避するために、最小の項から最大の項に向かって系列を合計する必要があります。だから

fortran77

省略 (248 文字)

      function pi(n)
      pi=0.
      t=10**(-n-0.5)
      i=int(4/t)
      i=i/2
      s=-1.                     
      do 1 j=i*2+1,1,-2
         pi = pi + s/j
         s=-s
 1    continue
      pi=abs(pi)*4              
      return
      end

足場とコメント付き（600文字）

      program leibnitz

      n=5
      p=int(pi(n)*10.**n)/10.**n
      write(6,*)p 

      stop
      end

c     Returns pi computed to <n> digits by the leibniz formula
      function pi(n)
      pi=0.
c     find the smallest term we need by insuring that it is too small to
c     effect the interesting digits.
      t=10**(-n-0.5)
      i=int(4/t)
      i=i/2
      s=-1.                     ! sign of term, might be off by one, but
      do 1 j=i*2+1,1,-2
         pi = pi + s/j
         s=-s
 1    continue
      pi=abs(pi)*4              ! we fix the sign problem here
      return
      end

出力：

   3.1415901

の精度がなくなる6桁までの任意の桁数でreal動作するようです。速度や操作の最小数のために最適化されていません。

score 0 · Accepted Answer

物議を醸す意見に関するトピックのインタビューの質問を読んだ直後に、私はこれを書いた. きれいではありませんが、約 3 ～ 4 分かかりました。各ループで精度を確認しています。C++. 私は明日目を覚まして、吸わない解決策を投稿します:)

double get_pi(int acc)
{

  double pi;
  double dynamicpart;
  int operationCoeff = 1;
  int denom = 3;
  while(1)
  { 
      dynamicpart =
         1/denom + operationCoeff*(denom+2);
      pi = 4*(1-dynamicpart);
      if(!(pi*acc*10-(int)pi*acc*10)) break;
)
      denom+=2;
      operationCoeff = -operationCoeff;
  }



}

score 0 · Accepted Answer

0

R - 27 文字

sum(4/seq(1,1e6,2)*c(1,-1))

于 2011-01-18T19:41:47.663 に答える

score 0 · Accepted Answer

PHP、99 文字

$output =

${!${''}=function(){$pi=1;for($i=0;$i<pow(10,6);$i++){$pi+=($i%2?1:-1)/(3+$i*2);}return $pi*4;}}();

var_dump($output);

この答えを減らすために私が知らないいくつかのかなりのトリックがあると思います! この投稿から1行の出力トリックを取りました。

score 0 · Accepted Answer

Python 3 (40 バイト)

sum(8/(n*(n+2))for n in range(1,5**8,4))

このバージョンは、 @Svante の回答からの最適化を使用します。

+7 バイトを出力

print(sum(8/(n*(n+2))for n in range(1,5**8,4)))

Python 2.x +1 バイト

sum(8./(n*(n+2))for n in range(1,5**8,4))

+6 バイトを出力

print sum(8./(n*(n+2))for n in range(1,5**8,4))

http://codepad.org/amtxUxKp

score 0 · Accepted Answer

Erlang、最大 126 文字:

-module (pi).
-export ([pi/0]).

pi() -> 4 * pi(0,1,1).
pi(T,M,D) ->
    A = 1 / D,
    if A > 0.00001 
              -> pi(T+(M*A), M*-1, D+2);
        true  -> T
    end.

score 0 · Accepted Answer

かなりクールな集計構文を使用した別の VB ソリューション:

Public ReadOnly Pi As Double = 4 * Aggregate i In Enumerable.Range(0, 100000) _
                                   Select (-1) ^ i / (i * 2 + 1) Into Sum()

式のみ: 不要な空白を含まない 74 文字。

score 0 · Accepted Answer

ジャワ

void pi(){
    double x=1,y=1,d=1;
    for(;x<1E6;) { y=-y;d+=y/((2*x++)+1); }
    System.out.println(d*4);
}