Week01 - Code01 분석 with 빠른 거듭제곱 알고리즘(Fast Exponential algorithm)

이번 포스팅에서는 내가 공부하면서 만들게되는 코드들에 대해 분석을 해보려 한다.

이번 주차에 분석 할 첫번째 전체 코드는 아래와 같다.

이 코드는 a^m mod n을 계산하는 로직이며, recursive를 사용하는 방식이기 때문에 적당히 낮은 숫자에서는 iteration이 적게 돌기 때문에 문제없이 돌아가지만, 숫자가 커지면 iteration 횟수도 그렇고, recursive에 의한 메모리 소비나 performace 저하는 물론이고, overflow가 날 가능성이 높다. 따라서 이런 문제들을 방지하기 위해서는 tail recursive 방식을 사용해야 한다. (tail recursive 방식에 대해서는 나중에 따로 포스팅을 하게 될 것이다.)

defmodule Code1 do

  def pow_mod(a, m, n) do

    pow_mod(a, m, n, 1)

  end

  defp pow_mod(_, 0, _, acc), do: acc

  defp pow_mod(a, m, n, acc) when rem(m, 2) == 1 do

    new_acc = rem(a * acc, n)

    pow_mod(rem(a * a, n), div(m, 2), n, new_acc)

  end

  defp pow_mod(a, m, n, acc) do

    pow_mod(rem(a * a, n), div(m, 2), n, acc)

  end

end

우선은 큰그림을 먼저 살펴보고, 그 이후에 부분별로 짤라서 분석을 해보겠다.

큰 그림: 함수의 호출 순서와 조건

이 코드의 entry point는 pow_mod/3이다. 그래서 이 함수를 호출하게 되면, 이 친구가 pow_mod/4를 호출하게 된다.

여기서 pow_mod/4는 아래의 3가지 조건에 따라, 그에 부합하는 함수를 호출하게 된다.

1. defp pow_mod(_, 0, _, acc), do: acc
2. defp pow_mod(a, m, n, acc) when rem(m, 2) == 1 do
3. defp pow_mod(a, m, n, acc) do

여기서 1번의 경우에는 when 키워드가 붙지 않았다. 그 이유는 when 키워드는 guard 문에서만 필요하기 때문이다. guard문은 함수의 파라메터가 특정 조건을 만족해야 할 때 사용하는 문법이다. 예를 들어, 아래와 같은 형태가 있을 수 있다.

def foo(x) when is_integer(x) do ... end

이 경우,  when 뒤에 boolean type의 특정 조건이 명시되고, 이 조건에 맞을 경우에만 이 함수가 호출이 되는 것이다.

그런데 1번의 경우 이미 파라메터 m의 자리에 0이라는 값이 주어졌다. 즉, 특정 조건인 m == 0 이라는 것이 명시적으로 나타나 있는 것이다. 이럴 경우에는 guard 문이 필요 없기 때문에 when을 사용하지 않은 것이다. 다시 말해, m의 값이 0이라는 것 자체가 이미 조건이기 때문에 따로 when을 사용할 필요가 없는 것이다.

결론적으로 

• defp pow_mod(_, m, _, acc) when m == 0, do: acc
• defp pow_mod(_, 0, _, acc), do: acc

위의 두 코드는 기능적으로 동일하다. 둘 다 m이 0일 때만 이 함수가 호출될 것이라는 것을 나타낸다.

하지만 첫 번째 방식은 when을 사용해서 조건을 명시적으로 표현했고, 두 번째 방식은 매개변수 자체를 0으로 설정해 조건을 명시했다. 두 번째 방식이 더 직관적이라고 생각되면 그것을 사용하면 된다. 결국 둘 다 같은 결과를 내므로 선택은 코드의 명확성이나 팀의 코딩 스타일 가이드에 따라 달라질 수 있다.

3번의 경우, 해당 함수는 다른 조건을 명시적으로 설정하지 않았기 때문에, 다른 pow_mod 함수들이 처리하지 못한 모든 경우에 대해 호출될 것이다.

Elixir에서는 함수 오버로딩과 패턴 매칭을 통해 여러 가지 경우를 분기할 수 있다. 따라서 defp pow_mod(_, 0, _, acc), do: acc와 같은 함수가 있는 경우, m이 0일 때는 이 함수가 호출되고 그 외의 경우에는 defp pow_mod(a, m, n, acc) do ... end가 호출된다.

이런 방식은 코드를 간결하고 읽기 쉽게 만들어 준다. 명시적으로 when을 사용하지 않았다면, 그것은 해당 함수가 "기본" 동작을 정의하고 있음을 나타낸다고 볼 수 있다. 이 "기본" 동작은 더 구체적인 조건에 맞지 않는 모든 경우에 실행될 것이다.

이제 각각의 함수들을 개별적으로 분석해보자.

1. defp pow_mod(_, 0, _, acc), do: acc

  defp pow_mod(_, 0, _, acc), do: acc

일단 이 함수에서는 누적값을 사용하기 위해서 accumulator를 사용하였다.  그리고 이렇게 pow_mod/3에서 private로 선언된 pow_mod/4를 호출하는 방식을 사용하는 이유는 acc의 초기값을 1로 셋팅해 주기 위해서이다. 이 acc 값은 거듭제곱 연산의 중간 결과를 저장하는 용도이다. tail recursive 방식은 이렇게 acc 값을 별도로 두는 방식으로 코드를 짠다.

