Qual é a maneira mais rápida de obter o valor de π?

votos
275

Eu estou procurando a maneira mais rápida para obter o valor de π, como um desafio pessoal. Mais especificamente, eu estou usando formas que não envolvem o uso de #defineconstantes como M_PI, ou embutir o número.

O programa abaixo testa as várias maneiras que eu conheço. A versão de montagem em linha é, em teoria, a opção mais rápida, embora claramente não portátil. Eu incluí-lo como uma linha de base para comparar com as outras versões. Em meus testes, com built-ins, a 4 * atan(1)versão é mais rápido no GCC 4.2, porque auto-dobra o atan(1)em uma constante. Com -fno-builtinespecificado, a atan2(0, -1)versão é mais rápida.

Aqui está o principal programa de testes ( pitimes.c):

#include <math.h>
#include <stdio.h>
#include <time.h>

#define ITERS 10000000
#define TESTWITH(x) {                                                       \
    diff = 0.0;                                                             \
    time1 = clock();                                                        \
    for (i = 0; i < ITERS; ++i)                                             \
        diff += (x) - M_PI;                                                 \
    time2 = clock();                                                        \
    printf(%s\t=> %e, time => %f\n, #x, diff, diffclock(time2, time1));   \
}

static inline double
diffclock(clock_t time1, clock_t time0)
{
    return (double) (time1 - time0) / CLOCKS_PER_SEC;
}

int
main()
{
    int i;
    clock_t time1, time2;
    double diff;

    /* Warmup. The atan2 case catches GCC's atan folding (which would
     * optimise the ``4 * atan(1) - M_PI'' to a no-op), if -fno-builtin
     * is not used. */
    TESTWITH(4 * atan(1))
    TESTWITH(4 * atan2(1, 1))

#if defined(__GNUC__) && (defined(__i386__) || defined(__amd64__))
    extern double fldpi();
    TESTWITH(fldpi())
#endif

    /* Actual tests start here. */
    TESTWITH(atan2(0, -1))
    TESTWITH(acos(-1))
    TESTWITH(2 * asin(1))
    TESTWITH(4 * atan2(1, 1))
    TESTWITH(4 * atan(1))

    return 0;
}

E o material de montagem inline ( fldpi.c) que irá funcionar apenas para sistemas x86 e x64:

double
fldpi()
{
    double pi;
    asm(fldpi : =t (pi));
    return pi;
}

E um script de construção que constrói todas as configurações estou testando ( build.sh):

#!/bin/sh
gcc -O3 -Wall -c           -m32 -o fldpi-32.o fldpi.c
gcc -O3 -Wall -c           -m64 -o fldpi-64.o fldpi.c

gcc -O3 -Wall -ffast-math  -m32 -o pitimes1-32 pitimes.c fldpi-32.o
gcc -O3 -Wall              -m32 -o pitimes2-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -fno-builtin -m32 -o pitimes3-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -ffast-math  -m64 -o pitimes1-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall              -m64 -o pitimes2-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall -fno-builtin -m64 -o pitimes3-64 pitimes.c fldpi-64.o -lm

Além de testar entre diversas bandeiras de compilador (Eu comparação 32 bits contra 64 bits, também, porque as optimizações são diferentes), que também já tentou trocando a ordem dos testes ao redor. Mas, ainda assim, a atan2(0, -1)versão ainda sai por cima o tempo todo.

Publicado 01/08/2008 em 06:21
fonte usuário
Em outras línguas...                            


23 respostas

votos
180

O método de Monte Carlo , como mencionado, aplica alguns grandes conceitos, mas é, claramente, não o mais rápido, e não por um tiro longo, não por qualquer medida razoável. Além disso, tudo depende de que tipo de precisão que você está procurando. O π mais rápida que eu conheço é aquele com os dígitos codificados. Olhando para Pi e Pi [PDF] , há um monte de fórmulas.

Aqui está um método que converge rapidamente - cerca de 14 dígitos por iteração. PiFast , a aplicação mais rápida corrente, utiliza esta fórmula com a FFT . Eu só vou escrever a fórmula, uma vez que o código é simples. Esta fórmula foi quase que por Ramanujan e descoberto por Chudnovsky . É realmente como ele calculou vários bilhões de dígitos do número - por isso não é um método de ignorar. A fórmula transbordará e rapidamente, uma vez que estão a dividir factoriais, seria vantajoso, em seguida, para atrasar tais cálculos para remover termos.

