1.2.6 연습:소수 찾기
소수 찾는 방법은 약수를 이용하는 방법과 페르마 검사를 이용한 확률적 방법 있다. 약수를 이용하는 방법은 계산 단계가 O(sqrt(n)) 이다.
확률적 방법에서는 새롭게 expmod 프로시저를 짜는데 이 프로시저를 주의해서 봐야 한다. expmod는 (base^exp)%m 을 계산하는 프로시저이고, 책에서는 다음과 같이 짜여 있다.
(define (expmod-1 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))))
이 프로시저는 시간은 O(log n), 공간은 O(n)의 복잡도를 가진다. 기존에 짜여진 fastexpt-2 프로시저(연습 문제 1.16)를 이용하면 다음과 같이 짤 수 있고, 이 경우 시간은 O(log n), 공간은 O(1)의 복잡도를 가진다. 이 부분만 볼때는 fastexpt-2 프로시저를 이용하는 것이 좋아 보인다.
(define (expmod-2 base exp m) (remainder (fastexpt-2 base exp) m))
연습 문제 1.25가 이 질문인데 참고한 외부 솔루션을 기반으로 정리해 보면,
expmod-1의 경우는 연산을 계속 미루면서 공간이 늘어나는 대신 상태 변수의 값이 증가하지 않고 오히려 값이 감소하는 반면,
fastexpt-2의 경우는 내부 iteration을 돌면서 상태 변수 값이 계속 증가하게 된다.
이상적으로는 값이 크기가 기본 연산(primitive operator)의 실행 속도에 관련이 없어야겠지만, 실제로는 값이 커지면 기본 연산의 속도에 영향을 미치게 되므로 expmod-2가 아닌 expmod-1을 사용해야 한다라고 결론 내릴 수 있다.
expmod-1에 의한 계산 절차는 다음과 같다.
;; e : expmod-1 ;; r : remainder ;; s : square (e 10 20 3) (r (s (e 10 10 3)) 3) (r (s (r (s (e 10 5 3)) 3)) 3) (r (s (r (s (* 10 (e 10 4 3))) 3)) 3) (r (s (r (s (* 10 (r (s (e 10 2 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (e 10 1 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r (* 10 (e 10 1 3)) 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r (* 10 (r (* 10 (e 10 0 3)) 3)) 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r (* 10 (r (* 10 1) 3)) 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r (* 10 (r 10 3)) 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r (* 10 1) 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s (r 10 3)) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r (s 1) 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s (r 1 3)) 3))) 3)) 3) (r (s (r (s (* 10 (r (s 1) 3))) 3)) 3) (r (s (r (s (* 10 (r 1 3))) 3)) 3) (r (s (r (s (* 10 1)) 3)) 3) (r (s (r (s 10) 3)) 3) (r (s (r 100 3)) 3) (r (s 1) 3) (r 1 3) 1
expmod-2에 의한 계산 절차는 다음과 같다.
;; iter는 내부에서 반복 프로세스로 동작하는 프로시저 (remainder (fastexpt-2 4 6) 3) (iter 1 4 6) (iter 1 16 3) (iter 16 16 2) (iter 16 256 1) (iter 4096 256 0) 4096
프로세스와 같이 expmod-1은 공간은 늘어났다 줄어드는 반면, 값의 크지 않고,expmod-2는 공간의 동일하나 값이 계속 커진다.
