자바스크립트로 배우는 SICP - 5. 소수 판정법과 고차함수로의 추상화

소수 판정법의 여러 종류들을 알아보고 고차함수로의 추상화를 살펴보자! 내가 제일 좋아하는 부분이다!

2023-10-27 | 독서 | 20min

키워드

오늘의 키워드는 다음과 같다.

소수의 판정 - 약수와 페르마 소정리
고차함수로의 추상화
- 합산의 추상화
- accumulate 과 filter 함수 구현해보기

그럼 하나씩 키워드 중심으로 살펴보자!

소수의 판정

전부 확인하자! - $\theta(n)$

어떤 수가 소수라는 것은 약수가 자기자신 또는 1인 수을 가리킨다.

그럼 어떤 수가 소수임을 어떻게 확인할까? 바로 떠오르는 방법으로는 단순하게 2부터 n까지 모든 값으로 n을 나누어 나머지가 존재하는지 여부를 확인하면 된다. 이 방식의 증가차수는 $\theta(n)$ 에 해당할 것이다.

위의 방식을 이용한 코드는 아래와 같을 것이다

function smallest_divisor(n) { // 우리가 구현하려 하는 함수이다
    return find_divisor(n, 2);
}
function find_divisor(n, test_divisor) { // 나누는 값을 찾는 함수이다
    return test_divisor > n // 2 부터 n까지 나눠지는 여부를 확인한 것이다.
           ? n
           : divides(test_divisor, n)
           ? test_divisor
           : find_divisor(n, test_divisor + 1);
}
function divides(a, b) { // 나눠지는 여부를 확인하는 함수이다.
    return b % a === 0;
}
 
smallest_divisor(42); // 2

조금 체로 걸러볼까? - $\theta(\sqrt{n})$

더 적은 시행을 하는 방법은 없을까? 고등학교 때 배웠던 내용을 떠올려보자. 에라토스테네스의 체 를 이용한 방법이 기억날 것이다. 이 방법에서는 n이 소수인지를 확인하기 위한 방법으로 $\sqrt{n}$ 이하의 수들로 $n$ 을 나눠보는 것이다. 이 방식의 증가차수는 $\theta(\sqrt{n})$ 에 해당할 것이다. 왜 $\sqrt{n}$ 인지에 대해서는 이 글을 참고바란다.

위의 방식을 이용한 코드는 앞서 언급된 코드에서 아래의 부분만 바꾸어주면 된다. 주석한 부분을 살펴보자.

function square(x) { // 제곱 계산을 추상화 한 함수이다.
    return x * x;
}
 
function find_divisor(n, test_divisor) {
    return square(test_divisor) > n // 이 부분에 square() 함수가 적용되었다.
           ? n
           : divides(test_divisor, n)
           ? test_divisor
           : find_divisor(n, test_divisor + 1);
}

이렇게 찾은 smallest_divisor() 함수를 적용한 값이 자기자신일 경우 소수가 되는 것이다.

function is_prime(n) {
    return n === smallest_divisor(n);
}
 
is_prime(42); // false (42 !== 2)

똑똑하게 가보자! 근데 페르마를 곁들인… - $\theta(\log{n})$

그럼 더욱 적은 시행을 하는 방법은 없을까? 있다! 대학교의 이산수학 시간에 배우던 내용을 떠올려보자… 바로 페르마 소정리 를 이용하는 것이다. 간단히 소개하자면 페르마 소정리는 다음을 의미한다.

p가 소수이고, a가 p로 나누어지지 않는 정수이면, 아래의 합동식이 성립한다.
$a^{p-1} ≡ 1\space(mod\space p)$
그리고, 모든 a에 대하여 다음 합동식 또한 성립한다.
$a^{p} ≡ a \space (mod \space p)$

위의 합동식 중 아래의 식을 이용하는 것이다. 그럼 이를 그럼 코드로 어떻게 구현할까?

차근차근 하나씩 생각해보자.

우선 한 수의 거듭제곱을 다른 수로 나눈 나머지를 계산하는 함수가 필요할 것이다.
그리고 위의 함수의 매개변수에 값을 대입하는 함수가 필요할 것이다.

한 수의 거듭제곱 과 다른 수 로 나누기 위해서는 3개의 매개변수가 필요할 것이다. 각각을 base(밑) , exp(지수) , m(나눌 값) 이라고 하자. 이때 함수 expmod 의 구조는 다음과 같을 것이다.

