¿Cuál es la manera más rápida de obtener el valor de π?

Realmente me gusta este programa, porque se aproxima π mirando su propia área.

IOCCC 1988: westley.c

#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

Aquí hay una descripción general de una técnica para calcular pi que aprendí en la escuela secundaria.

Solo comparto esto porque creo que es bastante simple que cualquiera pueda recordarlo, indefinidamente, además de que te enseña el concepto de métodos "Monte-Carlo" which que son métodos estadísticos para llegar a respuestas que no parecen inmediatamente deducibles a través de procesos aleatorios.

Dibuja un cuadrado e inscribe un cuadrante (un cuarto de un semicírculo) dentro de ese cuadrado (a cuadrante con radio igual al lado del cuadrado, por lo que llena tanto del cuadrado como sea posible)

Ahora lanza un dardo al cuadrado, y registra dónde cae that es decir, elige un punto aleatorio en cualquier lugar dentro del cuadrado. Por supuesto, aterrizó dentro de la plaza, pero ¿está dentro del semicírculo? Registre este hecho.

Repita este proceso muchas veces find y encontrará que hay una relación entre el número de puntos dentro del semicírculo versus el número total lanzado, llame a esta relación x.

Dado que el área del cuadrado es r veces r, se puede deducir que el área del semicírculo es x veces r veces r (es decir, x veces r al cuadrado). Por lo tanto x veces 4 le dará pi.

Este no es un método rápido de usar. Pero es un buen ejemplo de un método de Monte Carlo. Y si usted mira alrededor, usted puede encontrar que muchos problemas de otra manera fuera de sus habilidades computacionales pueden ser resueltos por tales métodos.

En aras de la integridad, una versión de plantilla de C++, que para una compilación optimizada calculará PI en tiempo de compilación y se insertará en un solo valor.

#include <iostream>

template<int I>
struct sign
{
    enum {value = (I % 2) == 0 ? 1 : -1};
};

template<int I, int J>
struct pi_calc
{
    inline static double value ()
    {
        return (pi_calc<I-1, J>::value () + pi_calc<I-1, J+1>::value ()) / 2.0;
    }
};

template<int J>
struct pi_calc<0, J>
{
    inline static double value ()
    {
        return (sign<J>::value * 4.0) / (2.0 * J + 1.0) + pi_calc<0, J-1>::value ();
    }
};


template<>
struct pi_calc<0, 0>
{
    inline static double value ()
    {
        return 4.0;
    }
};

template<int I>
struct pi
{
    inline static double value ()
    {
        return pi_calc<I, I>::value ();
    }
};

int main ()
{
    std::cout.precision (12);

    const double pi_value = pi<10>::value ();

    std::cout << "pi ~ " << pi_value << std::endl;

    return 0;
}

Nota para I > 10, las compilaciones optimizadas pueden ser lentas, del mismo modo para las corridas no optimizadas. Para 12 iteraciones creo que hay alrededor de 80k llamadas a value () (en ausencia de memoización).

En realidad hay un libro entero dedicado (entre otras cosas) a métodos rápidos para el cálculo de \pi: 'Pi and the AGM', por Jonathan y Peter Borwein (disponible en Amazon).

Estudié bastante la AGM y los algoritmos relacionados: es bastante interesante (aunque a veces no trivial).

Tenga en cuenta que para implementar la mayoría de los algoritmos modernos para calcular \pi, necesitará una biblioteca aritmética de múltiples precisiones (GMP es una buena opción, aunque es ha pasado un tiempo desde la última vez que lo usé).

La complejidad temporal de los mejores algoritmos está en O(M(n)log(n)), donde M(n) es la complejidad temporal para la multiplicación de dos enteros de n bits (M(n)=O(n log(n) log(log(n))) utilizando algoritmos basados en FFT, que generalmente se necesitan cuando se calculan dígitos de \pi, y tal algoritmo se implementa en GMP).

Tenga en cuenta que a pesar de que las matemáticas detrás de los algoritmos pueden no ser triviales, los algoritmos en sí son por lo general unas pocas líneas de pseudo-código, y su implementación suele ser muy sencilla (si eliges no escribir tu propia aritmética multiprecisión :-) ).

Las siguientes respuestas precisamente cómo hacer esto de la manera más rápida posible with con el menor esfuerzo de computación. Incluso si no te gusta la respuesta, tienes que admitir que de hecho es la forma más rápida de obtener el valor de PI.