pow_mod/4의 첫번째, 세번째 파라메터는 _로 두었는데, 이는 해당 위치에는 어떤 값이 들어와도 상관이 없다는 의미이다. private이므로 같은 모듈 내에서만 호출이 가능하다. 그리고 m의 값이 0일 경우에만 이 함수가 호출이 되며, m =0 이라는 것은 a^0 이기 때문에 결과 값은 1이 나오게 된다.

즉. pow_mod(a, m, n, 1)로 pow_mod(_, 0, _, acc)를 호출했기 때문에 acc는 1로 셋팅되면서 자연스럽게 1이 리턴되게 된다.

2. defp pow_mod(a, m, n, acc) when rem(m, 2) == 1 do

  defp pow_mod(a, m, n, acc) when rem(m, 2) == 1 do

    new_acc = rem(a * acc, n)

    pow_mod(rem(a * a, n), div(m, 2), n, new_acc)

  end

이 함수 역시 private로 선언되어 있다. 이렇게 private로 선언하는 이유는 이것들의 용도는 오로지 helper들이기 때문이다. 즉, 외부로는 노출될 필요도, 아니 노출 되어서는 안되기 때문에 이렇게 private로 선언해서 숨겨두는 것이다.

이 함수는 rem(m, 2) == 1이라는 조건이 성립할 경우에만 호출이 된다. 즉, m을 2로 나누었을 때 나머지가 1이 되는 경우, 다시말해 m이 홀수인 경우이다. 이 함수는 중간 계산 결과를 저장하기 위해서 존재한다.

• new_acc = rem(a * acc, n): m이 홀수일 때, a * acc는 중간 결과에 a를 한 번 더 곱한 것이다. 이를 n으로 나눈 나머지는 새로운 중간 결과 new_acc가 된다.
• pow_mod(rem(a * a, n), div(m, 2), n, new_acc): 이 부분에서는 a를 제곱한 후 n으로 나눈 나머지를 새로운 a 값으로 하고, m을 2로 나눈 몫을 새로운 m 값으로 한다. 그리고 새로 계산한 new_acc를 다음 재귀 호출에 넘긴다.

이렇게 하면, m이 홀수든 짝수든 간에 재귀적으로 계산을 효율적으로 수행할 수 있다. rem(a * acc, n)와 rem(a * a, n)을 사용하는 이유는 중간 계산 결과가 너무 커져서 오버플로우를 방지하기 위함이다. 나머지 연산을 통해 계산 결과를 n 아래로 유지한다.

이 함수는 "제곱-곱하기"라는 알고리즘의 일부로, 일반적인 제곱 계산보다 훨씬 빠르게 동작한다.

3. defp pow_mod(a, m, n, acc) do

  defp pow_mod(a, m, n, acc) do

    pow_mod(rem(a * a, n), div(m, 2), n, acc)

  end

앞의 1번 함수와 2번 함수의 조건에 만족되지 않는 경우, 즉 m이 짝수일 경우에 이 함수가 호출이 된다. 이 경우에는 누적값인 acc를 그대로 유지하면서 다음 recursive를 호출한다. 중간 계산 결과는 moduler n으로 계산한다.

이 코드는 빠른 거듭제곱 알고리즘(Fast Exponential algorithm)을 이용한 것이다.

빠른 거듭제곱 알고리즘(Fast Exponential algorithm)

빠른 거듭제곱 알고리즘은 기본적인 거듭제곱 연산을 보다 효율적으로 수행하기 위한 방법이다. 일반적인 거듭제곱 계산은 $�(�)$의 시간 복잡도를 가지지만, 빠른 거듭제곱 알고리즘은 $�(\log �)$의 시간 복잡도를 가진다. 이 알고리즘은 재귀적이거나 반복적인 형태로 구현될 수 있다.

기본 아이디어는 지수를 작은 값들로 나누어 문제를 작게 만든 다음, 그 결과를 조합하여 최종 결과를 얻는 것이다. 예를 들어 ${�}^{10}$은 ${�}^5\times {�}^5$와 같고, 또한 ${�}^5$는 ${�}^2\times {�}^2\times �$와 같다는 것을 이용한다.

재귀적인 예시 코드는 다음과 같다.

def fast_pow(a, n) when n <= 0, do: 1

def fast_pow(a, n) do

  if rem(n, 2) == 0 do

    half_pow = fast_pow(a, div(n, 2))

    half_pow * half_pow

  else

    a * fast_pow(a, n - 1)

  end

end

이 코드에서 fast_pow(a, n)은 ${�}^{�}$을 계산한다. n이 짝수일 경우 ${�}^{�}$을 $({�}^{�\mathrm{/}2}{)}^2$으로 계산하고, n이 홀수일 경우 ${�}^{�}$을 $�\times {�}^{�-1}$으로 계산한다. 이렇게 하면 최대 $�(\log �)$의 복잡도로 문제를 해결할 수 있게 된다.

이상으로 이번 코드 분석은 마무리한다.