Qual é a maneira mais rápida de obter o valor de p?
https://stackoverflow.com/questions/19
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou procurando a maneira mais rápida para obter o valor de p, como um desafio pessoal. Mais especificamente, eu estou usando formas que não envolvem o uso de constantes #define como M_PI, ou embutir o número.
O programa abaixo testes 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 versão 4 * atan(1) é mais rápido no GCC 4.2, porque auto-dobra o atan(1) em uma constante. Com -fno-builtin especificado, a versão atan2(0, -1) é mais rápido.
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 só irá funcionar 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 várias bandeiras do compilador (Eu comparei 32-bit contra 64-bit também porque as otimizações são diferentes), eu também tentei mudar a ordem dos testes ao redor. Mas ainda assim, a versão atan2(0, -1) ainda sai por cima de cada vez.
Solução
O Monte Carlo método , 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ápido p 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 para ignorar. A fórmula vai transbordar rapidamente e, já que estamos dividindo fatoriais, seria vantajoso, em seguida, para atrasar esses cálculos para remover termos.
onde,
Abaixo está a Brent-Salamin algoritmo . Wikipedia menciona que quando a e b são "suficientemente próximo", em seguida, (a + b) ² / 4t será uma aproximação de p. Eu não tenho certeza o que "perto o suficiente" meios, mas dos 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 true 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, como sobre alguns golf 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);}
Outras dicas
Eu realmente gosto deste programa, porque aproxima p, 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() { _-_-_-_ _-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_ _-_-_-_ }
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 é o suficiente 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 fazer imediatamente parecem ser dedutível por meio 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 lugar ponto aleatório dentro do quadrado. 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
.Uma vez que a área do quadrado é 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.
No interesse da integridade, uma versão template C ++, o que, para uma compilação otimizada, irá calcular uma aproximação da 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 80 mil chamadas para valor () (na ausência de memoisation).
Na verdade, há um livro inteiro dedicado (entre outras coisas) a rápido 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 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 que, apesar da 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: - )).
As seguintes respostas exatamente como fazer isso da maneira mais rápida possível - com o menor esforço computacional . Mesmo se você não gosta da resposta, você tem que admitir que é realmente a maneira mais rápida para obter o valor de PI.
O O MAIS RÁPIDO maneira de obter o valor de Pi é:
1) escolheu a sua linguagem de programação favorita 2) Coloque a sua biblioteca de matemática 3) e achar que Pi já está definido há - pronto para uso
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.
Este não é apenas uma resposta em parte 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: nota por favor que o OP perguntou: "maneira mais rápida para obter o valor de PI"
O BBP fórmula permite calcular o dígito enésimo - em base 2 (ou 16) - sem ter de se preocupar com os mesmo n-1 anteriores dígitos primeiro:)
Em vez de definir pi como uma constante, eu sempre uso acos(-1).
Apenas veio este que deveria estar aqui para ser completo:
Tem a propriedade bastante agradável que a precisão pode ser melhorada tornando o programa maior.
Aqui 's algumas dicas sobre o próprio
IdiomaSe este artigo é 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!
Este é um método "clássico", muito fácil de implementar. Esta implementação, em python (linguagem não tão rápido) faz isso:
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 preciso como-muito-como-você-quer valor de 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 corte e cole e identation, de qualquer maneira você pode encontrar a fonte aqui .
Se por mais rápido que você quer dizer mais rápida de digitar o código, aqui está a solução golfscript :
;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Use a Machin-like fórmula
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))))
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 já foi muito importante.
Com duplas:
4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))
Este será até precisas para 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).
Além disso Seth, é 3,14159265358979323846 3 , não 64.
Calcular PI em tempo de compilação com D.
(Copiado 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))) );
Pi é exatamente 3! [Prof. Frink (Simpsons)]
Joke, 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;
}
}
}
Esta versão (em Delphi) é nada especial, mas é, pelo menos, mais rápido do que a versão Nick Hodge postou em seu blogue :). 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.
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 é bastante preciso.
Se você quiser compute uma aproximação do valor de p (por alguma razão), você deve tentar um algoritmo de extração de binário. melhoria do Bellard de BBP dá faz PI em O (N ^ 2).
Se você quiser obter uma aproximação do valor de p para fazer cálculos, então:
PI = 3.141592654
Com certeza, 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 p, em seguida, obter-se um um pacote de álgebra computacional lápis e papel ou e valor exato uso do p, p.
Se você realmente quer uma fórmula, este é divertimento:
p = - i ln (-1)
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, o famoso fórmula BBP é útil em hex
Cálculo de p 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 += " "
}
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>
Melhor Approach
Para obter o resultado 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 loja do pi variável como constante.
math_pi.py
import math
print math.pi
Execute o script com a utilidade época do linux /usr/bin/time -v python math_pi.py
Output:
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 com arco cos de matemática
acos_pi.py
import math
print math.acos(-1)
Execute o script com a utilidade época do linux /usr/bin/time -v python acos_pi.py
Output:
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
- usar BBP fórmula
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))
Execute o script com a utilidade época do linux /usr/bin/time -v python bbp_pi.py
Output:
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 linguagem porque eles são o mais rápido e melhor para obter a saída. Em uso python math.pi