π의 가치를 얻는 가장 빠른 방법은 무엇입니까?
개인적 도전으로 π의 가치를 얻는 가장 빠른 방법을 찾고 있습니다. 보다 구체적으로, 나는 #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.cx86 및 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에 의해 발견되었습니다 . 실제로 그는 수십억 자리의 숫자를 계산 한 방식이므로 무시할 방법이 아닙니다. 수식은 빠르게 오버플로되며 계승을 나누기 때문에 이러한 계산을 지연시켜 항을 제거하는 것이 유리합니다.
어디,
아래는 브렌트-살라 민 알고리즘 입니다. Wikipedia는 a 와 b 가 "충분히 가까이"있을 때 (a + b) ² / 4t 는 π의 근사치 라고 언급합니다 . 나는 "충분히 근접하다"는 것이 무엇인지 확실하지 않지만, 테스트에서 하나의 반복은 2 자리, 2는 7, 3은 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() { _-_-_-_ _-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_ _-_-_-_ }
다음은 고등학교에서 배운 파이를 계산하는 기술에 대한 일반적인 설명입니다.
나는 누군가가 그것을 영원히 기억할 수있을 정도로 단순하다고 생각하기 때문에 이것을 공유 할뿐 아니라 "몬테카를로 (Monte-Carlo)"방법의 개념을 알려줍니다. 즉, 즉시 나타나지 않는 답변에 도달하는 통계적 방법입니다. 임의의 프로세스를 통해 공제 가능합니다.
정사각형을 그리고 그 정사각형 내부에 사분면 (반원의 1/4)을 기입하십시오 (사각의 측면과 같은 반경을 갖는 사분면은 가능한 많은 정사각형을 채 웁니다)
이제 사각형에 다트를 던지고 그것이 어디에 착륙했는지 기록하십시오. 즉, 사각형 안의 임의의 지점을 선택하십시오. 물론, 그것은 사각형 안에 착륙했지만 반원 안에 있습니까? 이 사실을 기록하십시오.
이 과정을 여러 번 반복하십시오. 반원 내부의 포인트 수 대 던진 총 수의 비율이 있음을 알 수 있습니다.이 비율을 x라고하십시오.
정사각형의 면적이 r 곱하기 r이므로, 반원의 면적이 x 곱하기 r 곱하기 r (즉, x 곱하기 r 제곱)이라고 추론 할 수 있습니다. 따라서 x 곱하기 4는 파이를 줄 것입니다.
이것은 빠른 방법이 아닙니다. 그러나 이것은 몬테 카를로 방법의 좋은 예입니다. 주변을 둘러 보면 계산 기술 이외의 많은 문제가 그러한 방법으로 해결 될 수 있습니다.
완전성을 위해 C ++ 템플릿 버전은 최적화 된 빌드를 위해 컴파일 타임에 PI의 근사값을 계산하고 단일 값으로 인라인합니다.
#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 ()에 대한 약 80k 호출이 있다고 생각합니다.
Jonathan과 Peter Borwein ( Amazon에서 사용 가능 ) 의 \ pi 계산 : 'Pi and AGM'의 빠른 방법을 다루는 책이 실제로 있습니다 .
나는 AGM과 관련 알고리즘을 꽤 많이 연구했다. 그것은 꽤 흥미 롭다 (때로는 사소하지는 않지만).
\ pi를 계산하기 위해 대부분의 최신 알고리즘을 구현하려면 다중 정밀도 산술 라이브러리가 필요합니다 ( 마지막으로 사용한 지 오래되었지만 GMP 는 좋은 선택입니다).
최상의 알고리즘의 시간 복잡도는 O (M (n) log (n))에 있으며, 여기서 M (n)은 두 n- 비트 정수의 곱셈에 대한 시간 복잡도입니다 (M (n) = O (n FFT 기반 알고리즘을 사용하여 log (n) log (log (n)))). 이는 일반적으로 \ pi의 숫자를 계산할 때 필요하며 이러한 알고리즘은 GMP로 구현됩니다.
알고리즘 뒤의 수학이 사소한 것은 아니지만 알고리즘 자체는 일반적으로 몇 줄의 의사 코드이며, 구현은 일반적으로 매우 간단합니다 (자신의 다중 정밀도 산술을 쓰지 않기로 선택한 경우 :-)).
다음 은 최소한의 컴퓨팅 노력으로 가능한 가장 빠른 방법으로이 작업을 수행하는 방법에 대한 정확한 답변 입니다. 대답이 마음에 들지 않더라도 실제로 PI의 가치를 얻는 가장 빠른 방법임을 인정해야합니다.
가장 빠른 파이의 값을 얻을 수있는 방법입니다 :
1) 좋아하는 프로그래밍 언어를 선택했습니다. 2) 수학 라이브러리를로드합니다. 3) Pi가 이미 정의되어 있음을 알 수 있습니다.
현재 수학 라이브러리가없는 경우 ..
두 번째로 빠른 방법 (보다 보편적 인 솔루션)은 다음과 같습니다.
인터넷에서 Pi를 찾아보십시오. 예를 들면 다음과 같습니다.
http://www.eveandersson.com/pi/digits/1000000 (100 만 자리 .. 부동 소수점 정밀도는 무엇입니까?)
또는 여기 :
http://3.141592653589793238462643383279502884197169399375105820974944592.com/
또는 여기 :
http://en.wikipedia.org/wiki/Pi
사용하려는 정밀 산술에 필요한 숫자를 찾는 것이 정말 빠르며 상수를 정의하여 소중한 CPU 시간을 낭비하지 않도록 할 수 있습니다.
이것은 부분적으로 유머러스 한 답변 일뿐만 아니라, 실제로 누군가가 실제 응용 프로그램에서 Pi의 가치를 계산하고 계산할 경우 CPU 시간을 상당히 낭비하는 것입니까? 적어도 이것을 다시 계산하려고하는 실제 응용 프로그램은 보이지 않습니다.
친애하는 중재자 : OP가 다음과 같이 질문했습니다. "PI의 가치를 얻는 가장 빠른 방법"
BBP 수식은 베이스 (2) (16)에서 - -는 n 번째 자릿수를 계산할 수 있도록 제 심지어 이전 N-1 자리 귀찮게하지 않고 :)
pi를 상수로 정의하는 대신 항상을 사용 acos(-1)합니다.
완성을 위해 여기에 있어야 할 것을 발견했습니다.
그것은 프로그램을 더 크게 만들어 정밀도를 향상시킬 수 있다는 다소 좋은 속성을 가지고 있습니다.
다음 은 언어 자체에 대한 통찰력입니다.
경우 이 문서는 사실, 다음 Bellard 그 알고리즘을 만들었다는 speediest 가능한 중 하나가 될 수 있습니다. 그는 데스크탑 PC를 사용하여 2.7 조 자리까지 파이를 만들었습니다!
잘 했어 Bellard, 너는 개척 자야!
http://www.theregister.co.uk/2010/01/06/very_long_pi/
이것은 구현하기 매우 쉬운 "클래식"방법입니다. 파이썬 (빠른 언어는 아님) 의이 구현은 다음을 수행합니다.
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)
어쨌든 파이썬에서 원하는만큼의 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<~\;
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.
예를 들어 Scheme에서 구현되었습니다.
(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))
근사값을 기꺼이 사용하려는 경우 355 / 11310 진수 6 자리에 적합하며 정수 표현식에 사용할 수 있다는 이점이 있습니다. "부동 소수점 연산 보조 프로세서"가 의미를 갖지 못한 것처럼 요즘 중요하지는 않지만 한 번만 중요했습니다.
복식 :
4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))
이것은 소수점 이하 14 자리까지 정확하며 이중을 채우기에 충분합니다 (아크 탄젠트의 나머지 소수점이 잘 리기 때문에 부정확 한 것일 수 있습니다).
또한 Seth는 64가 아니라 3.14159265358979323846 3 입니다.
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입니다! [교수 rink (심슨)]
농담이지만 C #에 하나 있습니다 (.NET-Framework required).
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.14159265 25879입니다 (정확한 부분은 굵게 표시됨).
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)
정밀도가 높지 않은 응용 프로그램 (예 : 비디오 게임)의 경우 매우 빠르며 충분히 정확합니다.
어떤 이유로 π 값의 근사값 을 계산 하려면 이진 추출 알고리즘을 시도해야합니다. Bellard의 BBP 개선 은 PI를 O (N ^ 2)로 나타냅니다.
계산을 위해 π 값의 근사값 을 얻으려면 다음을 수행하십시오.
PI = 3.141592654
물론, 그것은 단지 근사치이며 완전히 정확하지는 않습니다. 0.00000000004102보다 약간 벗어났습니다. (4 십억, 약 4 / 10,000,000,000 ).
π로 수학 을 하려면 연필과 종이 또는 컴퓨터 대수 패키지를 구하고 π의 정확한 값 π를 사용하십시오.
당신이 정말로 공식을 원한다면, 이것은 재미 있습니다 :
π = -i 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 += " "
}
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 또는 표준 개념 과 같은 표준 상수의 출력을 얻으려면 먼저 사용중인 언어에 사용 가능한 내장 메소드를 사용해야합니다. 가장 빠른 방법과 가장 좋은 방법으로 값을 반환합니다. 파이썬을 사용하여 파이를 얻는 가장 빠른 방법을 얻습니다.
- 수학 라이브러리의 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
- 아크 코스 계산법 사용
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 공식 사용
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를 사용하십시오.
참고 URL : https://stackoverflow.com/questions/19/what-is-the-fastest-way-to-get-the-value-of-%cf%80
'Programing' 카테고리의 다른 글
| 코드에서 WPF 이미지 소스 설정 (0) | 2020.03.11 |
|---|---|
| .NET DateTime에서 밀리 초를 자르는 방법 (0) | 2020.03.11 |
| Eclipse에서 빵 부스러기를 비활성화하는 방법 (0) | 2020.03.11 |
| 같은 창과 같은 탭에서 URL 열기 (0) | 2020.03.11 |
| 패키지 이름과 일치하는 클라이언트를 찾을 수 없습니다 (Google Analytics)-여러 productFlavors & buildTypes (0) | 2020.03.11 |