Computer algebra systems (CAS) brought algebraic numbers $\overline{Q}$ accessible to end-users.Still, there are uncountable transcendentals C$\backslash$Q.Kontsevich and Zagier introduced periods to fill in this gap: a period is the difference between the volumes of two algebraic sets. Periods are receiving increasing interest in algebraic model theory as they have finite descriptions, i.e., the polynomials' coefficients, and include all algebraic reals as well as some transcendentals. Recent research has located their worst-case complexity in low levels of the Grzegorczyk Hierarchy.
Meanwhile, regular floating-point arithmetic incurs rounding errors that accumulate over time and hamper reliable computations. Interval arithmetic deals with an interval [a;b] where the actual value reside instead of a single floating-point approximation to keep track of the error bounds. The error bound, however, may blow up beyond use. On the other hand, Exact Real Computation is an approximation of infinite computations of Type-2 machines by finite computations with arbitrary precision, i.e., given an output precision n, to produce a dyadic approximation a/$2^n$. In this background, this thesis specify a general problem of computing periods in sense of Exact Real Computation; then, introduces, analyzes, and evaluates a rigorous algorithms for rigorously computing periods up to error $2^{-n}$. We discuss pros and cons of traditional discrete computation and Exact Real Computation with our previous algorithms. Furthermore, we show the general problem of computing periods up to error $2^{-n}$ is \classNP-hard.
컴퓨터 대수 시스템(CAS)은 대수적인 수($\overline{Q}$)를 일반 대중들이 쉽게 사용할 수 있게 만들었다. 하지만 아직 셀 수 없을 만큼의 초월수(C$\backslash\overline{\Q}$)가 존재한다. 콘체비치(Kontsevich)와 자기어(Zagier)는 이 틈을 메꾸기 위해 피리어드를 제안했다. 피리어드는 두 준대수적 집합의 부피의 차이다. 피리어드는 유한한 표현 즉 다항식의 계수들을 가지고 있고, 모든 대수적인 수와 일부 초월수를 포함하고 있기 때문에 대수적 모델 이론에서 많은 관심을 받고 있다. 최근 연구에서 피리어드의 최악의 경우에 대한 복잡도가 제고직 계층(Grzegorczyk Hierarchy)에서 낮은 단계에 있다는 것이 밝혀졌다. 한편 흔히 쓰이는 부동소수점 연산은 반올림 오차를 야기하고, 시간이 지남에 따라 그 오차가 누적되어 신뢰할 수 있는 연산을 제공하지 못 한다. 구간 연산은 하나의 부동소수가 아닌, 실제값이 포함된 구간([a;b])을 다루고 모든 연산의 오차를 추적한다. 하지만 그 오차 범위는 점점 커져서 쓸모가 없어지기도 한다. 반대로 정확한 실수 계산은 타입-2 기계의 무한한 연산을 임의의 오차 이내의 유한한 연산으로 근사한다. 다시 말해서 출력 정확도(n)가 주어졌을 때, $2^{-n}$ 오차 범위 안의 다이애딕 근사값(a/$2^n$)을 구하는 것이다. 이러한 배경에서 이 논문은 피리어드를 계산하는 일반적인 문제를 정확한 실수 계산의 관점에서 명세한다. 그리고 이 논문은 피리어드를 $2^{-n}$ 오차 범위 안으로 계산하는 알고리즘을 제시하고, 분석하고, 평가한다. 또한 우리는 이 알고리즘을 우리의 선행 연구에서 제시한 알고리즘들과 비교하여 전통적인 이산 계산과 정확한 실수 계산의 장단점을 비교한다. 더 나아가 우리는 피리어드를 계산하는 문제가 NP-hard에 속함을 보인다.