digite descrição da imagem aqui

digite descrição da imagem aqui

Onde,

digite descrição da imagem aqui

Abaixo está o algoritmo de Brent-Salamin . Wikipedia menciona que, quando um e b são "fechar o suficiente", em seguida, (a + b) ² / 4t será uma aproximação de π. Eu não tenho certeza do que "perto o suficiente" significa, mas a partir de meus testes, uma iteração tem 2 dígitos, dois tem 7, e três tinham 15, é claro que isso é com duplos, por isso pode ter um erro com base na sua representação e o verdadeiro cálculo poderia ser mais preciso.

let pi_2 iters =
    let rec loop_ a b t p i =
        if i = 0 then a,b,t,p
        else
            let a_n = (a +. b) /. 2.0 
            and b_n = sqrt (a*.b)
            and p_n = 2.0 *. p in
            let t_n = t -. (p *. (a -. a_n) *. (a -. a_n)) in
            loop_ a_n b_n t_n p_n (i - 1)
    in 
    let a,b,t,p = loop_ (1.0) (1.0 /. (sqrt 2.0)) (1.0/.4.0) (1.0) iters in
    (a +. b) *. (a +. b) /. (4.0 *. t)

Por último, que tal um pouco de golfe pi (800 dígitos)? 160 caracteres!

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
Respondeu 02/08/2008 em 19:22
fonte usuário

votos
96

Eu realmente gosto deste programa, que se aproxima pi, olhando para sua própria á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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Respondeu 02/09/2008 em 14:28
fonte usuário

votos
72

Aqui está uma descrição geral de uma técnica para calcular o pi que eu aprendi na escola.

Eu só posso compartilhar isso porque eu acho que é bastante simples que qualquer um pode se lembrar, por tempo indeterminado, além de que lhe ensina o conceito de métodos "Monte-Carlo" - que são métodos estatísticos de se chegar a respostas que não aparecem imediatamente para ser deducible através de processos aleatórios.

Desenhar um quadrado, e inscrever um quadrante (um quarto de um semi-círculo) dentro desse quadrado (um quadrante com raio igual ao lado do quadrado, de modo a preencher tanto do quadrado quanto possível)

Agora lançar um dardo na praça, e gravar onde ele cair - isto é, escolher um ponto aleatório em qualquer lugar dentro da praça. Claro, que aterrou dentro do quadrado, mas é no interior do semi-círculo? Grave este fato.

Repita este processo muitas vezes - e você vai encontrar há uma relação entre o número de pontos dentro do semi-círculo em relação ao número total jogado, chamar esta relação x.

Como a área da praça é r vezes r, você pode deduzir que a área do semi-círculo é x vezes r r vezes (isto é, x vezes r quadrado). Daí x vezes 4 lhe dará pi.

Este não é um método rápido de usar. Mas é um bom exemplo de um método de Monte Carlo. E se você olhar ao redor, você pode achar que muitos problemas de outra maneira fora de suas habilidades computacionais podem ser resolvidos por tais métodos.

Respondeu 01/08/2008 em 14:37
fonte usuário

votos
51

No interesse da integridade, uma versão template C ++, o que para uma compilação otimizada irá calcular PI em tempo de compilação e inline para um único 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, otimizado constrói pode ser lento, mesmo para corridas não optimizados. Por 12 iterações Eu acredito que existem cerca de 80k chamadas para valor () (na ausência de memoisation).

Respondeu 22/12/2009 em 16:40
fonte usuário

votos
40

Na verdade, há um livro inteiro dedicado (entre outras coisas) para rápidos métodos para o cálculo de \ pi: 'Pi ea AGM', por Jonathan e Peter Borwein ( disponível na Amazon ).

Estudei a AGM e algoritmos relacionados um pouco: é bastante interessante (embora às vezes não-trivial).

Note-se que para implementar algoritmos mais modernos para calcular \ pi, você vai precisar de uma biblioteca aritmética multiprecision ( GMP é bastante uma boa escolha, embora ele tem sido um tempo desde a última vez usei).

