문제

개인적인 도전으로 π의 가치를 가장 빠르게 구할 수 있는 방법을 찾고 있습니다.좀 더 구체적으로 말하면, 나는 사용을 포함하지 않는 방법을 사용하고 있습니다. #define 같은 상수 M_PI, 또는 숫자를 하드 코딩합니다.

아래 프로그램은 내가 알고 있는 다양한 방법을 테스트합니다.인라인 어셈블리 버전은 이론적으로 가장 빠른 옵션이지만 분명히 이식 가능하지는 않습니다.다른 버전과 비교하기 위해 이를 기준으로 포함시켰습니다.내 테스트에서 내장 기능은 4 * atan(1) 버전은 GCC 4.2에서 가장 빠릅니다. atan(1) 상수로.와 함께 -fno-builtin 지정된 atan2(0, -1) 버전이 가장 빠릅니다.

주요 테스트 프로그램은 다음과 같습니다(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;
}

그리고 인라인 어셈블리 항목(fldpi.c) x86 및 x64 시스템에서만 작동합니다.

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

그리고 테스트 중인 모든 구성을 빌드하는 빌드 스크립트(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

다양한 컴파일러 플래그 간 테스트(최적화가 다르기 때문에 32비트와 64비트도 비교했습니다) 외에도 테스트 순서를 바꿔 보았습니다.그러나 여전히, atan2(0, -1) 버전은 여전히 ​​매번 맨 위에 나옵니다.

도움이 되었습니까?

해결책

그만큼 몬테카를로 방식, 언급한 바와 같이 몇 가지 훌륭한 개념을 적용하지만 분명히 가장 빠르지도 않고, 장기적으로도 아니고, 합리적인 척도도 아닙니다.또한 그것은 당신이 찾고 있는 정확성의 종류에 따라 달라집니다.내가 아는 가장 빠른 π는 숫자가 하드 코딩된 것입니다.보고 파이 그리고 파이[PDF], 수식이 많이 있습니다.

다음은 반복당 약 14자리로 빠르게 수렴하는 방법입니다. PiFast, 현재 가장 빠른 애플리케이션인 는 FFT와 함께 이 공식을 사용합니다.코드는 간단하므로 공식만 작성하겠습니다.이 공식은 거의 발견되었습니다. Ramanujan과 Chudnovsky가 발견했습니다..실제로 그가 수십억 자릿수의 숫자를 계산한 방식이므로 무시할 수 있는 방법은 아니다.공식은 빠르게 오버플로될 것이며 계승을 나누기 때문에 이러한 계산을 지연하여 항을 제거하는 것이 유리할 것입니다.

enter image description here

enter image description here

어디,

enter image description here

아래는 브렌트-살라민 알고리즘.Wikipedia에서는 다음과 같이 언급합니다. 그리고 그러면 "충분히 가깝다" (a + b)² / 4t π의 근사값이 됩니다."충분히 가깝다"는 것이 무엇을 의미하는지 잘 모르겠지만 내 테스트에서 한 번의 반복은 2자리, 두 번은 7, 세 번은 15를 얻었습니다. 물론 이것은 복식이므로 표현에 따라 오류가 있을 수 있습니다. 그만큼 진실 계산이 더 정확할 수 있습니다.

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)

마지막으로 파이골프(800자리)는 어떠세요?160자!

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

다른 팁

나는 이 프로그램을 정말 좋아하는데, 그 이유는 자신의 면적을 보고 π에 가까워지기 때문입니다.

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

다음은 제가 고등학교 때 배운 파이 계산 기술에 대한 일반적인 설명입니다.

제가 이것을 공유하는 이유는 이 방법이 누구나 무한정 기억할 수 있을 만큼 간단하고 "몬테카를로" 방법의 개념을 가르쳐주기 때문입니다. 몬테카를로 방법은 즉각적으로 답이 나오지 않는 통계적 방법입니다. 무작위 과정을 통해 추론할 수 있습니다.

정사각형을 그리고 그 정사각형 내부에 사분면(반원의 1/4)을 새깁니다(반경이 정사각형의 변과 같으므로 정사각형을 최대한 많이 채웁니다).

이제 사각형에 다트를 던지고 그것이 어디에 떨어지는지 기록하십시오. 즉, 사각형 내부 아무 곳에서나 임의의 지점을 선택하십시오.물론 정사각형 안쪽에 착지했지만 반원 안쪽인가요?이 사실을 기록해 보세요.

이 과정을 여러 번 반복하면 반원 내부의 점 수와 던진 총 수의 비율이 있음을 알 수 있습니다. 이 비율을 x라고 합니다.

정사각형의 넓이는 r 곱하기 r이므로, 반원의 넓이는 x 곱하기 r 곱하기 r(즉, x 곱하기 r 제곱)이라고 추론할 수 있습니다.따라서 x 곱하기 4는 파이를 제공합니다.