La forma MÁS RÁPIDA para obtener el valor de Pi es:

1. eligió su lenguaje de programación favorito
2. cargar su biblioteca de matemáticas
3. y encontrar que Pi ya está definido allí!! listo para usar se..

En caso de que no tenga una biblioteca de Matemáticas a mano..

El SEGUNDO camino MÁS RÁPIDO (solución más universal) es:

Busque Pi en Internet, por ejemplo, aquí:

Http://www.eveandersson.com/pi/digits/1000000 (1 millón de dígitos .. ¿cuál es su precisión de punto flotante? )

O aquí:

Http://3.141592653589793238462643383279502884197169399375105820974944592.com /

O aquí:

Http://en.wikipedia.org/wiki/Pi

Es muy rápido encontrar los dígitos que necesita para cualquier aritmética de precisión que le gustaría usar, y al definir una constante, puede asegurarse de no perder un tiempo valioso de CPU.

No solo es una respuesta parcialmente humorística, sino que en realidad, si alguien pudiera seguir adelante y calcular el valor de Pi en una aplicación real .. eso sería una gran pérdida de tiempo de CPU, ¿no? Al menos no veo un verdadero aplicación para tratar de volver a calcular esto.

Estimado Moderador: tenga en cuenta que el OP pidió: "La forma más rápida para obtener el valor de PI"

La fórmula BBP le permite calcular el enésimo dígito - en base 2 (o 16) - sin tener que molestarse siquiera con los dígitos n-1 anteriores primero:)

En lugar de definir pi como una constante, siempre uso acos(-1).

Acabo de encontrar este que debería estar aquí para completar:

Calcular PI en Piet

Tiene la propiedad bastante agradable de que la precisión se puede mejorar haciendo que el programa sea más grande.

Aquí 's una cierta penetración en la lengua sí mismo

Si este artículo es verdadero, entonces el algoritmo que Bellard ha creado podría ser uno de los más rápidos disponibles. Ha creado pi a 2,7 BILLONES de dígitos utilizando una PC DE ESCRITORIO!

...y ha publicado su trabajo aquí

Buen trabajo Bellard, eres un pionero!

Http://www.theregister.co.uk/2010/01/06/very_long_pi /

Este es un método "clásico", muy fácil de implementar. Esta implementación, en python (lenguaje no tan rápido) lo hace:

from math import pi
from time import time


precision = 10**6 # higher value -> higher precision
                  # lower  value -> higher speed

t = time()

calc = 0
for k in xrange(0, precision):
    calc += ((-1)**k) / (2*k+1.)
calc *= 4. # this is just a little optimization

t = time()-t

print "Calculated: %.40f" % calc
print "Costant pi: %.40f" % pi
print "Difference: %.40f" % abs(calc-pi)
print "Time elapsed: %s" % repr(t)

Puede encontrar más información aquí.

De todos modos, la forma más rápida de obtener un valor preciso de pi en python es:

from gmpy import pi
print pi(3000) # the rule is the same as 
               # the precision on the previous code

Aquí está la parte de la fuente para el método gmpy pi, no creo que el código sea tan útil como el comentario en este caso:

static char doc_pi[]="\
pi(n): returns pi with n bits of precision in an mpf object\n\
";

