Pochodzi z http://programmers.blogoverflow.com/2012/08/20-controversial-programming-opinions/

„Biorąc pod uwagę, że Pi można oszacować za pomocą funkcji 4 * (1 - 1/3 + 1/5 - 1/7 +…) z większą liczbą terminów dających większą dokładność, napisz funkcję, która oblicza Pi z dokładnością do 5 miejsc po przecinku. „

• Uwaga: oszacowania należy dokonać poprzez obliczenie sekwencji podanej powyżej.

JavaScript, 46 58 56 45 bajtów

Aktualizacja ES6 : Okazuje się, że po upływie pięciu lat dostępnych jest więcej funkcji.

let f=(i=0,a=0)=>i>1e6?a:f(i+4,a+8/-~i/(i+3))

Ta wersja ( 45 bajtów; tak, letjest wymagana) działa teoretycznie w trybie ścisłym ES6 . W praktyce można go uruchomić w wersji V8 (np. Z węzłem) za pomocą --use-strict --harmony-tailcalls; niestety, funkcja Właściwe ogony nie jest jeszcze powszechnie wdrażana. Jest to jednak określone zachowanie, więc powinno być w porządku.

Jeśli chcemy trzymać się tego, co jest powszechnie implementowane, i nie wymagamy trybu ścisłego, możemy po prostu użyć składni Fat-Arrow ES6 dla funkcji, ale w przeciwnym razie zachować tę samą implementację co wcześniej (sugerowana przez Briana H) za koszt 48 bajtów.

a=>{for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}

Wybór nazwy dla pojedynczego parametru nie naprawdę znaczenia, ale równie dobrze możemy wybrać jedną z nazw, których używamy, aby zminimalizować zanieczyszczenie o zasięgu globalnym.

function(){for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}

Ta wersja jest wyrażeniem funkcyjnym; dodaj dwa znaki (np. „ f”), jeśli chcesz go nazwać. Ta wersja blokuje globals ai i; można temu zapobiec, dodając „ a,i” do listy parametrów.

Wykorzystuje przeformułowaną wersję algorytmu w celu obejścia potrzeby odejmowania.

 1/1 - 1/3  +   1/5 - 1/7   +    1/9 - 1/11  + ...
(3/3 - 1/3) + (7/35 - 5/35) + (11/99 - 9/99) + ...
    2/3     +      2/35     +       2/99     + ...
  2/(1*3)   +    2/(5*7)    +     2/(9*11)   + ...

Oto „zwykła” wersja bez tego dostosowania:

function(){for(a=0,i=1;i<1e6;i+=2)a+=[,4,,-4][i%4]/i;return a}

która osiąga 64 62 znaków.

Dzięki @ardnew za sugestię, aby pozbyć się 4*przed return.

Historia

function(){for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}     // got rid of `i+=4`; restructured
// Old versions below.
function(){for(a=0,i=1;i<1e6;i+=4)a+=8/i/-~-~i;return a}    // got rid of `4*`
function(){for(a=0,i=1;i<1e6;i+=4)a+=2/i/-~-~i;return 4*a}

Python 59 bajtów

print reduce(lambda x,p:p/2*x/p+2*10**999,range(6637,1,-2))

Spowoduje to wydrukowanie 1000 cyfr; nieco więcej niż wymagane 5. Zamiast korzystać z przepisanej iteracji, wykorzystuje to:

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

6637(Mianownik najgłębsza) można formułować jako:

cyfry * 2 * log 2 (10)

To implikuje liniową zbieżność. Każda głębsza iteracja spowoduje wygenerowanie jeszcze jednego binarnego bitu pi .

Jeśli jednak nalegasz na użycietożsamości tan ^-1 , możesz osiągnąć podobną zbieżność, jeśli nie masz nic przeciwko temu, aby poradzić sobie z problemem nieco inaczej. Patrząc na kwoty częściowe:

4.0, 2.66667, 3.46667, 2.89524, 3.33968, 2.97605, 3.28374, ...

oczywiste jest, że każdy termin przeskakuje w obie strony w obie strony punktu konwergencji; seria ma przemienną konwergencję. Ponadto, każdy termin jest bliżej punktu zbieżności niż poprzedni termin; jest absolutnie monotoniczny w odniesieniu do punktu zbieżności. Połączenie tych dwóch właściwości implikuje, że średnia arytmetyczna dowolnych dwóch sąsiednich członów jest bliższa punktu zbieżności niż którykolwiek z nich. Aby lepiej zrozumieć, co mam na myśli, rozważ następujący obraz:

