거듭제곱, 최대공약수, 소수판정 최적화 (+ 확률에 의한 판정)

특정 산술 계산들에 적용할 수 있는 최적화 아이디어를 살펴보자.

거듭제곱

bⁿ 을 구하는 재귀함수는 다음과 같이 작성할 수 있다.

function exp(b, n){
    return n === 0 ? 1 : b * exp(b, n - 1);
}

이 때의 증가차수는 O(n)이 될 것이다.
여기서 다음 연속제곱식을 이용하면 증가차수를 O(logn)으로 줄일 수 있다.

bⁿ = (b½ⁿ)² : n = 짝수
bⁿ = b * bⁿ⁻¹ : n = 홀수

코드로 나타내면 다음과 같다.

function exp(b, n){
    return n === 0 ? 1
            : n % 2 === 0
            ? exp(b, n / 2) ** 2
            : b * exp(b, n - 1);
}

exp(b, n / 2) 으로 치환할 때마다 필요한 단계수가 절반으로 감소한다.
즉 exp(b, 2 * n)을 계산하는데 필요한 곱셈의 수가 exp(b, n) 보다 단 1회 많다.
이에따라 증가차수는 O(logn)(밑=2)이 됨을 알 수 있다.

최대공약수

유클리드 호제법을 적용하면 최대공약수를 O(logn)의 증가차수로 구할 수 있다.

유클리드 호제법
a, b의 공약수는 b와 a를 b로나눈 나머지 r의 공약수와 같다.
a % b = r 일 때, a, b의 공약수 = b, r의 공약수

a, b를 b, r로 교체할 때마다 더 작은 정수쌍의 문제로 축약된다.

function gcd(a, b){
    return b === 0 ? a : gcd(b, a % b);
}

라메의 정리에 의해 증가차수는 O(logn)(밑=황금비𝜙) 이다.

라메의 정리
어떤 정수 쌍의 최대공약수를 구하는데 필요한 단계수가 k 일때, 그 쌍의 더 작은 정수는 k번째 피보나치 수보다 크거다 같다.

소수판정

어떤 수 n이 소수인지 판정하는 가장 직관적인 방법은 그 수의 약수들을 2부터 n까지 전부 조사하는 것이다.
즉, 2 이상 n 이하의 정수로 모두 나누었을 때 나누어 떨어지지 않는 수를 찾으면 된다. 이때의 증가차수는 O(n)이다.
그런데 어떤수의 약수들은 항상 짝을 이룬다. 따라서 작은쪽 절반(2이상 √n이하)까지만 조사하면 증가차수는 O(√n)이다.

소수판정 - 확률적 방법

소수판정에 페르마 판정법을 적용하면 증가차수를 O(logn)까지 줄일 수 있다.

페르마 판정법
n이 소수이고 a는 a < n인 임의의 양의 정수일 때
aⁿ % n !== a : n은 소수가 아님
aⁿ % n === a : n은 소수일 가능성이 큼

이 법칙에 따라 aⁿ % n === a 연산을 여러번 수행하면 높은확률로 소수를 판별할 수 있다.

코드로는 다음과 같이 적용가능하다.

function fermat_test(n){
    function try_it(a){
        return expmod(a, n, n) === a; // aⁿ % n === a
    }
    return try_it(1 + Math.floor(Math.random() * n - 1))) // [1, n-1] 구간의 정수 a로 재시도
}

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


// times회 판정을 실행
function fast_is_prime(n, times){
    return times === 0
            ? fermat_test(n)
            : fast_is_prime(n, times - 1)
            : false;
}

expmod(a, n, n)는 exp(a, n)와 같은 원리로 연속제곱 기법을 사용하여 곱셈의 단계수는 O(logn)으로 같다.
exp(a, n) % n === a 로 계산할 수도 있지만, expmod는 실행마다 mod(%) 연산을 거치며 계산 값을 n 미만으로 줄여주기 때문에 훨씬 큰 n에 대한 연산이 가능하다.