Books by Example/SICP2007.11.15 22:27
1.16번

연습문제 1.16은 b를 n번 곱하는 문제의 복잡도를 어떻게 n에서 log n 으로 (밑수는 2)로 낮출 수 있느냐 하는 문제입니다. b * b * b * b * ... 이렇게 하는 대신 b를 계속해서 제곱해 나가다가 (b --> b^2 --> b^4 --> ... ) 마지막에 n이 홀수냐 짝수냐에 따라서 그 결과에 b를 한 번 더 곱해주거나 아니면 그냥 놔두거나 하면 되겠죠.

굉장히 간단한 아이디어입니다만, 의외로 실무에서 프로그래밍을 하다 보면 이렇게 간단한 부분도 놓치게 되는 일이 많은 것 같습니다.

비슷한 종류의 사례로 strcat에 관한 것도 있는데, 이에 대해서는 "조엘 온 소프트웨어"라는 책에 보면 나옵니다. strcat이 보통 '널 문자'를 찾기 위해 포인터를 문자열 앞에서 뒤 방향으로 계속 검색해 나가는데, 그런 이유로 strcat을 여러번 적용하면 문자열을 여러 개 합칠 경우 그 계산 복잡도가 n^n으로 바뀌고 만다, 뭐 그런 이야기였습니다.

아무튼 이 문제의 Scheme 식 해답은 다음과 같습니다.

(define (fast-expt-iter b n)
  (define (fast-expt-iter-part b m c)
    (cond ((= c 0) m)
          ((even? c) (fast-expt-iter-part (* b b) m (/ c 2)))
          (else (fast-expt-iter-part b (* b m) (- c 1)))))


  (fast-expt-iter-part b 1 n))

(fast-expt-iter 2 32)

"되도는 알고리즘보다 반복하는 알고리즘을 짜는 것이 더 어렵다"고 해서 (사실 그렇습니다) 문제 풀기전에 좀 겁먹었습니다만, 문제 자체가 쉬워서 크게 어려울 것은 없었습니다.

1.17번, 1.18번

그러면 a * b를 그런 식으로 계산할 수도 있겠군요. a * b를 덧셈만으로 구현한다고 하면 a를 b 번 더해나가야 되겠습니다만, a를 2a, 4a, 이런 식으로 계속 두 배 해 나가는 식으로 하면 더 빨리 돌도록 구현할 수 있겠습니다. 원래는 17번은 재귀 프로세스, 18번은 반복 프로세스로 구현하는 것인데, 재귀 프로세스로 구현하는 것은 반복 프로세스로 구현하는 것에 비해 쉬으므로, 반복 프로세스로 구현하는 경우만 보였습니다.

(define (double x) (* 2 x))

(define (halve x) (/ x 2))

(define (mul a b)
  (define (f adder result count)
    (cond ((= count 0) result)
          ((even? count) (f (double adder) result (halve count)))
          (else (f adder (+ result adder) (- count 1)))))
  (f a 0 b))

(mul 3 7)

신고
Posted by 이병준

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