/* This function was originally from netlib, package bmp, by
 * Richard P. Brent. Paulo Cesar Pereira de Andrade converted
 * it to C and used it in his LISP interpreter.
 *
 * Original comments:
 * 
 *   sets mp pi = 3.14159... to the available precision.
 *   uses the gauss-legendre algorithm.
 *   this method requires time o(ln(t)m(t)), so it is slower
 *   than mppi if m(t) = o(t**2), but would be faster for
 *   large t if a faster multiplication algorithm were used
 *   (see comments in mpmul).
 *   for a description of the method, see - multiple-precision
 *   zero-finding and the complexity of elementary function
 *   evaluation (by r. p. brent), in analytic computational
 *   complexity (edited by j. f. traub), academic press, 1976, 151-176.
 *   rounding options not implemented, no guard digits used.
*/
static PyObject *
Pygmpy_pi(PyObject *self, PyObject *args)
{
    PympfObject *pi;
    int precision;
    mpf_t r_i2, r_i3, r_i4;
    mpf_t ix;

    ONE_ARG("pi", "i", &precision);
    if(!(pi = Pympf_new(precision))) {
        return NULL;
    }

    mpf_set_si(pi->f, 1);

    mpf_init(ix);
    mpf_set_ui(ix, 1);

    mpf_init2(r_i2, precision);

    mpf_init2(r_i3, precision);
    mpf_set_d(r_i3, 0.25);

    mpf_init2(r_i4, precision);
    mpf_set_d(r_i4, 0.5);
    mpf_sqrt(r_i4, r_i4);

    for (;;) {
        mpf_set(r_i2, pi->f);
        mpf_add(pi->f, pi->f, r_i4);
        mpf_div_ui(pi->f, pi->f, 2);
        mpf_mul(r_i4, r_i2, r_i4);
        mpf_sub(r_i2, pi->f, r_i2);
        mpf_mul(r_i2, r_i2, r_i2);
        mpf_mul(r_i2, r_i2, ix);
        mpf_sub(r_i3, r_i3, r_i2);
        mpf_sqrt(r_i4, r_i4);
        mpf_mul_ui(ix, ix, 2);
        /* Check for convergence */
        if (!(mpf_cmp_si(r_i2, 0) && 
              mpf_get_prec(r_i2) >= (unsigned)precision)) {
            mpf_mul(pi->f, pi->f, r_i4);
            mpf_div(pi->f, pi->f, r_i3);
            break;
        }
    }

    mpf_clear(ix);
    mpf_clear(r_i2);
    mpf_clear(r_i3);
    mpf_clear(r_i4);

    return (PyObject*)pi;
}

EDITAR: Tuve algún problema con el corte y pegue e identation, de todos modos puede encontrar la fuente aquí.

Si por más rápido quieres decir más rápido para escribir el código, aquí está la solución golfscript :

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;

Utilice la fórmula tipo Machin

176 * arctan (1/57) + 28 * arctan (1/239) - 48 * arctan (1/682) + 96 * arctan(1/12943) 

[; \left( 176 \arctan \frac{1}{57} + 28 \arctan \frac{1}{239} - 48 \arctan \frac{1}{682} + 96 \arctan \frac{1}{12943}\right) ;], for you TeX the World people.

Implementado en Scheme, por ejemplo:

(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))

Pi es exactamente 3! [Prof. Frink (Simpsons)]

Broma, pero aquí hay uno en C# (. NET-Framework requerido).

using System;
using System.Text;

class Program {
    static void Main(string[] args) {
        int Digits = 100;

        BigNumber x = new BigNumber(Digits);
        BigNumber y = new BigNumber(Digits);
        x.ArcTan(16, 5);
        y.ArcTan(4, 239);
        x.Subtract(y);
        string pi = x.ToString();
        Console.WriteLine(pi);
    }
}

public class BigNumber {
    private UInt32[] number;
    private int size;
    private int maxDigits;

    public BigNumber(int maxDigits) {
        this.maxDigits = maxDigits;
        this.size = (int)Math.Ceiling((float)maxDigits * 0.104) + 2;
        number = new UInt32[size];
    }
    public BigNumber(int maxDigits, UInt32 intPart)
        : this(maxDigits) {
        number[0] = intPart;
        for (int i = 1; i < size; i++) {
            number[i] = 0;
        }
    }
    private void VerifySameSize(BigNumber value) {
        if (Object.ReferenceEquals(this, value))
            throw new Exception("BigNumbers cannot operate on themselves");
        if (value.size != this.size)
            throw new Exception("BigNumbers must have the same size");
    }