Szereg zewnętrzny jest oryginałem, a szereg wewnętrzny można znaleźć, biorąc średnią każdego z sąsiednich terminów. Niezwykła różnica. Ale naprawdę niezwykłe jest to, że ta nowa seria ma również przemienną zbieżność i jest absolutnie monotonna w stosunku do punktu zbieżności. Oznacza to, że proces ten można stosować w kółko, ad nauseum.

Dobrze. Ale jak?

Niektóre formalne definicje. Niech P ₁ (n), jest brak ^p określenie pierwszej kolejności, p ₂ (n), jest brak ^p termin drugiej kolejności, i podobnie P _k (n) n ^p termin z k ^th sekwencji, jak zdefiniowano powyżej, .

P ₁ = [P ₁ (1), P ₁ (2), P ₁ (3), P ₁ (4), P ₁ (5), ...]

P ₂ = [(P ₁ (1) + P ₁ (2)) / 2, (P ₁ (2) + P ₁ (3)) / 2, (P ₁ (3) + P ₁ (4)) / 2, (P ₁ (4) + P ₁ (5)) / 2, ...]

P ₃ = [(P ₁ (1) + 2P ₁ (2) + P ₁ (3)) / 4, (P ₁ (2) + 2P ₁ (3) + P ₁ (4)) / 4, (P ₁ (3) + 2P ₁ (4) + P ₁ (5)) / 4, ...]

P ₄ = [(P ₁ (1) + 3P ₁ (2) + 3P ₁ (3) + P ₁ (4)) / 8, (P ₁ (2) + 3P ₁ (3) + 3P ₁ (4) + P ₁ (5)) / 8, ...]

Nic dziwnego, że współczynniki te są dokładnie zgodne ze współczynnikami dwumianowymi i mogą być wyrażone jako pojedynczy rząd trójkąta Pascala. Ponieważ arbitralny rząd Trójkąta Pascala jest prosty do obliczenia, można znaleźć dowolną „głęboką” serię, po prostu biorąc pierwsze n częściowych sum, mnożąc każdy przez odpowiedni wyraz w k- ^tym rzędzie Trójkąta Pascala i dzieląc przez 2 ^k-1 .

W ten sposób można osiągnąć pełną 32-bitową precyzję zmiennoprzecinkową (~ 14 miejsc po przecinku) za pomocą zaledwie 36 iteracji, w których to miejscu częściowe sumy nawet nie są zbieżne na drugim miejscu po przecinku. To oczywiście nie jest gra w golfa:

# used for pascal's triangle
t = 36; v = 1.0/(1<<t-1); e = 1
# used for the partial sums of pi
p = 4; d = 3; s = -4.0

x = 0
while t:
  t -= 1
  p += s/d; d += 2; s *= -1
  x += p*v
  v = v*t/e; e += 1

print "%.14f"%x

Jeśli chcesz dowolną precyzję, możesz to osiągnąć z niewielką modyfikacją. Tutaj jeszcze raz obliczając 1000 cyfr:

# used for pascal's triangle
f = t = 3318; v = 1; e = 1
# used for the partial sums of pi
p = 4096*10**999; d = 3; s = -p

x = 0
while t:
  t -= 1
  p += s/d; d += 2; s *= -1
  x += p*v
  v = v*t/e; e += 1

print x>>f+9

Początkowa wartość p zaczyna się o 2 ¹⁰ większa, aby przeciwdziałać efektom s / d dzielenia liczb całkowitych, gdy d staje się większy, powodując, że kilka ostatnich cyfr się nie zbiega. Zauważ tutaj jeszcze raz3318 jest to również:

cyfry * log 2 (10)

Ta sama liczba iteracji co pierwszy algorytm (o połowę, ponieważ t zmniejsza się o 1 zamiast 2 w każdej iteracji). Ponownie oznacza to liniową zbieżność: jeden binarny bit pi na iterację. W obu przypadkach wymagane jest 3318 iteracji, aby obliczyć 1000 cyfr liczby pi , ponieważ jest to nieco lepszy przydział niż 1 milion iteracji w celu obliczenia 5.

Mathematica 42 39 34 33 31 26 32

Podejście Archimedesa 26 znaków

N@#*Sin[180 Degree/#]&

Osiąga to kryterium, gdy dane wejściowe wynoszą 822.

Pytanie: Czy ktoś wie, jak obliczył grzech 180 stopni? Ja nie.

