Pregunta Code Golf: fórmula Leibniz para Pi


Recientemente publiqué una de mis preguntas de codificación de pizarra favorita de entrevista en "Cuál es tu opinión de programación más controvertida", que es escribir una función que computa Pi usando el Fórmula Leibniz.

Se puede abordar de diferentes maneras, y la condición de salida requiere un poco de reflexión, así que pensé que podría ser una pregunta interesante sobre el código de golf. ¡El código más corto gana!

Dado que se puede estimar Pi utilizando la función 4 * (1 - 1/3 + 1/5 - 1/7 + ...) con más términos que otorgan mayor precisión, escriba una función que calcule Pi dentro de 0.00001.

Edición: 3 de enero de 2008

Como sugerí en los comentarios, cambié la condición de salida para estar dentro de 0.00001 ya que eso es lo que realmente quise decir (una precisión de 5 decimales es mucho más difícil debido al redondeo y entonces no querría preguntar eso en una entrevista, mientras que dentro de 0.00001 es una condición de salida más fácil de entender e implementar).

Además, para responder a los comentarios, creo que mi intención era que la solución calculara el número de iteraciones, o verificara cuándo había hecho suficiente, pero no hay nada que evite que pre-compute la cantidad de iteraciones y use ese número. Realmente pregunté la pregunta por interés para ver qué se proponía la gente.


31


origen


Respuestas:


J, 14 caracteres

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

Explicación

  • 1e6 es el número 1 seguido de 6 ceros (1000000).
  • i.y genera el primer y números no negativos
  • +: es una función que dobla cada elemento en el argumento de la lista.
  • >: es una función que incrementa en uno cada elemento en el argumento de la lista.

Entonces, la expresión >:+:i.1e6 genera el primer millón de números impares:

1 3 5 7 ...

  • % es el operador recíproco (se puede omitir el numerador "1").
  • -/ hace una suma alternativa de cada elemento en el argumento de la lista.

Entonces, la expresión -/%>:+:i.1e6 genera la suma alternativa de los recíprocos del primer millón de números impares:

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

  • 4* es la multiplicación por cuatro. Si multiplicas por cuatro la suma anterior, tienes π.

¡Eso es! J es un lenguaje poderoso para las matemáticas.


Editar: ¡desde la generación 9! (362880) los términos para la suma alternativa son suficientes para tener una precisión de 5 dígitos decimales, y dado que la fórmula de Leibniz también se puede escribir de esta manera:

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

... puedes escribir un mensaje más corto, 12 caracteres versión del programa:

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

61



Idioma: Brainfuck, Número de Char: 51/59

¿Esto cuenta? =]

Debido a que no hay números de coma flotante en Brainfuck, fue bastante difícil hacer que las divisiones funcionen correctamente. Grr.

Sin nueva línea (51):

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

Con nueva línea (59):

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

37



Perl

26 caracteres

26 solo la función, 27 para calcular, 31 para imprimir. De los comentarios a esta respuesta.

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

28 caracteres

28 solo informática, 34 para imprimir. De los comentarios Tenga en cuenta que esta versión no puede usar 'decir'.

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

36 caracteres

36 solo informática, 42 para imprimir. La toma de Hudson en la reorganización de dreeves, de los comentarios.

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

Acerca del recuento de iteraciones: en lo que respecta a mis recuerdos matemáticos, 400000 es probablemente suficiente para tener una precisión de 0.00001. Pero un millón (o tan bajo como 8e5) realmente hace que la expansión decimal realmente coincida con 5 lugares fraccionarios, y es el mismo recuento de caracteres, así que lo guardé.


24



Ruby, 33 personajes

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

23



Otra versión de C #:

(60 caracteres)

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

20



52 caracteres en Pitón:

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

(51 soltando la 'x' de xrange)

36 caracteres en Octave (o Matlab):

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

(ejecute "format long;" para mostrar todos los dígitos significativos.) Omitiendo 'disp' llegamos a 30 caracteres:

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

14



Oracle SQL 73 caracteres

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

13



Idioma: C, Número de caracteres: 71

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

Idioma: C99, Número de Char: 97 (incluida la nueva línea requerida)

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

Debo señalar que las versiones anteriores (que son las mismas) llevan un registro de si una iteración adicional afectaría el resultado. Por lo tanto, realiza un número mínimo de operaciones. Para agregar más dígitos, reemplace 1E6 con 1E(num_digits+1) o 4E5 con 4E(num_digits) (dependiendo de la versión). Para los programas completos, %g puede necesitar ser reemplazado. float puede necesitar ser cambiado a double también.

Idioma: C, Número de caracteres: 67 (ver notas)

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

Esta versión usa una versión modificada del algoritmo publicado, tal como lo usan algunas otras respuestas. Además, no es tan limpio / eficiente como las dos primeras soluciones, ya que fuerza 100 000 iteraciones en lugar de detectar cuando las iteraciones carecen de sentido.

Idioma: C, Número de caracteres: 24 (copiar)

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

Sin embargo, no funciona con conteos de dígitos> 6.


10



Haskell

Lo tengo hasta 34 caracteres:

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

Esta expresión produce 3.141596416935556 cuando se evalúa.

Editar: aquí hay una versión más corta (a 33 caracteres) que usa foldl1 en lugar de foldl:

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

Edite 2: 9 ^ 6 en lugar de 10 ^ 6. Uno tiene que ser económico;)

Edición 3: reemplazado con foldl 'y foldl1' con foldl y foldl1 respectivamente, como resultado de Edit 2, ya no se desborda. Gracias a ShreevatsaR por notar esto.


10