    public void Add(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] +
                            value.number[index] + carry;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                carry = 1;
            else
                carry = 0;
            index--;
        }
    }
    public void Subtract(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 borrow = 0;
        while (index >= 0) {
            UInt64 result = 0x100000000U + (UInt64)number[index] -
                            value.number[index] - borrow;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                borrow = 0;
            else
                borrow = 1;
            index--;
        }
    }
    public void Multiply(UInt32 value) {
        int index = size - 1;
        while (index >= 0 && number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] * value + carry;
            number[index] = (UInt32)result;
            carry = (UInt32)(result >> 32);
            index--;
        }
    }
    public void Divide(UInt32 value) {
        int index = 0;
        while (index < size && number[index] == 0)
            index++;

        UInt32 carry = 0;
        while (index < size) {
            UInt64 result = number[index] + ((UInt64)carry << 32);
            number[index] = (UInt32)(result / (UInt64)value);
            carry = (UInt32)(result % (UInt64)value);
            index++;
        }
    }
    public void Assign(BigNumber value) {
        VerifySameSize(value);
        for (int i = 0; i < size; i++) {
            number[i] = value.number[i];
        }
    }

    public override string ToString() {
        BigNumber temp = new BigNumber(maxDigits);
        temp.Assign(this);

        StringBuilder sb = new StringBuilder();
        sb.Append(temp.number[0]);
        sb.Append(System.Globalization.CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator);

        int digitCount = 0;
        while (digitCount < maxDigits) {
            temp.number[0] = 0;
            temp.Multiply(100000);
            sb.AppendFormat("{0:D5}", temp.number[0]);
            digitCount += 5;
        }

        return sb.ToString();
    }
    public bool IsZero() {
        foreach (UInt32 item in number) {
            if (item != 0)
                return false;
        }
        return true;
    }

    public void ArcTan(UInt32 multiplicand, UInt32 reciprocal) {
        BigNumber X = new BigNumber(maxDigits, multiplicand);
        X.Divide(reciprocal);
        reciprocal *= reciprocal;

        this.Assign(X);

        BigNumber term = new BigNumber(maxDigits);
        UInt32 divisor = 1;
        bool subtractTerm = true;
        while (true) {
            X.Divide(reciprocal);
            term.Assign(X);
            divisor += 2;
            term.Divide(divisor);
            if (term.IsZero())
                break;

            if (subtractTerm)
                this.Subtract(term);
            else
                this.Add(term);
            subtractTerm = !subtractTerm;
        }
    }
}

Si está dispuesto a usar una aproximación, 355 / 113 es bueno para 6 dígitos decimales, y tiene la ventaja añadida de ser utilizable con expresiones enteras. Eso no es tan importante en estos días, ya que "co-procesador matemático de coma flotante" dejó de tener ningún significado, pero fue bastante importante una vez.

Con dobles:

4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))

Esto será preciso hasta 14 decimales, suficiente para llenar un doble (la inexactitud es probablemente porque el resto de los decimales en las tangentes del arco están truncados).

También Seth, es 3.141592653589793238463, no 64.

Calcular PI en tiempo de compilación con D.

(Copiado de DSource.org )

/** Calculate pi at compile time
 *
 * Compile with dmd -c pi.d
 */
module calcpi;

import meta.math;
import meta.conv;

/** real evaluateSeries!(real x, real metafunction!(real y, int n) term)
 *
 * Evaluate a power series at compile time.
 *
 * Given a metafunction of the form
 *  real term!(real y, int n),
 * which gives the nth term of a convergent series at the point y
 * (where the first term is n==1), and a real number x,
 * this metafunction calculates the infinite sum at the point x
 * by adding terms until the sum doesn't change any more.
 */
template evaluateSeries(real x, alias term, int n=1, real sumsofar=0.0)
{
  static if (n>1 && sumsofar == sumsofar + term!(x, n+1)) {
     const real evaluateSeries = sumsofar;
  } else {
     const real evaluateSeries = evaluateSeries!(x, term, n+1, sumsofar + term!(x, n));
  }
}

/*** Calculate atan(x) at compile time.
 *
 * Uses the Maclaurin formula
 *  atan(z) = z - z^3/3 + Z^5/5 - Z^7/7 + ...
 */
template atan(real z)
{
    const real atan = evaluateSeries!(z, atanTerm);
}

template atanTerm(real x, int n)
{
    const real atanTerm =  (n & 1 ? 1 : -1) * pow!(x, 2*n-1)/(2*n-1);
}

/// Machin's formula for pi
/// pi/4 = 4 atan(1/5) - atan(1/239).
pragma(msg, "PI = " ~ fcvt!(4.0 * (4*atan!(1/5.0) - atan!(1/239.0))) );

Esta versión (en Delphi) no es nada especial, pero es al menos más rápida que la versión que Nick Hodge publicó en su blog :). En mi máquina, se tarda unos 16 segundos para hacer mil millones de iteraciones, dando un valor de 3.1415926525879 (la parte exacta está en negrita).

program calcpi;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  start, finish: TDateTime;

function CalculatePi(iterations: integer): double;
var
  numerator, denominator, i: integer;
  sum: double;
begin
  {
  PI may be approximated with this formula:
  4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 .......)
  //}
  numerator := 1;
  denominator := 1;
  sum := 0;
  for i := 1 to iterations do begin
    sum := sum + (numerator/denominator);
    denominator := denominator + 2;
    numerator := -numerator;
  end;
  Result := 4 * sum;
end;

