SICP 연습문제 1.25 친절한 풀이

문제

Alyssa P.Hacker는 expmod를 만들면서 쉽게 할 수 있는 일을 너무 복잡하게 한다고 투덜거렸다. 거듭제곱 값을 어떻게 구하는지 자신이 잘 알고 있으며, 아래처럼 하면 된다고 말한다.

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

참말 이렇게 해도 되는가? 이 프로시저를 소수 찾는 일에 그대로 써도 되는지 설명하라.

문제로 부터 얻은 것

새로 만든 expmod는 메모리가 수용할 수 없는 크기의 수를 만든다.

문제풀이

문제에서 나온 대로 프로시저를 짜고 아래와 같은 코드를 실행시켰습니다.

(prime? 1009 100)

메모리 부족으로 프로세스가 정상종료하지 못했습니다.
어쩌면 당연한 결과일지도 모릅니다.

(prime? 1009 100)를 계산하기 위해서는
우선 1009보다 작은 어떤 정수 a에 대해
$a^{1009}$를 계산해야 합니다.

$2^{10}$btye가 1KB입니다.
$2^{20}$btye가 1MB입니다.
$2^{30}$btye가 1GB입니다.

$2^{30}$만으로도 기가단위입니다.
$a^{1009}$는 메모리가 감당하기에는 너무 큰 숫자입니다.

반면, 책에서 설명한 expmod프로시저는 수가 너무 커지기 전에 미리 모듈러 연산을 진행하므로 메모리를 많이 차지하지 않습니다.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

효율적인 알고리즘의 필요성을 다시한번 느낍니다.

참고로 위 expmod프로시저가 이해가 되지 않으신다면 이 글을 추천합니다.

읽어주셔서 감사합니다.