수치 알고리즘

요약

이 단원의 앞선 수업들에서는 반복문을 쓰는 법과, 불변식과 변량으로 반복문에 대해 추론하는 법을 배웠다. 이 수업은 그 추론을 컴퓨터보다 오래되었고 지금도 쓰이는 네 가지 고전적인 수치 알고리즘에 적용한다. 시험 나눗셈에 의한 소수 판정: 증명할 수 있는 이유로 $\sqrt{n}$ 에서 멈추며, 부주의하게 쓰면 정지 조건에서 오버플로가 난다. 최대공약수를 구하는 유클리드 호제법: 그 불변식, 종료, 음수와 관련된 함정, 그리고 std::gcd 함수와의 비교를 다룬다. 연속 나눗셈에 의한 진법 변환과 호너의 방법: 호너의 방법은 자릿수들로부터 수를 다시 만들고, 같은 틀로 다항식의 값을 계산한다. 그리고 이분법: 구간을 둘로 나누어 근을 근사하는 방법으로, 중간값 정리가 보장하며, 필요한 회차 수를 미리 계산할 수 있다. 각 알고리즘은 수학적 대상으로 제시된다. 즉 말한 대로 한다는 증명, 끝난다는 증명, 그리고 단계 수에 대한 첫 셈과 함께 제시된다.

학습 목표

$\sqrt{n}$ 까지 나누어 보는 소수 판정을 구현하고, $\sqrt{n}$ 까지 가면 충분한 이유를 설명한다.
유클리드 호제법을 구현하고, 그 불변식(최대공약수는 변하지 않는다)을 진술하고, std::gcd 함수와 비교한다.
연속 나눗셈으로 수를 다른 진법으로 변환하고, 호너의 방법으로 위치 표기나 다항식의 값을 계산한다.
이분법으로 근을 허용 오차까지 근사하고, 필요한 회차 수를 계산한다.

약수와 소수

시험 나눗셈

정수 $n \geq 2$ 의 양의 약수가 1과 $n$ 뿐이면 그 정수를 소수라 하고, 다른 약수가 있으면 합성수라 한다. 0과 1은 어느 쪽도 아니다. 이 정의는 곧바로 하나의 알고리즘을 떠올리게 한다. 각 후보 $d$ 의 값을 2부터 $n - 1$ 까지 시험하여, 어느 하나가 나누어떨어지게 하는 즉시 그 수를 합성수로 판정하는 것이다. 이것은 반복문 수업에서 본 가장 작은 약수를 찾는 반복문이며, 올바르다. 그러나 열 자리 소수에 대해서는 거의 백억 번의 나눗셈을 하며, 그 거의 전부가 쓸모없다. 이유는 아래와 같다.

명제

\sqrt{n}

까지만 시험하면 충분하다

$n \geq 2$ 인 정수가 합성수이면, 약수 $d$ 가 있어 $2 \leq d \leq \sqrt{n}$ 을 만족한다.

증명

$n = a \cdot b, \quad 2 \leq a \leq b$
$n$ 이 합성수이면, 어느 쪽도 1이나 $n$ 의 값과 같지 않은 두 인수의 곱으로 쓸 수 있다. 둘 중 작은 쪽을 $a$ 로 나타내자.
$a^2 \leq a \cdot b = n$
$a \leq b$ 의 양변에 양수 $a$ 를 곱하면 $a^2 \leq ab = n$ 을 얻고, 따라서 $a \leq \sqrt{n}$ 이다. 즉 어떤 인수분해에서든 작은 인수는 $\sqrt{n}$ 의 왼쪽에 있다.
$d \leq \sqrt{n} \iff \frac{n}{d} \geq \sqrt{n}$
따라서 약수는 $(d, n/d)$ 꼴의 쌍으로 나타나며, $\sqrt{n}$ 의 양쪽에 대칭으로 놓인다. $n = 36$ 일 때 쌍은 $(2, 18)$ , $(3, 12)$ , $(4, 9)$ , $(6, 6)$ 이다. $\sqrt{n}$ 까지의 어떤 후보도 $n$ 의 약수가 아니면, 그 너머의 어떤 후보도 약수가 아니다. 짝이 되는 수가 더 일찍 나타났을 것이기 때문이다.

따라서 나눗셈 횟수는 약 $n$ 번에서 약 $\sqrt{n}$ 번으로 줄어든다. $n$ 의 값이 이십억에 가까우면, 이십억 번에서 사만 육천 번으로 줄어든다. 프로그램은 올바른 반복문 설계 수업의 플래그 패턴을 쓴다. isPrime 변수는 참으로 시작하고, 반복문이 약수를 찾으면 그것을 끈다.

