Trigonometric tables

Original article: wikipedia:Trigonometric tables

수학(mathematics)에서, 삼각 함수(trigonometric function)는 여러 영역에서 유용합니다. 포켓 계산기(pocket calculator)의 존재 전에, 삼각 테이블(trigonometric tables)은 항법(navigation), 과학(science)과 공학(engineering)에 필수적이었습니다. 수학적 테이블(mathematical table)의 계산은 연구의 중요한 분야였고, 이것은 최초의 기계 계산 장치(first mechanical computing devices)의 개발로 이어졌습니다.

최신 컴퓨터 및 포켓 계산기는, 수학적 코드의 특수 라이브러리를 사용하여, 이제 요구에 따라 삼각 함수 값을 생성합니다. 종종, 이들 라이브러리는 내부적으로 미리-계산된 테이블을 사용하고, 적절한 보간(interpolation) 방법을 사용함으로써 요구된 값을 계산합니다. 삼각 함수의 간단한 조회 테이블 보간은 여전히 컴퓨터 그래픽(computer graphics)에서 사용되며, 여기서 적당한 정확도가 요구될 수 있고 속도가 종종 가장 중요합니다.

삼각 테이블과 생성 계획의 또 다른 중요한 응용은 고속 푸리에 변환(fast Fourier transform) (FFT) 알고리듬에 대한 것이며, 여기서 (트위들 인수(twiddle factors)라고 불리는) 같은 삼각 함수 값이 주어진 변환에서 여러 번 평가되며, 특히, 공통적인 경우에서 같은 크기의 많은 변환이 계산됩니다. 이 경우에서, 매번 일반 라이브러리 루틴을 호출하는 것은 받아들일 수 없을 정도로 느립니다. 하나의 선택 사항은 라이브러리 루틴을 한번 호출하고, 요구될 그것들의 삼각 값의 테이블을 미리 작성하는 것이지만, 이것은 테이블을 저장하기 위해서 상당한 메모리를 요구합니다. 다른 가능성은, 값의 정규 수열이 필요하기 때문에, 즉석에서 삼각 값을 계산하기 위해 재귀 공식을 사용하는 것입니다. 상당한 연구가 FFT의 정확성을 유지하기 위해 정확하고, 안정적인 재귀 계획을 찾는 것에 바쳐져 왔습니다 (이것들은 삼각 오차에 매우 민감합니다).

On-demand computation

A page from a 1619 book of mathematical tables.

