1.15는 쉽게 계산이 되기에 생략하였습니다.

1.16은 거듭제곱을 구하는 프로세스를 만드는 것입니다.

조건은 반복 프로세스이고 빠른 방법을 써야한다는 점입니다.

여기서 빠른 방법은 다음과 같습니다.

b^n 즉, b의 n 거듭제곱을 구할 때

n이 짝수이면 지수를 반으로 나눠 제곱하고,

n이 홀수이면 지수에 1을 빼고 밑수를 곱하는 방법입니다.

(SCIP 57쪽)

여기에 맞춰 프로시저를 만들었습니다.

결과가 제대로 출력됩니다.

그리고 속도가 아주 빠릅니다.

2^1000을 구하는데 있어 아주 빠른 속도로 결과를 보여줍니다.

이는 자람 차수(order of growth)가 Θ(log n)이기 때문입니다.

낭만고양이님이 언급하신 것처럼 반복 프로세스는 대체로 짜기 어렵다는 말에

'이 문제를 푸는데 과연 얼마의 시간이 걸릴까?' 고민부터 하였습니다.

하지만 예상외로 빠른 시간에 풀 수 있었습니다.

(중간에 Lisp 문법 에러가 있었지만....)

(관련글 : 'SICP Exercise : 연습문제 1.16, 1.17, 1.18')

참조

Structure and Interpretation of Computer Programs 2/E - Page 59

PS

해당 연습문제의 첫 문장에 이런 단어가 있습니다.

'되풀이 프로세스'

되풀이 프로세스가 무엇인지 몰라 잠시 고민했습니다.

하지만 본문에 나오는 것은 되돌이 프로세스(recursive process)이니

아마 반복 프로세스(iterative process)가 아닐까 생각했습니다.

원서를 보니 그렇게 적혀있는 것을 확인하였습니다.

여기에 대해 인사이트에 문의메일을 보냈습니다.^^

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.