BLOG ARTICLE Review | 2 ARTICLE FOUND

  1. 2010.12.09 6일차 review
  2. 2010.11.25 1.1.1 ~ 1.1.4 리뷰

6일차 review

Review 2010.12.09 23:42

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는 공간의 동일하나 값이 계속 커진다.

저작자 표시 비영리
신고

1.1.1 ~ 1.1.4 리뷰

Review 2010.11.25 01:55
Lisp - LISt Processing
  • Symbolic data 다루기
  • List 타입을 중점으로 다룸 (괄호로 묶인)
  • 문법에 중요성을 두지 않음
  • Prefix notation ( <procedure> <arguments ..> )
  • 식 expression 들을 읽고 셈 evaluation 을 반복 : read-eval-print loop

Special form

define
(define (<name> <formal parameters>) <body>)
  • guess? 같은 네이밍 컨벤션

cond
(cond (<p1> <e1>) (<p2> <e2>) .. (<pn> <en>) )

if
(if <predicate> <consequent> <alternative>)
  • and, or
  • not 예외적으로 procedure

인자 먼저 계산법, 정의대로 계산법
  • 예외적으로 lazy evaluation 경우 정의대로 계산법
신고

티스토리 툴바