Это происходит от http://programmers.blogoverflow.com/2012/08/20-controversial-programming-opinions/

«Учитывая, что число Pi можно оценить с помощью функции 4 * (1 - 1/3 + 1/5 - 1/7 +…) с большим количеством членов, дающих большую точность, напишите функцию, которая вычисляет число Pi с точностью до 5 десятичных знаков. "

• Обратите внимание, что оценка должна быть сделана путем расчета последовательности, приведенной выше.

JavaScript 46 58 56 45 байт

Обновление ES6 : Оказывается, теперь, когда прошло пять лет, нам доступно больше возможностей.

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

Эта версия ( 45 байт; да, letтребуется) работает в ES6 строгого режима в теории . На практике вы можете запустить его в V8 (например, с узлом) с помощью --use-strict --harmony-tailcalls; Функция надлежащего Tailcalls пока не реализована широко, увы. Тем не менее, это определенное поведение, так что должно быть хорошо.

Если мы хотим придерживаться того, что широко реализовано и не требует строгого режима, мы можем просто использовать синтаксис жирных стрелок ES6 для функций, но в остальном сохранить ту же реализацию, что и раньше (предложенную Брайаном Х), за стоимость 48 байт.

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

Выбор имени для одного параметра на самом деле не имеет значения, но мы могли бы также выбрать одно из имен, которые мы используем, чтобы минимизировать загрязнение глобальной области.

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

Эта версия является выражением функции; добавьте два символа (например, " f"), если хотите, чтобы они были названы. Эта версия забивает глобалы aи i; это может быть предотвращено, если мы добавим « a,i» в список параметров.

Использует пересмотренную версию алгоритма, чтобы обойти необходимость вычитания.

 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)   + ...

Вот «простая» версия без этой настройки:

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

который в часы на 64 62 символов.

Спасибо @ardnew за предложение избавиться от 4*до return.

история

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 байт

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

Это печатает 1000 цифр; немного больше, чем требуется 5. Вместо того, чтобы использовать предписанную итерацию, он использует это:

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

6637( Самый внутренний знаменатель) может быть сформулирован как:

цифры * 2 * log 2 (10)

Это подразумевает линейную сходимость. Каждая более глубокая итерация произведет еще один двоичный бит числа пи .

Если , однако, вы настаиваете на использование загара ^-1 личности, подобная конвергенция может быть достигнута, если вы не возражаете идти о проблеме несколько иначе. Взглянем на частичные суммы:

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

очевидно, что каждый член прыгает вперед и назад по обе стороны от точки схождения; ряд имеет переменную сходимость. Кроме того, каждый член ближе к точке схождения, чем предыдущий; оно абсолютно монотонно по отношению к точке сходимости. Сочетание этих двух свойств подразумевает, что среднее арифметическое любых двух соседних слагаемых ближе к точке сходимости, чем любое из самих слагаемых. Чтобы лучше понять, что я имею в виду, рассмотрим следующее изображение:

Внешняя серия является оригинальной, а внутренняя серия определяется по среднему значению каждого из соседних членов. Замечательная разница. Но что действительно примечательно, так это то, что эта новая серия также имеет чередующуюся сходимость и является абсолютно монотонной по отношению к точке схождения. Это означает, что этот процесс может применяться снова и снова, до тошноты.

Ok. Но как?

Некоторые формальные определения. Пусть P ₁ (n) - n- ^й член первой последовательности, P ₂ (n) - n- ^й член второй последовательности, и аналогично P _k (n) - n- ^й член k- ^й последовательности, как определено выше. ,

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, ...]

Не удивительно, что эти коэффициенты точно следуют биномиальным коэффициентам и могут быть выражены в виде одной строки треугольника Паскаля. Поскольку произвольная строка треугольника Паскаля тривиальна для вычисления, можно найти произвольно «глубокий» ряд, просто взяв первые n частичных сумм, умножив каждый на соответствующий член в k- ^й строке треугольника Паскаля и разделив на 2 ^к-1 .

Таким образом, полная 32-битная точность с плавающей запятой (~ 14 знаков после запятой) может быть достигнута всего за 36 итераций, и в этот момент частичные суммы даже не сходятся во втором знаке после запятой. Это явно не игра в гольф

# 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

Если вам нужна произвольная точность, это может быть достигнуто с небольшой модификацией. Здесь еще раз вычисляем 1000 цифр:

# 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

Начальное значение p начинается на 2 ¹⁰ больше, чтобы нейтрализовать эффекты целочисленного деления s / d, когда d становится больше, в результате чего последние несколько цифр не сходятся. Обратите внимание, что здесь 3318также:

цифры * log 2 (10)

То же количество итераций, что и в первом алгоритме (уменьшается вдвое, поскольку t уменьшается на 1 вместо 2 на каждую итерацию). Еще раз, это указывает на линейную сходимость: один двоичный бит числа пи на итерацию. В обоих случаях для расчета 1000 цифр числа пи требуется 3318 итераций , что несколько лучше, чем 1 миллион итераций для расчета 5.