이는 빠른 사용 방법이 아닙니다.하지만 이는 몬테카를로 방법의 좋은 예입니다.그리고 주위를 둘러보면 컴퓨터 능력 이외의 많은 문제가 이러한 방법으로 해결될 수 있다는 것을 알게 될 것입니다.

완전성을 위해 최적화된 빌드를 위해 컴파일 타임에 PI의 근사치를 계산하고 단일 값으로 인라인되는 C++ 템플릿 버전입니다.

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

I > 10인 경우 최적화되지 않은 실행의 경우에도 마찬가지로 최적화된 빌드가 느려질 수 있습니다.12번의 반복 동안 (메모가 없는 경우) value()에 대한 호출이 약 80,000번 있다고 생각합니다.

실제로 (무엇보다도) 다음과 같은 내용을 다룬 책 전체가 있습니다. 빠른 \pi 계산 방법:Jonathan Borwein과 Peter Borwein의 'Pi와 AGM'(아마존에서 구매 가능).

저는 AGM 및 관련 알고리즘을 꽤 많이 연구했습니다.꽤 흥미롭습니다(때때로 사소하지는 않지만).

\pi를 계산하기 위한 가장 현대적인 알고리즘을 구현하려면 다중 정밀도 산술 라이브러리(GMP 꽤 좋은 선택이지만 마지막으로 사용한 지 꽤 됐습니다).

최고의 알고리즘의 시간 복잡도는 O(M(n)log(n))입니다. 여기서 M(n)은 두 n 비트 정수의 곱셈에 대한 시간 복잡도입니다(M(n)=O(n) \pi의 숫자를 계산할 때 일반적으로 필요한 FFT 기반 알고리즘을 사용하는 log(n) log(log(n))), 이러한 알고리즘은 GMP에서 구현됩니다.

알고리즘 이면의 수학이 사소하지 않더라도 알고리즘 자체는 일반적으로 몇 줄의 의사 코드이며 구현은 일반적으로 매우 간단합니다(자신의 다중 정밀도 산술을 작성하지 않기로 선택한 경우 :-)).

다음 답변 최소한의 컴퓨팅 노력으로 가장 빠른 방법으로 이를 수행하는 방법을 정확하게 설명합니다..대답이 마음에 들지 않더라도 그것이 실제로 PI의 가치를 얻는 가장 빠른 방법이라는 것을 인정해야 합니다.

그만큼 가장 빠른 Pi의 값을 얻는 방법은 다음과 같습니다.

1) 좋아하는 프로그래밍 언어를 선택했습니다. 2) 수학 라이브러리를로드하고 PI가 이미 정의되어 있음을 알게됩니다.

수학 라이브러리가 없는 경우..

그만큼 두 번째로 빠름 방법 (보다 보편적인 솔루션)은 다음과 같습니다.

인터넷에서 Pi를 찾아보세요.여기:

http://www.evandersson.com/pi/digits/1000000 (100만 자리..부동 소수점 정밀도는 얼마입니까?)

아니면 여기:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

아니면 여기:

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

사용하려는 정밀 연산에 필요한 숫자를 찾는 것은 정말 빠르며, 상수를 정의함으로써 귀중한 CPU 시간을 낭비하지 않도록 할 수 있습니다.

이것은 부분적으로 유머러스한 대답일 뿐만 아니라 실제로 누군가가 실제 응용 프로그램에서 Pi의 가치를 계산한다면 ..그것은 CPU 시간을 상당히 낭비하는 일이겠죠, 그렇죠?적어도 나는 이것을 다시 계산하려는 실제 응용 프로그램을 보지 못했습니다.

친애하는 중재자:OP가 다음과 같이 질문했습니다."PI의 가치를 얻는 가장 빠른 방법"

그만큼 BBP 공식 이전 n-1 숫자를 먼저 계산할 필요 없이 n번째 숫자를 2진수(또는 16)로 계산할 수 있습니다. :)

pi를 상수로 정의하는 대신 나는 항상 다음을 사용합니다. acos(-1).

완전성을 위해 여기에 있어야 하는 다음을 발견했습니다.

Piet에서 PI 계산

프로그램을 더 크게 만들어 정밀도를 향상시킬 수 있다는 다소 좋은 특성이 있습니다.

여기언어 자체에 대한 통찰력

만약에 이 기사 사실이라면 벨라드가 만든 알고리즘 가장 빠른 것 중 하나가 만들어졌습니다.그는 데스크탑 PC를 사용하여 2.7조 자리의 파이를 만들었습니다!

...그리고 그는 자신의 책을 출판했습니다 여기서 일하다

잘했어요 벨라드 씨, 당신은 개척자이군요!

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

이것은 구현하기가 매우 쉬운 "전통적인" 방법입니다.Python(그리 빠르지는 않은 언어)으로 구현하면 다음과 같습니다.

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)

더 많은 정보를 확인하실 수 있습니다 여기.