O tempo-complexidade dos melhores algoritmos está em O (H (n) de registo (n)), em que M (N) é o tempo-complexidade para a multiplicação dos dois inteiros de n bits (H (n) = O (n log (n) (log (n))) utilizando algoritmos baseados em FFT, que são geralmente necessários quando computação dígitos de \ pi, e um tal algoritmo é implementada em GMP).

Note-se que, embora a matemática por trás dos algoritmos pode não ser trivial, os próprios algoritmos são geralmente algumas linhas de pseudo-código, e sua implementação é geralmente muito simples (se você optar por não escrever a sua própria aritmética multiprecision :-)).

Respondeu 24/08/2008 em 18:14
fonte usuário

votos
36

As seguintes respostas precisamente como fazer isso da maneira mais rápida possível - com o menor esforço computacional . Mesmo se você não gostar da resposta, você tem que admitir que ele é realmente o caminho mais rápido para obter o valor de PI.

A forma mais RÁPIDA de obter o valor de Pi é:

  1. escolheu sua linguagem de programação favorita
  2. carregá-lo da biblioteca de matemática
  3. e achar que Pi já está definido lá !! pronto para usá-lo ..

no caso de você não tem uma biblioteca de matemática na mão ..

o segundo mais rápido forma (solução mais universal) é:

olhar para cima Pi na Internet, por exemplo aqui:

http://www.eveandersson.com/pi/digits/1000000 (1 milhão de dígitos .. qual é o seu ponto flutuante de precisão?)

ou aqui:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

ou aqui:

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

É muito rápido para encontrar os dígitos que você precisa para qualquer aritmética de precisão que você gostaria de usar, e definindo uma constante, você pode ter certeza que você não perca tempo CPU precioso.

Não só isto é uma resposta parcialmente bem-humorado, mas, na realidade, se alguém iria em frente e calcular o valor de Pi em uma aplicação real .. que seria um muito grande desperdício de tempo de CPU, não é? Pelo menos eu não vejo uma aplicação real para tentar re-calcular isso.

Caro Moderador: por favor, note que o OP perguntou: "maneira mais rápida para obter o valor de PI"

Respondeu 28/10/2011 em 02:02
fonte usuário

votos
25

A fórmula BBP permite calcular o dígito enésimo - na base 2 (ou 16) - sem ter de se preocupar com os mesmo n-1 anteriores dígitos primeiro :)

Respondeu 29/08/2008 em 10:22
fonte usuário

votos
21

Em vez de definir pi como uma constante, eu sempre uso acos(-1).

Respondeu 08/03/2009 em 04:02
fonte usuário

votos
20

Se este artigo for verdade, então o algoritmo que Bellard criou poderia ser um dos mais rápida disponível. Ele criou pi a 2,7 trilhões de dígitos usando um PC desktop!

... e ele publicou seu trabalho aqui

O bom trabalho Bellard, Você é um pioneiro!

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

Respondeu 06/01/2010 em 13:41
fonte usuário

votos
20

Apenas veio este que deveria estar aqui para ser completo:

calcular PI em Piet

Ele tem a propriedade bastante agradável que a precisão pode ser melhorada tornando o programa maior.

Aqui é alguns insights sobre a própria linguagem

Respondeu 12/01/2009 em 19:46
fonte usuário

votos
19

Este é um método "clássico", muito fácil de implementar. Esta implementação, em python (linguagem não tão rápido) faz:

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)

Você pode encontrar mais informações aqui .

De qualquer forma o caminho mais rápido para obter um como-muito-as-you-want valor preciso do pi em python é:

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

aqui é o pedaço de fonte para o método pi gmpy, eu não acho que o código é tão útil quanto o comentário, neste 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;
}

EDIT: eu tinha algum problema com cortar e colar e identation, de qualquer maneira você pode encontrar a fonte aqui .

Respondeu 02/10/2008 em 22:27
fonte usuário

votos
17

Se por mais rápido que você quer dizer mais rápida de digitar o código, aqui está a golfscript solução:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Respondeu 06/08/2008 em 23:54
fonte usuário

votos
15

Utilizar a Fórmula de 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 no Esquema, por exemplo:

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

Respondeu 05/02/2011 em 06:26
fonte usuário

