2008년 01월 14일
SICP Exercise 연습문제 1.20
이 문제는 정의대로 계산하는 방법(normal-order evaluation)과
인자 먼저 계산(applicative-order evaluation)을 활용하는 문제입니다.
(관련글 : 'SICP Exercise 연습문제 1.5')
최대공약수를 구하는 방법인 유클리드 호제법 프로시저를 만들 때
이것이 정의대로 계산하는 방법을 따를 때와 인자 먼저 계산법을 따를 때
어떤 차이가 있는지 확인합니다.
유클리드 호제법을 프로시저로 구성하면 다음과 같습니다.
(SICP 63쪽)
연습문제는 (gcd 206 40)을 수행할 때
remainder 연산자의 실행 횟수를 물어보았습니다.
(remainder 연산자는 나머지를 구하는 연산자입니다.
예를 들어 'remainder 9 4'의 값은 1입니다.)
문제 순서와 바꾸어 먼저 인자 먼저 계산부터 살펴보았습니다.
(gcd 206 40)
(gcd 40 (remainder 206 40)) - 1
(gcd 40 6)
(gcd 6 (remainder 40 6)) - 1
(gcd 6 4)
(gcd 4 (remainder 6 4)) - 1
(gcd 4 2)
(gcd 2 (remainder 4 2)) - 1
(gcd 2 0)
2
인자부터 계산을 하기에 remainder가 미리 계산될 것입니다.
따라서 두 번째 줄에 (remainder 206 40)이 6으로 바뀌게 됩니다.
줄 끝에 '- n'은 그 줄에서 계산된 remainder의 횟수입니다.
따라서 모두 다 합치면 4번 연산이 된 것으로 나옵니다.
다음으로 정의대로 계산하는 방법에 대해서 알아보겠습니다.
(gcd 206 40)
if (= 40 0)
(gcd 40 (remainder 206 40))
if(= (remainder 206 40) 0) - 1
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
if (= (remainder 40 (remainder 206 40)) 0) - 2
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) - 4
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) - 7
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))) - 1
(remainder 6 (remainder 40 (remainder 206 40))) - 1
(remainder 6 (remainder 40 6)) - 1
(remainder 6 4) - 1
2
이 역시 결과는 2로 나왔습니다.
하지만 그 과정이 상당히 복잡하네요.^^;;
처음에 적을 때 이런 고민을 했습니다.
'if의 predicate를 수행할 때 remainder를 계산하는가? 뒤로 미루는가?'
- 잠시 얘기할 것(SICP 25쪽)
if는 'if <predicate> <consequent> <alternative>'로 되어있습니다.
(if (= 1 0) 0 1)일 때 <predicate> : (= 1 0), <consequent> : 0, <alternative> : 1
마지막에 기본 연산(primitive operator)으로만 이루어진 식을 만든다는 설명에
remainder는 어떻게 해야하는가 고민했던 것입니다.
하지만 값이 필요할 때까지 피연산자들을 계산하지 않고 미룬다는 말에
if의 predicate는 값이 필요할 때라 생각했습니다.
이를 바탕으로 이렇게 생각하였습니다.
gcd 프로시저를 실행시키면 처음으로 if문을 검사합니다.
그래서 두 번째 줄에 'if (= 40 0)'라 적었습니다.
40은 0이 아니기에 alternative 식을 계산합니다.
그 결과 (gcd 40 (remainder 206 40))이 나옵니다.
(gcd 40 (remainder 206 40))을 시작하면 다시 if문이 나옵니다.
하지만 이번에는 'if(= (remainder 206 40) 0)'입니다.
왜냐하면 b가 '(remainder 206 40)'이기 때문입니다.
predicate의 참거짓을 판단하기위해 remainder 연산자를 사용합니다.
그 후 연산자의 결과값으로 나온 6이 0과 같지 않으므로 false를 내놓습니다.
하지만 b는 변하지 않습니다.
즉, b가 '(remainder 206 40)'이고 이미 계산을 하였지만,
이는 = 연산자 안에서 수행된 것이기에 gcd 프로시저의 b는 변화가 없습니다.
따라서 alternative 식인 (gcd b (remainder a b))에 따라
'(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))'로 적히는 것입니다.
그래서 위처럼 상당히 긴 식이 나왔습니다.
인자 먼저 계산법때처럼 '- n'으로 remainder의 수행횟수를 기록하였습니다.
다 더하니 18이 나오는군요.^^
제 답은 심하게 복잡합니다.
따라서 다른 이의 답안을 추천합니다.
'Solution to SICP Exercise 1.20'
참조
Structure and Interpretation of Computer Programs 2/E - Page 64
PS
이 문제는 정말 친절하더군요.
이런 문장이 문제 속에 있습니다.
'(if를 정의대로 계산하는 방법은 연습문제 1.5에 있다.)'
이 문장 덕분에 관련 내용을 좀 더 빠르게 찾을 수 있었습니다.^^
# by | 2008/01/14 16:22 | in OCW | 트랙백 | 덧글(2)
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
그런데 gcd가 뭔지 모르겠어요.. 무식해서; 유클리드 호제법 프로세서인가요?
네.. 그 방법에 따라 저렇게 달라진다는군요.
연습문제 1.5를 보시면 방법 차이에 따라 무한루프를 도느냐 아니냐가 결정됩니다.;;;
GCD는 Greatest Common Divisor(최대공약수)의 준말입니다.
네.. 유클리드 호제법 프로시저입니다.^^