어쨌든 Python에서 원하는 만큼 정확한 pi 값을 얻는 가장 빠른 방법은 다음과 같습니다.

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

여기에 gmpy pi 메소드의 소스가 있습니다. 이 경우 코드는 주석만큼 유용하지 않다고 생각합니다.

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

편집하다: 잘라내기 및 붙여넣기 및 식별에 문제가 있었습니다. 어쨌든 소스를 찾을 수 있습니다. 여기.

가장 빠르다는 것이 코드를 입력하는 것이 가장 빠르다는 뜻이라면 다음과 같습니다. 골프 스크립트 해결책:

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

기계와 같은 공식을 사용하세요

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.

예를 들어 Scheme에서 구현되었습니다.

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

근사치를 사용하려는 경우, 355 / 113 6자리 십진수에 적합하며 정수 표현식과 함께 사용할 수 있다는 추가 이점이 있습니다.요즘에는 "부동 소수점 수학 보조 프로세서"가 더 이상 의미가 없기 때문에 그다지 중요하지 않지만 한때는 꽤 중요했습니다.

복식의 경우:

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

이는 소수점 이하 14자리까지 정확하며 이중을 채우기에 충분합니다(부정확성은 아마도 아크 탄젠트의 나머지 소수가 잘렸기 때문일 수 있습니다).

그리고 Seth는 3.14159265358979323846입니다.3, 64가 아닙니다.

D를 사용하여 컴파일 타임에 PI를 계산합니다.

(에서 복사됨 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))) );

파이는 정확히 3이다![교수.프링크(심슨)]

농담입니다. 하지만 C#으로 작성된 내용이 있습니다(.NET-Framework 필요).

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

이 버전(Delphi)은 특별한 것은 아니지만 적어도 다음 버전보다 빠릅니다. Nick Hodge가 자신의 블로그에 게시한 버전 :).내 컴퓨터에서는 10억 번의 반복을 수행하는 데 약 16초가 걸리며, 3.1415926525879 (정확한 부분은 굵은 글씨)

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.

예전에는 단어 크기가 작고 부동 소수점 연산이 느리거나 존재하지 않았기 때문에 다음과 같은 작업을 수행했습니다.

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

많은 정밀도가 필요하지 않은 애플리케이션(예: 비디오 게임)의 경우 이는 매우 빠르고 충분히 정확합니다.

당신이 원한다면 계산하다 어떤 이유로든 π 값의 근사값을 얻으려면 이진 추출 알고리즘을 시도해야 합니다. 벨라드의 개선 BBP O(N^2)에서 PI를 제공합니다.


당신이 원한다면 얻다 계산을 수행하기 위한 π 값의 근사값은 다음과 같습니다.

PI = 3.141592654

물론 이는 대략적인 것일 뿐이고 완전히 정확하지는 않습니다.0.00000000004102보다 조금 더 차이가 납니다.(4/10조, 약 4/10,000,000,000).


하고 싶다면 수학 π를 사용하는 경우 연필과 종이 또는 컴퓨터 대수학 패키지를 가져와 π의 정확한 값인 π를 사용하십시오.

정말 공식을 원한다면 다음이 재미있을 것입니다.

π = - ln(-1)

위에 Chris가 게시한 Brent의 방법은 매우 좋습니다.브렌트는 일반적으로 임의 정밀도 산술 분야의 거인입니다.

당신이 원하는 것이 N번째 숫자뿐이라면, 그 유명한BBP 공식16진수에서 유용하다

원 면적에서 π 계산하기 :-)

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

더 나은 접근 방식

다음과 같은 표준 상수의 출력을 얻으려면 파이 또는 표준 개념을 사용하려면 먼저 사용 중인 언어에서 사용할 수 있는 내장 메서드를 사용해야 합니다.가장 빠른 방법과 가장 좋은 방법으로 가치를 반환합니다.pi 값을 얻는 가장 빠른 방법을 얻기 위해 Python을 사용하고 있습니다.

  • 수학 라이브러리의 pi 변수.수학 라이브러리는 변수 pi를 상수로 저장합니다.

math_pi.py

import math
print math.pi

Linux의 시간 유틸리티를 사용하여 스크립트 실행 /usr/bin/time -v python math_pi.py

산출:

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
  • Arc Cos 수학 방법을 사용하세요.

acos_pi.py

import math
print math.acos(-1)

Linux의 시간 유틸리티를 사용하여 스크립트 실행 /usr/bin/time -v python acos_pi.py

산출:

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

Linux의 시간 유틸리티를 사용하여 스크립트 실행 /usr/bin/time -v python bbp_pi.py

산출:

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

따라서 가장 좋은 방법은 언어에서 제공하는 내장 방법을 사용하는 것입니다. 왜냐하면 출력을 얻는 것이 가장 빠르고 가장 좋기 때문입니다.파이썬에서는 math.pi를 사용하세요.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top