votos
15

Com duplos:

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

Este será preciso até 14 casas decimais, o suficiente para encher um duplo (a imprecisão é provavelmente porque o resto das casas decimais nas tangentes arco são truncados).

Também Seth, é 3,14159265358979323846 3 , não 64.

Respondeu 28/02/2010 em 04:52
fonte usuário

votos
15

Se você estiver disposto a usar uma aproximação, 355 / 113é bom para 6 dígitos decimais, e tem a vantagem adicional de ser utilizável com expressões inteiras. Isso não é tão importante nos dias de hoje, como "flutuante co-processador de ponto de matemática" deixou de ter qualquer significado, mas foi muito importante uma vez.

Respondeu 17/09/2009 em 17:30
fonte usuário

votos
15

Pi é exatamente 3! [Prof. Frink (Simpsons)]

Piada, mas aqui está um em C # (.NET Framework necessário).

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;
        }
    }
}
Respondeu 26/02/2009 em 20:22
fonte usuário

votos
15

Calcule PI em tempo de compilação com D.

(Copiados a partir 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))) );
Respondeu 17/09/2008 em 18:49
fonte usuário

votos
13

Esta versão (em Delphi) é nada especial, mas é, pelo menos, mais rápido do que a versão Nick Hodge postou em seu blog :). Na minha máquina, leva cerca de 16 segundos para fazer um bilhão de iterações, dando um valor de 3,14159265 25879 (a parte exata está em negrito).

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.
Respondeu 12/01/2009 em 19:24
fonte usuário

votos
12

Se você quiser calcular uma aproximação do valor de π (por alguma razão), você deve tentar um algoritmo de extração de binário. De Bellard melhoria da BBP dá faz PI em O (n ^ 2).


Se você quiser obter uma aproximação do valor de π para fazer cálculos, então:

PI = 3.141592654

Concedido, isso é apenas uma aproximação, e não é totalmente preciso. É fora por um pouco mais de ,00000000004102. (quatro de dez-trilhonésimos, cerca de 4 / 10000000000 ).


Se você quer fazer matemática com π, em seguida, obter-se um um pacote de álgebra computacional lápis e papel ou, e usar o valor exato de π, π.

Se você realmente quer uma fórmula, este é divertido:

π = - i ln (-1)

Respondeu 22/12/2009 em 22:13
fonte usuário

votos
12

De volta aos velhos dias, com tamanhos de palavra pequenas e operações de ponto flutuante lentos ou inexistentes, estamos habituados a fazer coisas como esta:

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

Para aplicações que não exigem muita precisão (jogos de vídeo, por exemplo), isso é muito rápido e é precisa o suficiente.

Respondeu 20/02/2009 em 22:21
fonte usuário

votos
11

O método de Brent postou acima por Chris é muito bom; Brent geralmente é um gigante no campo da aritmética de precisão arbitrária.

Se tudo que você quer é o dígito Nth, a famosa fórmula BBP é útil em hexadecimal

Respondeu 04/08/2009 em 22:39
fonte usuário

votos
1

Calculando a partir da área do 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>

Respondeu 03/06/2017 em 17:13
fonte usuário

votos
0

melhor Approach

Para obter a saída de constantes padrão como pi ou os conceitos normais, devemos primeiro ir com os builtins métodos disponíveis a linguagem que você está usando. Ele irá retornar o valor da maneira mais rápida e melhor maneira também. Eu estou usando python para obter o caminho mais rápido para obter o valor de pi

  • variável pi da biblioteca de matemática . Biblioteca de matemática armazenar o pi variável como constante.

math_pi.py

import math
print math.pi

Executar o script com utilidade época do linux /usr/bin/time -v python math_pi.py

Saída:

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 arco cos método de matemática

acos_pi.py

import math
print math.acos(-1)

Executar o script com utilidade época do linux /usr/bin/time -v python acos_pi.py

Saída:

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

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

Executar o script com utilidade época do linux /usr/bin/time -v python bbp_pi.py

Saída:

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

Assim melhor maneira é usar builtins método fornecido pela causa linguagem que eles são a melhor e mais rápido para obter o resultado. Em python uso math.pi

Respondeu 18/06/2018 em 10:07
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more