begin
  try
    start := Now;
    WriteLn(FloatToStr(CalculatePi(StrToInt(ParamStr(1)))));
    finish := Now;
    WriteLn('Seconds:' + FormatDateTime('hh:mm:ss.zz',finish-start));
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

En los viejos tiempos, con palabras pequeñas y operaciones de coma flotante lentas o inexistentes, solíamos hacer cosas como estas:

/* Return approximation of n * PI; n is integer */
#define pi_times(n) (((n) * 22) / 7)

Para aplicaciones que no requieren mucha precisión (videojuegos, por ejemplo), esto es muy rápido y es lo suficientemente preciso.

Si desea calcular una aproximación del valor de π (por alguna razón), debe probar un algoritmo de extracción binaria. La mejora de Bellardde BBP da doe PI en O(N^2).

Si quieres obtener una aproximación del valor de π para hacer cálculos, entonces:

PI = 3.141592654

Concedido, eso es solo una aproximación, y no del todo exacto. Está apagado por un poco más de 0.00000000004102. (cuatro diez trillonésimas, aproximadamente ⁴/_{10,000,000,000}).

Si quieres hacer matemáticas con π, entonces consíguete un lápiz y papel o un paquete de álgebra computacional, y usa el valor exacto de π, π.

Si realmente quieres una fórmula, esta es divertida:

Π = - i ln (-1)

El método de Brent publicado anteriormente por Chris es muy bueno; Brent generalmente es un gigante en el campo de la aritmética de precisión arbitraria.

Si todo lo que quieres es el Enésimo dígito, el famoso Fórmula BBP es útil en hex

Calculando π del área del círculo: -)

<input id="range" type="range" min="10" max="960" value="10" step="50" oninput="calcPi()">
<br>
<div id="cont"></div>

<script>
function generateCircle(width) {
    var c = width/2;
    var delta = 1.0;
    var str = "";
    var xCount = 0;
    for (var x=0; x <= width; x++) {
        for (var y = 0; y <= width; y++) {
            var d = Math.sqrt((x-c)*(x-c) + (y-c)*(y-c));
            if (d > (width-1)/2) {
                str += '.';
            }
            else {
                xCount++;
                str += 'o';
            }
            str += "&nbsp;" 
        }
        str += "\n";
    }
    var pi = (xCount * 4) / (width * width);
    return [str, pi];
}

function calcPi() {
    var e = document.getElementById("cont");
    var width = document.getElementById("range").value;
    e.innerHTML = "<h4>Generating circle...</h4>";
    setTimeout(function() {
        var circ = generateCircle(width);
        e.innerHTML  = "<pre>" + "π = " + circ[1].toFixed(2) + "\n" + circ[0] +"</pre>";
    }, 200);
}
calcPi();
</script>

Mejor enfoque

Para obtener la salida de constantes estándar como pi o los conceptos estándar, primero debemos ir con los métodos builtins disponibles en el lenguaje que está utilizando. Devolverá valor de la manera más rápida y mejor también. Estoy usando python para obtener la forma más rápida de obtener el valor pi

• variable pi de la biblioteca matemática. La biblioteca matemática almacena la variable pi como constante.

Math_pi.py

import math
print math.pi

Ejecutar la utilidad script with time de linux /usr/bin/time -v python math_pi.py

Salida:

Command being timed: "python math_pi.py"
User time (seconds): 0.01
System time (seconds): 0.01
Percent of CPU this job got: 91%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03

• Use el método arc cos de matemáticas

Acos_pi.py

import math
print math.acos(-1)

Ejecute el script con la utilidad time de linux /usr/bin/time -v python acos_pi.py

Salida:

Command being timed: "python acos_pi.py"
User time (seconds): 0.02
System time (seconds): 0.01
Percent of CPU this job got: 94%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03

• use Fórmula BBP

Bbp_pi.py

from decimal import Decimal, getcontext
getcontext().prec=100
print sum(1/Decimal(16)**k * 
          (Decimal(4)/(8*k+1) - 
           Decimal(2)/(8*k+4) - 
           Decimal(1)/(8*k+5) -
           Decimal(1)/(8*k+6)) for k in range(100))

Ejecute el script con la utilidad time de linux /usr/bin/time -v python bbp_pi.py

Salida:

Command being timed: "python c.py"
User time (seconds): 0.05
System time (seconds): 0.01
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.06

Así que la mejor manera es utilizar el método builtins proporcionado por la causa de la lengua que son los más rápidos y mejores para obtener la salida. En python usa matemáticas.pi