C++ 프로그램

#include <iostream>#include <print>int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{}: 소수", n);    } else {        std::println("{}: 소수 아님", n);    }}

프로그램 입력

2147483647

출력

2147483647: 소수

세 가지 결정은 설명할 만하다. 플래그는 n >= 2 식으로 초기화되므로, 0, 1, 음수는 반복문에 들어가지 않고 소수가 아니라고 판정된다. 이 경우를 잊는 것이 전형적인 오류인데, $n = 1$ 일 때 반복문은 한 회차도 돌지 않아 프로그램이 1을 소수로 판정하게 되기 때문이다. for 문의 조건은 두 부분으로 되어 있다. 첫 약수에서 반복문을 멈추는 플래그와, 상한이다. 그리고 상한은 d <= n / d 식으로 쓰여 있는데, 이는 양의 정수에 대해 $d^2 \leq n$ 조건과 동치이다(정수 나눗셈은 버림을 하지만, $d$ 의 값이 버림한 몫을 넘지 않는 것은 정확히 $n/d$ 의 값을 넘지 않을 때이다. $d$ 의 값이 정수이기 때문이다). 입력된 수 $2^{31} - 1$ 의 값은 가장 큰 int 값이며 소수이다. 프로그램은 이것을 $46\,339$ 번의 나머지 계산, 즉 2부터 $46\,340$ 까지의 후보에 대한 나머지로 판정한다.

반복문의 불변식은 2부터 $d - 1$ 까지의 어떤 정수도 $n$ 의 약수가 아니다이며, 이는 플래그가 참인 동안의 이야기다. 들어갈 때는 2부터 1까지의 범위가 비어 있으므로 성립한다. $d$ 의 값이 $n$ 의 약수가 아니면 범위에 약수가 아닌 수 하나가 더해질 뿐이므로 유지된다. 그리고 플래그가 참인 채로 나올 때는, 불변식과 거짓이 된 조건 $d^2 > n$ 이 함께, $\sqrt{n}$ 까지의 어떤 후보도 $n$ 의 약수가 아님을 말해 준다. 이것이 바로 명제가 요구하는 것이다. 변량은 아직 시험할 후보의 개수, 즉 $d$ 와 $\sqrt{n}$ 사이의 정수 개수이다. 회차마다 하나씩 줄고 0 아래로 내려가지 않는다.

오버플로가 나는 조건

상한을 쓰는 자연스러운 방법은 d * d <= n 식이고, 이것은 오류이다. 같은 입력에서 반복문은 $d = 46\,341$ 에 이르고, 그때 곱 $46\,341^2 = 2\,147\,488\,281$ 의 값은 int 타입의 최댓값을 넘는다.

C++ 프로그램

#include <iostream>#include <print>int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("소수? {}", isPrime);}

프로그램 입력

2147483647

출력

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

프로그램이 코드 1(으)로 종료되었습니다.

정의되지 않은 동작 새니타이저는 곱에서 프로그램을 멈춘다. 새니타이저가 없으면 부호 있는 오버플로는 정의되지 않은 동작이며, 표준은 무슨 일이 일어나는지 말하지 않는다. Linux의 GCC에서 최적화를 켜든 끄든 관찰되는 것은 교훈적이다. 곱은 한 바퀴 돌아 음수가 되거나 $n$ 보다 작아지고, 어떤 int 값도 최댓값을 넘지 않으므로 d * d <= n 조건은 더는 거짓이 되지 않는다. 반복문은 약 이십억 회차 동안 후보를 계속 시험하다가 $d = n$ 에 이르고(이것은 $n$ 의 약수이다), 프로그램은 소수를 합성수로 판정한다. 오버플로 오류는 오버플로로 나타나지 않고 틀린 답으로 나타난다. d <= n / d 형태는 오버플로가 날 수 없다. 곱하는 대신 나누기 때문이다. 비트와 수학 라이브러리 수업은 다른 출구, 즉 std::sqrt 함수로 상한을 한 번 계산하는 방법을 제시했지만, 그러면 상한의 정확성이 부동소수점 반올림에 좌우된다. 정수 나눗셈에는 그런 문제가 없다.

대수학과 기하학 I 강좌의 “소수와 산술의 기본 정리” 수업은 1보다 큰 모든 정수가 소수의 곱으로 단 한 가지 방식으로 쓰인다는 것을 증명한다. 시험 나눗셈은 찾은 약수마다 $n$ 의 값을 나누고 몫으로 계속하는 방식으로, 그 곱을 찾는 가장 직접적인 방법이다.

요약