Books by Example/SICP2007.12.16 03:55

연습문제 1.21은 너무 쉬우므로 생략합니다. 1.22는 이미 있는 소스 코드를 가지고 search-for-primes라는 프로시저를 작성하는 것입니다. 기존의 프로시저를 아무 수정없이 사용할 수는 없는데, 그것은 start-prime-test가 검사 대상 수 n이 prime이 아닐 때 false를 반환하도록 구현되어 있지 않기 때문입니다. 그래서 아래의 소스 코드 붉은 색으로 표기된 부분에 false를 반환하는 코드를 넣었습니다. (저것말고 더 쉬운 방법이 있을텐데 지금으로선 잘 모르겠네요. ㅋ)

아 그리고, PLT-scheme은 SICP 책에 나오는 runtime이라는 함수를 제공하지 않습니다. 대신 current-seconds나 current-milliseconds같은 함수들을 제공합니다. (language를 PLT 아래에 있는 것 중 하나로 선택하면 사용할 수 있습니다.) 그래서 그 함수들을 사용하도록 코드를 고쳤습니다. (아래에 녹색 표시된 부분)

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n) (= (smallest-divisor n) n))

(define (timed-prime-test n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime n (- (current-milliseconds) start-time))
      (= 1 0)))

(define (report-prime n elapsed-time)
  (newline)
  (display n)
  (display " is prime and ")
  (display elapsed-time)
  (display " milli-seconds have passed"))

(define (search-for-primes start-from count)
  (if (> count 0)
      (if (even? start-from)
          (search-for-primes (+ start-from 1) count)
          (if (timed-prime-test start-from)
              (search-for-primes (+ start-from 2) (- count 1))
              (search-for-primes (+ start-from 2) count)))))

(display (sqrt 10))
(search-for-primes 1000000000 3)
(newline)
(search-for-primes 10000000000 3)
(newline)
(search-for-primes 100000000000 3)
(newline)
(search-for-primes 1000000000000 3)

맨 마지막의 8줄은 실행 결과를 확인하기 위한 부분입니다. sqrt 10이 대략 3입니다. search-for-primes의 실행 결과는 탐색이 시작되는 수의 자릿수가 10이 증가할 때 마다 대략 3배씩 늘어납니다. (따라서, 책에서 '정말 그러한가?'하고 묻는 부분에 대한 답은 'yes'라고 할 수 있겠습니다.)

아이가 아파서 늦게까지 잠을 잘 수가 없었는데, 이제 열도 떨어지고 했으니 그만 자야겠습니다.


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. runtime이 안되어 고생하였는데 먼저 해결책을 알려주셔서 고맙습니다.^^ㅜㅜ

    2008.01.17 15:20 신고 [ ADDR : EDIT/ DEL : REPLY ]