π 값을 얻는 가장 빠른 방법은 무엇입니까?
https://stackoverflow.com/questions/19
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
개인적인 도전으로 π의 가치를 얻을 수있는 가장 빠른 방법을 찾고 있습니다. 더 구체적으로, 저는 #define와 같은 M_PI 상수를 사용하거나 숫자를 하드 코딩하지 않는 방법을 사용하고 있습니다.
아래 프로그램은 내가 아는 다양한 방법을 테스트합니다. 인라인 어셈블리 버전은 이론상 가장 빠른 옵션이지만 이식성이 분명하지는 않습니다. 다른 버전과 비교하기위한 기준으로 포함 시켰습니다. 내 테스트에서 내장 된 genracodicetagcode 버전은 4 * atan(1)를 상수로 자동 접기 때문에 GCC 4.2에서 가장 빠릅니다. atan(1)를 지정하면 -fno-builtin 버전이 가장 빠릅니다.
다음은 주요 테스트 프로그램 (atan2(0, -1))입니다.
라코 디스
x86 및 x64 시스템에서만 작동하는 인라인 어셈블리 (pitimes.c) :
라코 디스
테스트중인 모든 구성을 빌드하는 빌드 스크립트 (fldpi.c) :
라코 디스
다양한 컴파일러 플래그 간의 테스트 (최적화가 다르기 때문에 32 비트와 64 비트도 비교했습니다)와 별도로 테스트 순서를 전환 해 보았습니다. 하지만 여전히 genracodicetagcode 버전이 매번 맨 위에 나옵니다.
해결책
Monte Carlo 방법 은 앞서 언급했듯이 몇 가지 훌륭한 개념을 적용하지만 분명히 가장 빠른 것도 아니고, 장거리도 아니고, 합리적인 조치도 아닙니다. 또한, 그것은 모두 당신이 찾고있는 정확도의 종류에 달려 있습니다. 내가 아는 가장 빠른 π는 숫자가 하드 코딩 된 것입니다. Pi 및 Pi [PDF] 에는 많은 공식이 있습니다.
다음은 빠르게 수렴하는 방법입니다. 반복 당 약 14 자리 숫자입니다. 현재 가장 빠른 애플리케이션 인 PiFast 는이 공식을 사용합니다. FFT로. 코드가 간단하므로 공식을 작성하겠습니다. 이 공식은 Ramanujan에 의해 거의 발견되었으며 Chudnovsky에서 발견했습니다 . 실제로 그가 수십억 자릿수를 계산 한 방법이므로 무시할 수있는 방법이 아닙니다. 공식은 빠르게 넘칠 것이며 계승을 나누기 때문에 항을 제거하기 위해 그러한 계산을 지연시키는 것이 유리할 것입니다.
어디
아래는 Brent–Salamin 알고리즘 입니다. Wikipedia는 a 와 b 가 "충분히 가까우면" (a + b) ² / 4t 가 π의 근사치가된다고 언급합니다. "충분히 가까움"이 무엇을 의미하는지 잘 모르겠지만 테스트에서 한 번의 반복은 2 자리, 2 번은 7, 3 번은 15입니다. 물론 이것은 복식이므로 그 표현에 따라 오류가있을 수 있습니다. 실제 계산이 더 정확할 수 있습니다. 라코 디스
마지막으로 파이 골프 (800 자리)는 어떻습니까? 160 자! 라코 디스
다른 팁
저는이 프로그램이 자신의 영역을보고 π에 가깝기 때문에 정말 마음에 듭니다.
IOCCC 1988 : westley.c <인용구> 라코 디스
다음은 내가 고등학교에서 배운 파이 계산 기술에 대한 일반적인 설명입니다.
누구나 무기한 기억할 수있을 정도로 간단하다고 생각하기 때문에 공유합니다. 또한 "Monte-Carlo"방법의 개념을 알려줍니다. 즉, 즉시 답변에 도달하는 통계적 방법입니다. 무작위 프로세스를 통해 추론 할 수있는 것처럼 보입니다.
정사각형을 그리고 그 정사각형 안에 사분면 (반원의 1/4)을 새기십시오 (반지름이 정사각형의 변과 같으므로 가능한 한 많은 정사각형을 채우도록 함)
이제 정사각형에 다트를 던지고 착지 위치를 기록합니다. 즉, 정사각형 내부의 임의의 지점을 선택합니다. 물론 정사각형 내부에 착륙했지만 반원 내부에 있습니까? 이 사실을 기록하십시오.
이 과정을 여러 번 반복하면 반원 안에있는 포인트 수와 던진 총 수의 비율이 있음을 알 수 있습니다.이 비율을 x라고합니다.
정사각형의 면적이 r x r이므로 반원의 면적은 x x r x r (즉, x x r 제곱)이라고 추론 할 수 있습니다. 따라서 x 곱하기 4는 파이를 제공합니다.
빠른 사용 방법이 아닙니다. 하지만 이것은 몬테카를로 방법의 좋은 예입니다. 주위를 둘러 보면 계산 능력 이외의 많은 문제가 그러한 방법으로 해결 될 수 있다는 것을 알 수 있습니다.
완벽 성을 위해 최적화 된 빌드를 위해 컴파일 타임에 PI의 근사치를 계산하고 단일 값으로 인라인되는 C ++ 템플릿 버전입니다. 라코 디스
I> 10에 대한 참고 사항, 최적화되지 않은 실행의 경우와 마찬가지로 최적화 된 빌드가 느려질 수 있습니다.12 번의 반복에서 value ()에 대한 약 80k 호출이 있다고 생각합니다 (메모리가없는 경우).
실제로는 Jonathan과 Peter Borwein ( Amazon에서 사용 가능 ).
저는 AGM 및 관련 알고리즘을 꽤 많이 연구했습니다. 꽤 흥미 롭습니다 (때로는 사소하지 않은 경우도 있음).
\ pi를 계산하기 위해 대부분의 최신 알고리즘을 구현하려면 다중 정밀도 산술 라이브러리가 필요합니다 ( GMP 는 상당히 마지막으로 사용한 지 오래되었지만 좋은 선택입니다.
최상의 알고리즘의 시간 복잡도는 O (M (n) log (n))이며, 여기서 M (n)은 두 개의 n 비트 정수를 곱하는 시간 복잡도입니다 (M (n)= O (n log (n) log (log (n))) FFT 기반 알고리즘을 사용합니다. 일반적으로 \ pi의 숫자를 계산할 때 필요하며 이러한 알고리즘은 GMP에서 구현됩니다.
알고리즘이면의 수학이 사소하지 않더라도 알고리즘 자체는 일반적으로 몇 줄의 의사 코드이며 구현은 일반적으로 매우 간단합니다 (자신 만의 다중 정밀도 산술을 작성하지 않기로 선택한 경우). )).
다음은 최소한의 컴퓨팅 노력으로 가능한 가장 빠른 방법으로이 작업을 수행하는 정확한 방법 입니다. 대답이 마음에 들지 않더라도 PI의 가치를 얻는 가장 빠른 방법이라는 것을 인정해야합니다.
Pi의 가치를 얻는 가장 빠른 방법은 다음과 같습니다.
1) 좋아하는 프로그래밍 언어 선택 2) 수학 라이브러리로드 3) Pi가 이미 정의되어 있음을 확인하십시오-사용할 준비가되었습니다!
수학 라이브러리가없는 경우 ..
두 번째로 빠른 방법 (보다 보편적 인 솔루션)은 다음과 같습니다.
인터넷에서 Pi를 찾습니다 (예 : 여기 :
http://www.eveandersson.com/pi/digits/1000000 (백만 자릿수 .. 부동 소수점 정밀도는 무엇입니까?)
또는 여기 :
http://3.141592653589793238462643383279502884197169399375105820974944592.com/
또는 여기 :
http://en.wikipedia.org/wiki/Pi
사용하려는 정밀 산술에 필요한 자릿수를 찾는 것은 정말 빠르며 상수를 정의하여 귀중한 CPU 시간을 낭비하지 않도록 할 수 있습니다.
이것은 부분적으로 유머러스 한 대답 일뿐만 아니라 실제로 누군가가 진행하여 실제 응용 프로그램에서 Pi의 값을 계산한다면 CPU 시간을 상당히 낭비하게 될 것입니다. 적어도 나는 이것을 재 계산하려는 실제 응용 프로그램을 보지 못했습니다.
운영자님께 : OP에서 "PI의 가치를 얻는 가장 빠른 방법"을 물었다는 점에 유의하세요.
BBP 공식 을 사용하면 n 번째 숫자를 2 진수로 계산할 수 있습니다.(또는 16)-이전 n-1 자리를 먼저 신경 쓰지 않아도됩니다. :)
pi를 상수로 정의하는 대신 항상 acos(-1)를 사용합니다.
완전성을 위해 여기에 있어야하는 다음 항목을 발견했습니다.
정밀도가 향상되어 프로그램을 더 크게 만들 수 있다는 점이 다소 좋은 특성이 있습니다.
여기 는 언어 자체에 대한 몇 가지 통찰력입니다.
가장 빠르다고해서 코드를 입력하는 것이 가장 빠르다는 것을 의미한다면 다음은 golfscript 솔루션입니다.: 라코 디스
Machin과 유사한 공식 사용 라코 디스
Schema에서 구현 됨 :
(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))
근사치를 사용하려는 경우 genracodicetagcode는 6 자리 십진수에 적합하며 정수 표현식과 함께 사용할 수 있다는 추가 이점이 있습니다.요즘에는 "부동 소수점 수학 보조 프로세서"가 의미가 없어 졌기 때문에 그다지 중요하지 않지만 한 번은 상당히 중요했습니다.
복식 포함 : 라코 디스
이는 소수점 이하 14 자리까지 정확하며 이중을 채우기에 충분합니다 (아크 탄젠트의 나머지 소수가 잘 렸기 때문에 부정확 할 수 있습니다).
또한 Seth는 64가 아닌 3.14159265358979323846 3 입니다.
D로 컴파일 타임에 PI를 계산합니다.
( DSource.org 에서 복사 됨)) 라코 디스
Pi는 정확히 3입니다![Prof.Frink (Simpsons)]
농담,하지만 여기 C #에서 하나가 있습니다 (.NET-Framework 필요). 라코 디스
이 버전 (Delphi)은 특별한 것은 아니지만 최소한 Nick Hodge가 블로그에 게시 한 버전 :).내 컴퓨터에서 10 억 번 반복하는 데 약 16 초가 걸리며 값은 3.14159265 25879입니다 (정확한 부분은 굵게 표시됨). 라코 디스
예전에는 작은 단어 크기와 느리거나 존재하지 않는 부동 소수점 연산으로 다음과 같은 작업을 수행했습니다. 라코 디스
정밀도가 많이 필요하지 않은 애플리케이션 (예 : 비디오 게임)의 경우 매우 빠르며 충분히 정확합니다.
어떤 이유로 π 값의 근사치를 계산 하려면 이진 추출 알고리즘을 시도해야합니다. Bellard의 BBP 는 O (N ^ 2)에서 PI를 제공합니다. <시간>
계산을 수행하기 위해 π 값의 근사치를 얻으려면 다음을 수행하십시오. 라코 디스
확실히 이것은 근사치이며 완전히 정확하지는 않습니다.0.00000000004102보다 조금 더 떨어져 있습니다.(4 조 1 조, 약 4 / 10,000,000,000 ) <시간>
π로 수학 을하고 싶다면 연필과 종이 또는 컴퓨터 대수 패키지를 준비하고 π의 정확한 값인 π를 사용하세요.
정말로 공식을 원한다면이 방법은 재미 있습니다.
π=- i ln (-1)
Chris가 위에 게시 한 Brent의 방법은 매우 좋습니다.Brent는 일반적으로 임의 정밀도 산술 분야에서 거인입니다.
원하는 모든 것이 N 번째 자리이면 유명한 BBP 공식 16 진수에서 유용합니다
원형 영역에서 π 계산 :-)
더 나은 접근 방식
pi 또는 표준 개념과 같은 표준 상수의 출력을 얻으려면 먼저 사용중인 언어에서 사용할 수있는 내장 메서드를 사용해야합니다. 가장 빠른 방법과 가장 좋은 방법으로 값을 반환합니다. 파이 값을 얻는 가장 빠른 방법을 얻기 위해 파이썬을 사용하고 있습니다
- 수학 라이브러리의 pi 변수 . 수학 라이브러리는 변수 pi를 상수로 저장합니다.
math_pi.py 라코 디스
linux
/usr/bin/time -v python math_pi.py의 시간 유틸리티로 스크립트 실행출력 : 라코 디스
- 아크 코스 수학 방법 사용
acos_pi.py 라코 디스
linux
/usr/bin/time -v python acos_pi.py의 시간 유틸리티로 스크립트 실행출력 : 라코 디스
- 아크 코스 수학 방법 사용