function expmod(base, exp, m) {
    return exp === 0
           ? 1
           : is_even(exp)
           ? square(expmod(base, exp / 2, m)) % m
           : (base * expmod(base, exp - 1, m)) % m;
}

생각보다 어려운 코드는 아니다. 우선 지수가 0일 때, 반환 값은 1일 수 밖에 없다. 지수가 짝수라면 우리는 exp 의 값을 반으로 줄이고, 해당 값을 제곱한 결과를 m 으로 나눈 나머지를 통해 확인할 수 있다!

만약 지수가 0도, 짝수도 아니라면, base를 따로 곱해주고 짝수 지수로 만들어 다시 재귀적 호출한 값을 m 으로 나눈 값을 확인할 수 있다!

이렇게 expmod 함수를 구현해보았다. 이제 이 함수에 적절한 매개변수를 대입해주면 된다! 코드는 다음과 같다.

function fermat_test(n) {
    function try_it(a) {
        return expmod(a, n, n) === a;
    }
    return try_it(1 + math_floor(math_random() * (n - 1)));
}
 
fermat_test(97);

위 코드에서 고민해볼 점은 n과 a의 어휘적 범위가 다르다는 것이다. n의 범위가 더욱 크고, a의 범위가 더욱 작다. 이렇게 설정한 이유가 무엇일까?

위 코드에서 소수임을 확인하고 싶은 대상은 바로 n 이라는 값이다. 그리고 페르마 소정리에서 modulo로 보는 값은 바로 n 이다. 즉, n으로 나눈 영역인 1 부터 n-1 의 값을 확인해보면 될 것이다. 관련 수학 개념으로는 Galois Field 링크를 참고하길 바란다!

그러므로, 우리는 1부터 n-1 사이의 값을 랜덤하게 골라 expmod 의 base 값으로 대입해볼 때, 만약 expmod 의 결과 값이 base 값이라면 이는 n 이 소수임을 판정해주게 된다! 여기서 n의 값이 바로 우리의 관심사이기에 적용되는 함수의 스코프가 더욱 크며, 해당 영역 내에서 고정된 채로 a 라는 값이 내부 스코프에서 적용되는 것이다.

설명은 길었지만, 그냥 우리가 구현한 expmod 를 적용할 매개변수 값을 설정하여 적용하고 확인한 것이다. 😅

최강의 방법일까? 아니다! 근데… 맞다?

페르마 소정리를 이용하는 방법은 사실 언제나 통하는 방법이 아니다. 사실 가장 위의 두 방법은 브루트 포스한 방법이기에 그 결과가 참임을 (결과의 신빙성을 이야기하는 것이다.) 확신할 수 있다. 하지만, 페르마 소정리의 경우에는 그 결과가 참임을 확신할 수 없다!

실제로, 페르마 판정법을 속이는 수들이 있다. 이를 카마이클 수 라고 부른다. 자세한 내용은 이 글을 참고하자.

그러면 이쯤에서 “언제나 맞다는 것을 확신할 수 없다는 거네? 분명 아닌 값이 존재할 가능성이 있고, 그럼 이는 확률에 맡기는 것이 아닌가?” 라는 생각을 할 수 있을 것이다. 그런데, 페르마 소정리는 소수를 판정하는 매우 강력한 방법에 속한다! 엥? 왜냐하면, 무작위로 선택한 아주 큰 수의 소수 판정에서 페르마 판정법을 속일 값이 나올 확률은 컴퓨터가 “정확한” 알고리즘을 실행하는 도중에 우주방사선 때문에 오류를 일으킬 확률보다도 작기 때문이다! 사실상 확률이 100%에 근사하다는 것이다. 게다가, 오류의 확률을 얼마든지 낮출 수 있음이 증명 가능한 판정법이 존재한다는 점 또한 알려져 있다.

이러한 알고리즘을 바로 확률적 알고리즘(probabilistic algorithms) 라고 한다!

고차함수로의 추상화

첫 내용이 조금 길었다..😅 하지만 앞으로 나올 부분들은 앞선 부분보다 훨씬 재미있을 것이다!