Podejście Leibniza (seria Gregory'ego) 32 znaki

Jest to ta sama funkcja, którą poser podał jako przykład. Kryterium osiąga około pół miliona iteracji.

N@4Sum[(-1)^k/(2k+1),{k,0,10^6}]

Podejście Madhava-Leibniza 37 znaków

Ta odmiana wykorzystuje kilka dodatkowych znaków, ale zbiega się z kryterium tylko w 9 iteracjach!

N@Sqrt@12 Sum[(-1/3)^k/(2k+1),{k,0,9}]

APL (14)

4×-/÷1-⍨2×⍳1e6

Java (67 znaków)

float r(){float p=0,s=4,i=1E6f;while(--i>0)p+=(s=-s)/i--;return p;}

Zauważ, że pozwala to uniknąć utraty znaczenia poprzez dodanie liczb w odpowiedniej kolejności.

Haskell, 32

foldr(\k->(4/(2*k+1)-))0[0..8^7]

GHCi> foldr (\ k -> (4 / (2 * k + 1) -)) 0 [0..8 ^ 7]
3.141593130426724

Liczenie nazwy funkcji to

34

π=foldr(\k->(4/(2*k+1)-))0[0..8^7]

R - 25 znaków

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

C (GCC) (44 znaki)

float p(i){return i<1E6?4./++i-p(++i):0;}

To 41 znaków, ale należy je również skompilować, -O2aby uzyskać optymalizator eliminujący rekurencję ogona. Zależy to również od nieokreślonego zachowania w odniesieniu do kolejności, w jakiej ++są wykonywane; dzięki ugoren za zwrócenie na to uwagi. Testowałem z gcc 4.4.3 pod 64-bitowym Linuksem.

Pamiętaj, że jeśli optymalizator nie zmieni również kolejności sumy, zostanie ona dodana od najmniejszej liczby, aby uniknąć utraty znaczenia.

Jak zadzwonić p().

J, 26 znaków

+ / + / _ 2 ((4 _4) i%)>: +: i.100

Przeniesiono ze 100 elementów sekwencji do 1e6 elementów. Również teraz jest to kod oznaczony i może być kopiowany z przeglądarki do konsoli bez błędów.

+/+/_2((4 _4)&%)\>:+:i.1e6

JavaScript - 33 znaków

p=x=>4*(1-(x&2))/x+(x>1?p(x-2):0)

Zadzwoń ppodając dodatnią liczbę nieparzystą, xa wyliczy Pi z (x-1)/2warunkami.

Rubin - 82 znaki

def f(n,k=n)k>0?(f(n,k-1)+f(n+1,k-1))/2:n<0?0:f(n-1,0)+(-1)**n/(2*n+1.0)end;4*f(9)

Wypróbuj: https://repl.it/LQ8w

W podejściu wykorzystuje się daną serię pośrednio, stosując metodę przyspieszenia numerycznego. Wynikowy wynik to

pi ≈ 3.14159265161

vs.

pi = 3.14159265359

Zaczyna się od

f(n,0) = 1/1 - 1/3 + 1/5 - ... + ((-1)**n)/(2*n+1)

A ponieważ jest to na przemian, możemy przyspieszyć konwergencję za pomocą

f(n,1) = (f(n,0) + f(n+1,0))/2

I wielokrotnie stosuje to:

f(n,k) = (f(n,k-1) + f(n+1,k-1))/2

I dla uproszczenia f(n) = f(n,n).

Rubin - 50 znaków

Jeśli nie masz nic przeciwko bieganiu przez naprawdę długi czas, możesz po prostu użyć

def f(n)n<0?0:f(n-1)+(-1)**n/(2*n+1.0)end;4*f(1e7)

lub

a=0;for k in 0..1e7 do a+=(-1)**k/(2*k+1.0)end;4*a

C, 69 znaków

float p,b;void main(a){b++<9e6?p+=a/b++,main(-a):printf("%f\n",4*p);}

• Uruchom bez parametrów wiersza poleceń (więc ajest inicjowany na 1).
• Musi zostać skompilowany z optymalizacją.
• void mainjest dziwny i niestandardowy, ale sprawia, że ​​wszystko działa. Bez tego rekurencja jest implementowana jako prawdziwe wywołanie, co prowadzi do przepełnienia stosu. Alternatywą jest dodawanie return.
• 4*Można zapisać dwa znaki , jeśli działają z trzema parametrami wiersza poleceń.

Clojure - 79 znaków

(fn [](* 4(apply +(map #(*(Math/pow -1 %1)(/ 1.0(+ 1 %1 %1)))(range 377000)))))

Tworzy to funkcję bez argumentów, która obliczy liczbę zmiennoprzecinkową, która poprawnie przybliża pi do pięciu miejsc po przecinku. Należy zauważyć, że to nie wiąże funkcja nazwę, na przykład pi, tak, że kod musi być albo oceniona na miejscu eval, jak (<code>)i związany z nazwy w tym przypadku roztwór jest

(defn p[](* 4(apply +(map #(*(Math/pow -1 %1)(/ 1.0(+ 1 %1 %1)))(range 377000)))))

dla 82 znaków

O

(defn nth-term-of-pi [n] (* (Math/pow -1 n) (/ 1.0 (+ 1 n n))))
(defn pi [c] (* 4 (apply + (map nth-term-of-pi (range c)))))
(def  pi-accuracy-constant (loop [c 1000] (if (< (pi c) 3.14159) (recur (inc c)) c)))
; (pi pi-accuracy-constant) is then the value of pi to the accuracy of five decimal places

PHP - 56 55 znaków

<?for($j=$i=-1;1e6>$j;){$p+=($i=-$i)/($j+=2);}echo$p*4;

Nie wiem, czy mogę go znacznie zmniejszyć, nie naruszając reguły algorytmu.

Perl - 43 39 znaków

nie jestem pewien zasad dotyczących anonimowych podprogramów, ale oto kolejna implementacja wykorzystująca konstrukcję serii @ FireFly

sub{$s+=8/((4*$_+2)**2-1)for 0..1e6;$s}

sub p{$s+=(-1)**$_*4/(2*$_+1)for 0..1e6;$s}

Java - 92 84 znaków

Zdecydowanie nie mogę pokonać wyniku Petera Taylora, ale oto mój:

double d(){float n=0,k=0,x;while(n<9E5){x=1/(1+2*n++);k+=(n%2==0)?-x:x;}return 4*k;}

Wersja bez golfa:

double d() {
    float n = 0, k = 0, x;
    while (n < 9E5) {
        x = 1 / (1 + 2 * n++);
        k += (n % 2 == 0) ? -x : x;
    }
    return 4 * k;
}

Edycja: Zapisano kilka znaków przy użyciu operatora trójskładnikowego.

Python - 56 znaków

Meh, Moje python-fu nie jest wystarczająco silne. Nie widziałem żadnych skrótów, ale może bardziej doświadczony golfista mógłby znaleźć coś do przycięcia?

t=s=0
k=i=1
while t<1e6:t,s,i,k=t+1,k*4./i+s,i+2,-k

Rubin - 54 znaki

def a()p=0;1000000.times{|i|p+=8/(4*i*(4*i+2))};p;end;

Moja pierwsza próba na konsoli

def a()i=1;p=0;while i<2**100 do p+=8/(i*(i+2));i+=4;end;p;end;

63 znaki.

Perl (76 chars)

$y=1e4;for$x(0..1e4-1){$y--while sqrt($x**2+$y**2)>1e4;$a+=$y}print 4*$a/1e8

(Result: 3.14159052)

Not the shortest possible solution, but maybe interesting. It's a geometrical one. I calculate the area under a circle.

I got another funny approach, but it's really slow. It counts the number of discrete points in a square that are below a quarter circle and calculates pi from it:

$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2

It expects the number of iterations as command line argument. Here you can see how run time relates to accuracy. ;)

$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 100
3.1796
real    0m0.011s
user    0m0.005s
sys 0m0.003s

$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 1000
3.14552
real    0m0.354s
user    0m0.340s
sys 0m0.004s

$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 10000
3.14199016
real    0m34.941s
user    0m33.757s
sys 0m0.097s

k (25 chars)

4*+/%(i#1 -1)'1+2!i:1000000

Slightly shorter:

+/(i#4 -4)%1+2*!i:1000000

Python (49)

print 4*sum((-1)**i/(2*i+1.)for i in range(9**6))

3.14159453527

CJam - 21

1e6{WI#4d*I2*)/}fI]:+

Pretty straightforward calculation of the given series.
CJam is http://sf.net/p/cjam

Julia - 30 characters

sum(4./[1:4:1e6] - 4./[3:4:1e6])

SQL, 253 bytes

DECLARE @B int=3, @A varchar(max), @C varchar(max)='1'
WHILE @B<100000
BEGIN
SELECT @C=@C+(select case when (@B-1)%4=0 then'+'else'-'end)+
(SELECT cast(cast(1.0/@B as decimal(9,8)) as varchar(max)))
SELECT @B=@B+2
END
EXECUTE('SELECT 4*('+@C+')')

I would provide a SQL Fiddle, but this goes too many loops deep finding the 1/3 1/5 1/7 etc. fractions and gives errors lol. However, if you change @B<100000 to 1000 then it runs (obviously not to the same number of digits of accuracy).

Befunge, 129 bytes

p08p109p^v*86%+55:<$$$<
\$\>:#,_@>+\55+/:#^_"."
v>p"~"/:"~"%08p"~"/00p:2\4%-*"(}"
8^90%"~":+2:+g90*+g80*<
>*:**\/+>"~~"00g:"~"`!|

Try it online!

In case anyone is wondering, it's an elephant.