Mathematica 42 39 34 33 31 26 32

Архимедов подход 26 символов

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

Это достигает критерия, когда ввод 822.

Вопрос: Кто-нибудь знает, как он рассчитал грех на 180 градусов? Я не.

Подход Лейбница (серия Григория) 32 символа

Это та же функция, которую задала проблемная задача в качестве примера. Он достигает критерия примерно за полмиллиона итераций.

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

Мадхава-Лейбниц Подход 37 символов

Этот вариант использует еще несколько символов, но сходится к критерию всего за 9 итераций!

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

APL (14)

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

Ява (67 символов)

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

Обратите внимание, что это позволяет избежать потери значимости, добавляя числа в правильном порядке.

Хаскелл, 32

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

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

Считая имя функции это

34

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

R - 25 символов

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

C (GCC) (44 знака)

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

Это 41 символ, но его также нужно скомпилировать, -O2чтобы оптимизатор исключил рекурсию хвоста. Это также зависит от неопределенного поведения в отношении порядка, в котором ++они выполняются; спасибо Угорену за указание на это. Я тестировал с gcc 4.4.3 под 64-битным Linux.

Обратите внимание, что если оптимизатор также не переупорядочивает сумму, он будет прибавлять к наименьшему числу, поэтому он избегает потери значимости.

Звоните как p().

J, 26 символов

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

Перенесено из 100 предметов последовательности в 1е6 предметов. Кроме того, теперь этот код помечен и может быть скопирован из браузера в консоль без ошибок.

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

Javascript - 33 персонажа

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

Позвоните, pпередав положительное нечетное число, xи он вычислит Пи с (x-1)/2условиями.

Рубин - 82 символа

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)

Попробуйте это: https://repl.it/LQ8w

Подход использует данную серию косвенно, используя подход численного ускорения. В результате получается

pi ≈ 3.14159265161

против

pi = 3.14159265359

Начинается с

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

И затем, так как это чередуется, мы можем ускорить сходимость, используя

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

И это неоднократно применяется это:

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

И для простоты f(n) = f(n,n).

Рубин - 50 символов

Если вы не возражаете бежать очень долго, то вы можете просто использовать

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

или

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

C 69 символов

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

• Запустить без параметров командной строки (поэтому aустанавливается в 1).
• Должен быть скомпилирован с оптимизацией.
• void mainстранно и нестандартно, но заставляет вещи работать. Без этого рекурсия реализуется как реальный вызов, приводящий к переполнению стека. Альтернативой является добавление return.
• Два символа 4*могут быть сохранены, если они работают с тремя параметрами командной строки.

Clojure - 79 символов

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

Это создает функцию без аргументов, которая будет вычислять число с плавающей запятой, которое правильно приближает число Пи к пяти десятичным разрядам. Обратите внимание, что это не привязывает функцию к имени, такому как pi, поэтому этот код должен оцениваться на месте evalкак (<code>)или привязываться к имени, и в этом случае решение

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

для 82 символов

Около

(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 символов

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

Я не знаю, что смогу получить его намного меньше, не нарушая правила алгоритма.

Perl - 43 39 символов

не уверен, правила для анонимных подпрограмм, но вот еще одна реализация, использующая конструкцию серии @ FireFly

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

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

Ява - 92 84 символа

Я не могу превзойти результат Питера Тейлора, но вот мой:

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;}

Безголовая версия:

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;
}

Редактировать: Сохранено несколько символов с помощью троичного оператора.

Питон - 56 символов

Мех, мой питон-фу недостаточно силен. Я не мог видеть больше ярлыков, но, возможно, более опытный игрок в гольф мог найти что-то, чтобы урезать здесь?

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

Рубин - 54 символа

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

Моя первая попытка на консоли

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

63 символа

Perl (76 символов)

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

(Результат: 3.14159052)

Не самое короткое решение, но, возможно, интересное. Это геометрический. Я рассчитываю площадь под кругом.

У меня есть другой забавный подход, но он очень медленный. Он подсчитывает количество дискретных точек в квадрате, которые находятся ниже четверти круга, и вычисляет число пи из него:

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

Ожидается количество итераций в качестве аргумента командной строки. Здесь вы можете увидеть, как время выполнения относится к точности. ;)

$ 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

к (25 символов)

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

Немного короче:

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

Python (49)

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

3.14159 453527

CJam - 21

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

Довольно простой расчет данной серии.
CJam является http://sf.net/p/cjam

Юлия - 30 персонажей

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

SQL, 253 байта

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+')')

Я бы предоставил SQL Fiddle, но в нем слишком много циклов, находим дроби 1/3, 1/5, 1/7 и т. Д., И это дает ошибки. Однако, если вы измените @B<100000на, 1000то он запустится (очевидно, не с тем же числом цифр точности).

Befunge, 129 байт

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

Попробуйте онлайн!

Если кому-то интересно, это слон.