보통 난 경험상 프론트엔드 개발 내에서 추상화는 반복적인 컴포넌트 작성이나 공통의 데이터 페칭 역할의 함수를 작성하는 것 정도로만 함수를 사용해왔다. 그리고 매번 함수를 작성할 때, 뭔가 더 똑똑한 함수를 만들어보고 싶다는 욕구가 있었다. 그런데 앞으로 나올 부분을 읽고 이 욕구를 해소해줄지도 모른다는 점이 너무나 좋았다..!

그럼 다시 추상화의 세계로 빠져보자 🤩!

합산의 추상화

제곱을 하는 함수를 구현한다고 생각해보자. 이는 아래와 같이 함수를 작성하여 사용할 수 있을 것이다.

function square(x) {
    return x * x
}

그렇지만, 위와 같이 추상화된 함수를 사용하는 방식이 아닌 x * x 를 순수하게 작성하여 이용할 수 있다. 두 방식의 차이점은 바로 언어의 원시 요소들을 이용한 연산에 대한 여부이다. 만약, 값이 커지거나 원시 요소들의 반복이 잦다면, 이를 매번 작성하는 것은 불필요하다. 이런 점에서 함수는 공통적인 패턴에 이름을 부여하여 추상을 구축하는 강력한 능력을 제공해준다.

여기까지는 이전의 내용과 다를 바 없다. 그럼 한 단계 더 나아가 보자!

함수를 더욱 추상화 할 수는 없을까? 있다! 함수에 함수가 들어가는 경우이다! 아래의 예시들을 보자.

아래는 주어진 정수들 사이 값들의 합을 계산하는 함수이다.

function sum_integers(a, b) {
		return a > b
               ? 0
               : a + sum_integers(a + 1, b);
}

아래는 주어진 정수들의 세제곱의 합을 계산하는 함수이다.

function cube(x) {
    return x * x * x;
}
 
function sum_cubes(a, b) {
    return a > b
           ? 0
           : cube(a) + sum_cubes(a + 1, b);
}

아래는 $\pi/8$ 에 수렴하는 급수이다. 자세한 내용은 여기를 참고하자.

\pi/8 = 1/1\times3\space + \space1/5\times7\space + \space1/9\times11 \space \dots

위를 코드로 작성하면 아래와 같다.

function pi_sum(a, b) {
    return a > b
           ? 0
           : 1 / (a * (a + 2)) + pi_sum(a + 4, b);
}

위 세 예시에서 공통점을 찾아보면 전부 함수들이 다음과 같은 패턴을 띠고 있다!

function 이름(a, b) {
    return a > b
           ? 0
           : 현재_항 (a) + 이름 (다음_항(a), b)
}

이렇게 공통의 패턴의 존재성은 유용한 추상이 숨어 있음을 말해주는 강력한 증거가 된다! 그리고 이와 관련해서 정말 인상 깊었던 책의 내용을 인용하자면,

실제로, 수학자들은 오래전에 급수의 합 이라는 추상을 인식하고, 그러한 개념을 표기하기 위해 ‘시그마 표기법’을 고안했다. 다음이 시그마 표기의 예이다.
$\sum_{n=a}^{b}f(n) = f(a) + f(a+1) + f(a+2)+ \cdots + f(b)$
시그마 표기법은 수학자가 어떤 특정한 수치들의 합이 아니라 합산이라는 개념 자체를 다룰 수 있게 한다는 점에서 강력하다 … 이와 비슷하게 우리의 언에도 특정한 합을 계산하는 함수가 아니라 합산 개념 자체를 표현하는 함수를 작성하는 능력이 있으면 좋을 것이다.

이 부분을 읽고 머리가 한 대 맞은 느낌이었다! 지금껏 시그마는 여러 항들의 합을 단순하게 표시한다는 의미로만 받아들였다. 하지만, 이를 합산이라는 추상화된 개념을 다루기 위한 수단이라고 생각해보니 정말 새로운 관점으로 다가왔다!

잠시 흥분을 가라앉히고 합산이라는 개념을 다시 코드로 작성해보자! 형태는 앞서 대강 제시한 공통 패턴에 이름만 바꿔주면 된다! 다음 코드를 보자.

function sum(term, a, next, b) {
    return a > b
           ? 0
           : term(a) + sum(term, next(a), next, b);
}

이전의 패턴에서 매개변수에 term 과 next 라는 함수들을 추가로 설정했다. 이로써, sum 이라는 함수는 급수의 형태를 지니고 있는 어떤 식이라도 표현할 수 있는 강력한 추상함수로서 작동할 수 있게 된 것이다!

