Extremely Agile:

비슷한 종류의 사례로 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)