파이 계산이 정확한지 어떻게 확인합니까?

파이 계산이 정확한지 어떻게 확인합니까?

---

파이의 숫자를 순차적으로주는 프로그램을 구현하기 위해 다양한 방법을 시도하고있었습니다. Taylor 시리즈 방법을 시도했지만 매우 느리게 수렴하는 것으로 나타났습니다 (시간이 지난 후 결과를 온라인 값과 비교했을 때). 어쨌든 더 나은 알고리즘을 시도하고 있습니다.

따라서 프로그램을 작성하는 동안 모든 알고리즘과 마찬가지로 문제가 발생했습니다. n계산 한 숫자가 정확한지 어떻게 알 수 있습니까?

---

나는 현재 파이의 가장 많은 자리에 대한 세계 기록 보유자이므로 2 센트를 더할 것입니다 .

실제로 새로운 세계 기록을 설정하지 않는 한 일반적인 관행은 알려진 값에 대해 계산 된 숫자를 확인하는 것입니다. 그래서 그것은 충분히 간단합니다.

사실, 나는 그들에 대한 계산을 검증 할 목적으로 숫자의 스 니펫을 나열하는 웹 페이지를 가지고 있습니다 : http://www.numberworld.org/digits/Pi/

---

그러나 세계 기록 영토에 들어가면 비교할 것이 없습니다.

역사적으로 계산 된 숫자가 올바른지 확인하기위한 표준 접근 방식은 두 번째 알고리즘을 사용하여 숫자를 다시 계산하는 것입니다. 따라서 계산이 잘못되면 끝에있는 숫자가 일치하지 않습니다.

이것은 일반적으로 필요한 시간의 두 배 이상을 수행합니다 (보통 두 번째 알고리즘이 더 느리기 때문에). 그러나 미지의 영역 인 미지의 영역으로 방황 한 후 계산 된 숫자를 확인하는 유일한 방법은 전례없는 숫자와 새로운 세계 기록입니다.

---

슈퍼 컴퓨터가 기록을 세웠던 시절에는 두 가지 다른 AGM 알고리즘 이 일반적으로 사용되었습니다.

• Gauss–Legendre 알고리즘
• Borwein의 알고리즘

둘 다 O(N log(N)^2)구현하기가 매우 쉬운 알고리즘입니다.

그러나 요즘은 상황이 조금 다릅니다. 지난 3 개의 세계 기록에서 두 번의 계산을 수행하는 대신 가장 빠른 알려진 공식 ( Chudnovsky Formula )을 사용하여 하나의 계산 만 수행했습니다 .

이 알고리즘은 구현하기가 훨씬 어렵지만 AGM 알고리즘보다 훨씬 빠릅니다.

그런 다음 숫자 추출을위한 BBP 공식을 사용하여 이진수를 확인합니다 .

이 공식을 사용하면 앞에있는 모든 자릿수 를 계산 하지 않고 임의의 이진수를 계산할 수 있습니다 . 따라서 마지막으로 계산 된 이진수 몇 개를 확인하는 데 사용됩니다. 따라서 전체 계산보다 훨씬 빠릅니다.

이것의 장점은 다음과 같습니다.

1. 값 비싼 계산은 하나만 필요합니다.

단점은 다음과 같습니다.

1. BBP ( Bailey–Borwein–Plouffe ) 공식 의 구현 이 필요합니다.
2. 2 진수에서 10 진수로의 기수 변환을 확인하려면 추가 단계가 필요합니다.

_{마지막 몇 자리를 확인하는 것이 모든 숫자가 정확하다는 것을 의미하는 이유에 대해 자세히 설명했습니다. 그러나 계산 오류가 마지막 숫자로 전파되기 때문에 쉽게 알 수 있습니다.}

---

이제이 마지막 단계 (변환 확인)는 실제로 상당히 중요합니다. 이전 세계 기록 보유자 중 한 명이 실제로 우리를 불렀습니다 . 처음에는 그것이 어떻게 작동하는지에 대한 충분한 설명을 제공하지 않았기 때문입니다.

그래서 내 블로그에서이 스 니펫을 가져 왔습니다.

N = # of decimal digits desired
p = 64-bit prime number

밑이 10 인 산술을 사용하여 A를 계산하고 이진 산술을 사용하여 B를 계산합니다.

이면 A = B"매우 높은 확률"이있는 경우 변환이 정확합니다.

---

자세한 내용은 내 블로그 게시물 Pi-5 Trillion Digits를 참조하십시오 .

---

의심 할 여지없이, 귀하의 목적을 위해 (내가 프로그래밍 연습 일 뿐이라고 가정합니다) 가장 좋은 방법은 웹에서 pi 숫자 목록과 비교하여 결과를 확인하는 것입니다.

And how do we know that those values are correct? Well, I could say that there are computer-science-y ways to prove that an implementation of an algorithm is correct.

More pragmatically, if different people use different algorithms, and they all agree to (pick a number) a thousand (million, whatever) decimal places, that should give you a warm fuzzy feeling that they got it right.

Historically, William Shanks published pi to 707 decimal places in 1873. Poor guy, he made a mistake starting at the 528th decimal place.

Very interestingly, in 1995 an algorithm was published that had the property that would directly calculate the nth digit (base 16) of pi without having to calculate all the previous digits!

Finally, I hope your initial algorithm wasn't pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... That may be the simplest to program, but it's also one of the slowest ways to do so. Check out the pi article on Wikipedia for faster approaches.

---

You could use multiple approaches and see if they converge to the same answer. Or grab some from the 'net. The Chudnovsky algorithm is usually used as a very fast method of calculating pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

---

The Taylor series is one way to approximate pi. As noted it converges slowly.

The partial sums of the Taylor series can be shown to be within some multiplier of the next term away from the true value of pi.

Other means of approximating pi have similar ways to calculate the max error.

We know this because we can prove it mathematically.

---

You could try computing sin(pi/2) (or cos(pi/2) for that matter) using the (fairly) quickly converging power series for sin and cos. (Even better: use various doubling formulas to compute nearer x=0 for faster convergence.)

BTW, better than using series for tan(x) is, with computing say cos(x) as a black box (e.g. you could use taylor series as above) is to do root finding via Newton. There certainly are better algorithms out there, but if you don't want to verify tons of digits this should suffice (and it's not that tricky to implement, and you only need a bit of calculus to understand why it works.)

참고URL : https://stackoverflow.com/questions/14283270/how-do-i-determine-whether-my-calculation-of-pi-is-accurate