그럼 앞선 세 예시를 위의 sum 함수를 이용하여 표현하면 다음과 같을 것이다!

sum(self, a, inc, b) // self는 자기자신을, inc는 1 더한 값을 반환하는 함수이다.
sum(cube, a, inc, b) // cube은 매개변수를 세제곱 한 값을 반환하는 함수이다.
sum(fn, am, inc_by_4, b) // fn은 pi_sum을 구성하는 급수의 일반항을 표시하는 함수이다.

만약 sum 과 sum이 매개변수로 받는 함수들을 하나의 함수 내에 구현한다면 해당 함수는 우리의 관심사만을 대입하는 매우 잘 추상화된 함수일 것이다. 다음은 세제곱의 합을 추상화한 함수이다!

function sum_cubes(a, b) {
    return sum(cube, a, inc, b);
}

위와 같이 구현된 함수 sum_cubes 의 장점을 꼽자면 다음과 같다.

범위만을 명시해주면 값을 얻을 수 있다. → 블랙박스로의 추상이 잘 되어있다.
구현 도중 사용된 sum 함수는 타 급수 형태에도 이용이 가능하다 → 모듈로서 이용이 가능하다.

즉, 함수로서의 추상이 매우 잘 되어있는 케이스라고 생각한다.

pi_sum 도 해볼까? 이 역시 마찬가지로 아래와 같이 구현할 수 있다.

function pi_sum(a, b) {
    function pi_term(x) {
        return 1 / (x * (x + 2));
    }
    function pi_next(x) {
        return x + 4;
    }
    return sum(pi_term, a, pi_next, b);
}

같은 방식으로 아래와 같은 정적분의 형태 또한 구현하면 다음과 같다!

\int_a^bf = f(a+\frac{dx}{2}) + f(a+\frac{dx}{2}+dx)+f(a+\frac{dx}{2}+2dx)+\cdots

function integral(f, a, b, dx) {
    function add_dx(x) {
        return x + dx;
    }
    return sum(f, a + dx / 2, add_dx, b) * dx;
}

이제 적용하고 싶은 함수 f를 구현하여 매개변수로 넣으면 원하는 정적분의 결과를 구할 수 있다!

누산과 필터링 추상화하기

서로 달라 보이는 다수의 연산을 적절한 추상을 이용해서 통합하면 표현력이 얼마나 커지는지를 보여주는 것이다.

이제 응용을 해보자..! 자바스크립트에서 자주 쓰이는 내장 메소드로는reduce , filter 가 있다. 이들은 누산과 필터링에 각각 속하는 함수이다. 이 함수들의 정확한 내부를 구현하지 않지만, 이들이 지닐 추상은 아래의 과정을 통해 구현되지 않았을까 하는 두근거리는 마음에 소개한다.

누산함수

누산(accumulate)는 리듀서의 개념이다. 조합할 항과 구간의 상계와 하계를 받으면서, 현재까지의 누산 결과와 조합 방식을 명시하는 함수, 그리고 종료 판정을 위한 기준값을 받을 것이다.

이는 다음과 같은 형태를 보일 것이다.

accumulate(combiner, null_value, term, a, next, b)

combiner 에는 누산 결과와 조합 방식을 명시하는 함수가 들어간다
null_value 에는 누산할 값이 더 이상 없을 경우의 기준 값을 의미한다. (종료 판정을 위한 기준값일 것이다!)

그리고 등장하는 term , a , next , b 는 이전에 다뤘던 sum 의 형태 그대로라고 판단하면 된다! 즉, 추가된 것은 조합 함수 와 종료 판정 기준값 뿐이다!

그러면 누산함수를 구현해보자!

재귀적 과정을 통해 구현한 누산함수

위의 조건을 생각하면 다음과 같이 구현할 수 있다!

function acc_recursive(combiner, null_value, term, a, next, b) {
	return a > b
           ? null_value
           : combiner(term(a), acc_recursive(combiner, null_value, term, next(a), next, b));
}

생각해보면 당연한게, 추가된 매개변수인 combiner 함수는 “조합”을 위한 함수이다. 즉, 앞으로 누산될 결과를 필요로 하며 이를 현재 항과 조합해야 한다. 그렇기에 현재 항인 term(a) 와 이전까지 누산된 결과인 acc_recursive(...앞으로 연산될 결과) 를 매개변수로 받는다.