현대의 컴퓨터와 계산기는 임의적인 각도에 대해 삼각 함수 값을 제공하기 위해 다양한 기법을 사용합니다 (Kantabutra, 1996). 하나의 공통적인 방법은, 특히 부동-점(floating-point) 단위를 갖는 고급 프로세서에서, (체비쇼프 근사(Chebyshev approximation), 최상의 균등 근사, 및 파데 근사(Padé approximation), 및 전형적으로 더 높거나 가변 정밀도에 대해, 테일러(Taylor)와 로랑 급수(Laurent series)와 같은) 다항식(polynomial) 또는 유리(rational) 근사(approximation)를 범위 감소 및 테이블 조회와 결합하는 것입니다 – 그것들은 먼저 작은 테이블에서 가장 가까운 각도를 찾고, 그런-다음 다항식을 보정을 계산하기 위해 사용합니다. 어쨌든, 그러한 보간을 수행하는 동안 정밀도를 유지하는 것은 비-자명합니다; 갈의 정확한 테이블(Gal's accurate tables), 코디(Cody)와 웨이트(Waite) 감소, 및 페인(Payne)과 해네크(Hanek) 감소 알고리듬과 같은 방법은 이 목적에 대해 사용될 수 있습니다. 하드웨어 배수(hardware multiplier)가 없는 더 단순한 장치에서, 더 효율적인 CORDIC (마찬가지로 관련된 기법)이라고 불리는 알고리듬이 있는데, 왜냐하면 그것은 오직 이동(shift)과 덧셈을 사용하기 때문입니다. 이들 모든 방법은 성능상의 이유로 공통적으로 하드웨어(hardware)에서 구현됩니다.

삼각 함수를 근사하기 위해 사용되는 특정 다항식은 최소-최대 근사 알고리듬(minimax approximation algorithm)의 일부 근사를 사용하여 미리 생성됩니다.

매우 높은 정밀도(very high precision) 계산에 대해, 급수-전개 수렴이 너무 느리게 될 때, 삼각 함수는 산술-기하 평균(arithmetic-geometric mean)으로 근사화될 수 있으며, 이것 자체는 (복소(complex)) 타원 적분(elliptic integral)에 의해 삼각 함수에 근사합니다 (Brent, 1976).

2π의 유리(rational) 배수인 각도의 삼각 함수는 대수적 숫자(algebraic number)입니다. a/b·2π에 대해 값은 n = a에 대해 드 무아브르의 항등식(de Moivre's identity)을 b^번째 단위원의 근(root of unity)에 적용함으로써 구할 수 있으며, 이것은 역시 복소 평면(complex plane)에서 다항식 x^b - 1의 근입니다. 예를 들어, 2π ⋅ 5/37의 코사인과 사인은 단위원의 37번째 근 cos(2π/37) + sin(2π/37)i의 5번째 거듭제곱의, 각각, 실수(real)와 허수 부분(imaginary part)이며, 이것은 차수(degree))-37 다항식 x³⁷ − 1의 근입니다. 이 경우에 대해, 뉴턴의 방법(Newton's method)과 같은 근-찾는 알고리듬은 비슷한 점근적 율에서 수렴하는 동안 위의 산술-기하 평균 알고리듬보다 훨씬 더 간단합니다. 후자 알고리듬은 어쨌든 초월적(transcendental) 삼각 상수를 요구합니다.

Half-angle and angle-addition formulas

역사적으로, 삼각 테이블을 계산하는 가장 초기 방법과 컴퓨터가 등장할 때까지 아마도 가장 공통적인 방법은 (sin(π/2) = 1, cos(π/2) = 0와 같은) 알려진 값에서 시작하여 절반-각도 및 각도-덧셈 삼각 항등식(trigonometric identities)을 반복적으로 적용하는 것이었습니다. 이 방법은 고대 천문학자 프톨레마이오스(Ptolemy)에 의해 사용되었으며, 그는 Almagest, 천문학에 관한 논문에서 그것들을 유도합니다. 현대적인 형식에서, 그가 유도했던 항등식은 다음과 같이 명시됩니다 (x가 놓이는 사분면에 의해 결정되는 부호를 가집니다):

$\cos \left({\frac {x}{2}}\right)=\pm {\sqrt {{\tfrac {1}{2}}(1+\cos x)}}$

$\sin \left({\frac {x}{2}}\right)=\pm {\sqrt {{\tfrac {1}{2}}(1-\cos x)}}$

$\sin(x\pm y)=\sin(x)\cos(y)\pm \cos(x)\sin(y)\,$

$\cos(x\pm y)=\cos(x)\cos(y)\mp \sin(x)\sin(y)\,$

이것들은 프톨레마이오스의 현의 테이블(Ptolemy's table of chords)을 구성하기 위해 사용되었으며, 이것은 천문학적 문제에 적용되었습니다.

이들 항등식에 대한 다양한 다른 순열이 가능합니다: 예를 들어, 일부 초기 삼각 테이블은 사인과 코사인이 아니라 사인과 벌사인(versine)을 사용했습니다.

A quick, but inaccurate, approximation

sin(2πn/N)에 대해 N 근사 s_n과 cos(2πn/N)에 대해 N 근사 c_n의 테이블을 계산하는 것에 대해 빠르지만, 부정확한 알로리즘은 다음입니다:

s₀ = 0

c₀ = 1

s_n+1 = s_n + d × c_n

c_n+1 = c_n − d × s_n

n = 0,...,N − 1에 대해, 여기서 d = 2π/N입니다.

이것은 미분 방정식(differential equation)을 적분하는 것에 대한 간단한 오일러 방법(Euler method)입니다:

$ds/dt=c$

$dc/dt=-s$

여기서 초기 조건 s(0) = 0 및 c(0) = 1을 가지며, 그것의 해석적 해는 s = sin(t) 및 c = cos(t)입니다.

불행하게도, 이것은 사인 테이블을 생성하는 데 유용한 알고리듬이 아닌데 왜냐하면 그것은 1/N에 비례하는 상당한 오류를 가지기 때문입니다.

예를 들어, N = 256에 대해, 사인 값에서 최대 오차는 ~0.061 (−0.9757 대신에 s₂₀₂ = −1.0368)입니다. N = 1024에 대해, 사인 값에서 최대 오차는 ~0.015 (−0.97832 대신에 s₈₀₃ = −0.99321)으로, 약 4배 더 작습니다. 만약 얻어진 사인과 코사인 값이 그려져야 하면, 이 알고리듬은 원이 아닌 로그 나선을 그립니다.

A better, but still imperfect, recurrence formula

삼각 테이블을 생성하기 위한 간단한 재귀 공식은 오일러의 공식(Euler's formula)과 다음 관계를 기반으로 합니다:

$e^{i(\theta +\Delta )}=e^{i\theta }\times e^{i\Delta \theta }$

이것은 위에서 처럼 삼각 값 s_n과 c_n을 계산하기 위해 다음 재귀로 이어집니다:

c₀ = 1

s₀ = 0

c_n+1 = w_r c_n − w_i s_n

s_n+1 = w_i c_n + w_r s_n

n = 0, ..., N − 1에 대해, 여기서 w_r = cos(2π/N) 및 w_i = sin(2π/N)입니다. 이들 둘의 시작하는 삼각 값은 보통 기존의 라이브러리 함수를 사용하여 계산됩니다 (그러나 역시 z^N − 1의 원시 근(root)에 대해 풀기 위해 복소 평면에서 예를 들어 뉴턴의 방법(Newton's method)을 사용함으로써 구할 수 있습니다).

이 방법은 정확한 산술에서 정확한 테이블을 생성하지만, 유한-정밀도 부동-점(floating-point) 산술에서 오차를 가집니다. 사실, 그 오차는 (최악과 평균 경우 둘 다에서) O(ε N)으로 성장하며, 여기서 ε는 부동-점 정밀도입니다.

상당한 개선은 FFT 구현에 대해 삼각 값을 생성하기 위해 종종 사용되는 트릭 (Singleton, 1967에 의함), 위의 것에 다음 수정 사항을 사용하는 것입니다:

c₀ = 1

s₀ = 0

c_n+1 = c_n − (α c_n + β s_n)

s_n+1 = s_n + (β c_n − α s_n)

여기서 α = 2 sin²(π/N) 및 β = sin(2π/N)입니다. 이 방법의 오차는 훨씬 더 작은, 평균에서 O(ε √N) 최악의 경우에서 O(ε N)이지만, 이것은 여전히 큰 크기의 FFT의 정확도를 상당히 저하시킬만큼 충분히 큽니다.

See also

• Aryabhata's sine table
• CORDIC
• Exact trigonometric constants
• Madhava's sine table
• Numerical analysis
• Plimpton 322
• Prosthaphaeresis

References

• Carl B. Boyer (1991) A History of Mathematics, 2nd edition, John Wiley & Sons.
• Manfred Tasche and Hansmartin Zeuner (2002) "Improved roundoff error analysis for precomputed twiddle factors", Journal for Computational Analysis and Applications 4(1): 1–18.
• James C. Schatzman (1996) "Accuracy of the discrete Fourier transform and the fast Fourier transform", SIAM Journal on Scientific Computing 17(5): 1150–1166.
• Vitit Kantabutra (1996) "On hardware for computing exponential and trigonometric functions," IEEE Transactions on Computers 45(3): 328–339 .
• R. P. Brent (1976) "Fast Multiple-Precision Evaluation of Elementary Functions", Journal of the Association for Computing Machinery 23: 242–251.
• Singleton, Richard C. (1967) "On computing the fast Fourier transform", Communications of the ACM 10: 647–654.
• Gal, Shmuel and Bachelis, Boris (1991) "An accurate elementary mathematical library for the IEEE floating point standard", ACM Transactions on Mathematical Software.