연습문제 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)
'Books by Example > SICP' 카테고리의 다른 글
| SICP Exercise : 연습문제 1.22 (2) | 2007/12/16 |
|---|---|
| SICP Exercise : 연습문제 1.19 (1) | 2007/11/17 |
| SICP Exercise : 연습문제 1.16, 1.17, 1.18 (0) | 2007/11/15 |
| SICP Exercise : 연습문제 1.12 (0) | 2007/11/10 |
| SICP Exercise : 연습문제 1.11 (2) | 2007/11/10 |
| SICP Exercise : 연습문제 1.8 (8) | 2007/11/09 |
TRACKBACK http://www.buggymind.com/trackback/77
-
SICP Exercise 연습문제 1.16 삭제
2008/01/13 22:53TRACKBACK FROM NoSyu의 주저리 주저리1.15는 쉽게 계산이 되기에 생략하였습니다. 1.16은 거듭제곱을 구하는 프로세스를 만드는 것입니다. 조건은 반복 프로세스이고 빠른 방법을 써야한다는 점입니다. 여기서 빠른 방법은 다음과 같습니다. b^n 즉, b의 n 거듭제곱을 구할 때 n이 짝수이면 지수를 반으로 나눠 제곱하고, n이 홀수이면 지수에 1을 빼고 밑수를 곱하는 방법입니다. (SCIP 57쪽) 여기에 맞춰 프로시저를 만들었습니다. &nb...
-
SICP Exercise 연습문제 1.17, 1.18 삭제
2008/01/14 10:47TRACKBACK FROM NoSyu의 주저리 주저리연습문제 1.16과 1.17, 1.18은 이어지는 문제이지만, 시간 문제로 1.16만 먼저 풀었던터라 따로 글을 적습니다. 1.17과 1.18은 앞에서 배웠던 거듭제곱 계산법을 곱셈에 적용시킨 문제입니다. 거듭제곱이라는 것이 곱셈을 여러 번 한것처럼 곱셈 역시 덧셈을 여러 번 한것과 같기 때문에 조금만 수정하면 됩니다. fast-multi가 1.17의 답 i-fast-multi가 1.18의 답입니다. 배운...
댓글을 달아 주세요