그리고 주어진 범위 (a 부터 b까지) 내에서 연산이 진행되어야 하므로 종료 판정 조건문 및 null_value 를 이용하면 재귀적으로 구현할 수 있다!

반복적 과정을 통해 구현한 누산함수

function acc_iterative(combiner, null_value, term, a, next, b) {
	function iter(a, result) {
		return a > b
               ? result
               : iter(next(a), combiner(term(a), result));
	}
	return iter(a, null_value);
}

반복적 과정의 경우, 현재 상태를 기록할 것이다. 하지만 재귀적 과정과 다르게, 매 과정의 결과를 기억하는 과정이 사라지기에 자원에서의 증가차수가 $\theta(1)$ 이었다! 그렇다면 재귀적 호출을 하더라도 앞서 구현된 재귀적 과정과 다르게 iter이라는 함수 내부의 매개변수로 다음 항을 기억하는 것이다.

🔥 조금 더 자세하게 설명하자면, 재귀적 과정은 다음과 같은 순서로 함수가 평가될 것이다. combiner은 이해하기 쉽게 그냥 두 매개변수의 합으로 보자.

c(초항, 나머지 누산된 결과)
c(초항, c(다음항, 나머지 누산된 결과))
c(초항, c(다음항, c(다다음항, 나머지 누산된 결과)))
…

자바스크립트는 인수 우선 평가로 진행되는 것을 기억하자. 여기서, 매 단계에서 초항, 다음항의 연산 결과의 계산은 “나머지 누산된 결과”가 종료 판정에 도달하기까지 연산이 미뤄진다는 것이다. 즉, 공간을 계속 차지한다는 것이다.

반면에 반복적 과정은 다음과 같이 함수가 평가될 것이다.

iter(초항, 결과) → 처음엔 결과가 null_value이다.
iter(다음항, 누산된 결과) → 누산된 결과는 초항과 null_value의 조합된 결과일 것이다.
iter(다다음항, 다음항까지 누산된 결과) → 다음항까지 누산된 결과가 매개변수로 들어간다.
…

즉, 재귀적 과정에서는 combiner가 acc_recursive에 의해 종료판정에 다다르기까지 겹겹이 호출되었는데, 반복적 과정에서는 그때 그때 누산된 결과(즉, combiner 함수의 평가가 끝난) 결과 값이 이용되기에 매 단계에서 다음 단계로 넘어갈 때 공간을 요구하지 않는다. 이는 즉, $\theta(1)$ 의 증가차수를 지니게 될 것이다.

필터링된 누산 함수

필터링된 누산 결과를 반환하는 함수도 누산함수와 형태가 비슷하다. 크게 보면 다음과 같다. 단순히 filter 를 위한 함수가 추가되었을 뿐이다.

filtered_accumulate(combiner, null_value, term, a, next, b, filter)

자세한 구현은 아래와 같다.

function filtered_accumulate(combiner, null_value, term, a, next, b, filter) {
	return a > b
           ? null_value
           : filter(a)
           ? combiner(term(a), filtered_accumulate(combiner, null_value, term, next(a), next, b, filter))
           : filtered_accumulate(combiner, null_value, term, next(a), next, b, filter);
}

정말 달라진 것이 없다. 앞서 구현된 재귀적 과정의 누산함수에 단지 filter(a) 라는 조건이 추가 된 것 뿐이다.

즉, 해당 항에서 필터링 조건을 충족하는 경우에만 combiner 함수를 적용하고, 그 외의 경우는 combiner 을 호출하지 않고 다음 항을 대입한다. 이로써 필터링 조건에 충족하는 경우에만 누산이 진행되는 추상 함수를 구현할 수 있게 되었다!

마무리

와. 이번 내용은 상당이 내용이 깊었다. 책 페이지는 102쪽에서 124쪽이다. 단순히 22쪽 분량에 이리 깊은 내용이 포함되어있다니… 이걸 한번에 읽으려는 시도는 정말 위험한 것 같다.. 간단하게 정리하려던게 내가 이해한 과정을 써내려가다가 누군가는 읽지 않을까라는 생각에 설명을 추가하고 추가하다보니 상당히 길어진 것 같았다. 오늘도 수고했다! 이걸 읽은 누군가에겐 도움이 되었다면 좋겠다…!