Exercise 1.17
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure :
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.
1) 문제에서 언급했던 fast-expt procedure. (b^n 을 짝수와 홀수로 나누어 연산하는 procedure)
b^n = (b^n/2)^2 if n is even,
b^n = b x b^n-1 if n is odd.
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (even? n)
(= (remainder n 2) 0))
O(log n) steps and O(log n) space.
2) 문제 중간에서 곱셈을 반복되는 덧셈의 연산의 결과로 만드는 procedure를 fast-expt와 유사하게 바꾸라고 합니다. 그리고 그렇게 하면서 시간복잡도(?)를 O(n)에서 O(log n)으로 바꾸는 문제입니다.
제가 생각했던 procedure는
이거였는데, 연산이 되지 않더라구요. 아무리 생각해서 이게 맞는 것 같아서, 다른 사람들이 푼 것들을 보았는데 저와 비슷하거나 다르게 풀었는데 달랐던 점은,
(* a b)로 하지 않고 "fast-multi" 같이 정의를 통해서 했더라구요.
제가 궁금한 점은,
exercise1.17 중간에서 보여줬듯이 (* a b)를 바꾸어 실행해보니 실행이 되었었는데,
fast-expt와 유사한 procedure를 바꿀려고 할 때, (* a b)로 정의할 때는 안되고
다른 것으로(예를들어 fast-multi) 정의할 때는 되는 이유가 궁금하네요.
일단 제가 추측하는 것은 * 곱셈이라는 연산자가 기본적인 것 때문에, 그러는 것이라는 생각도 들기는 합니다만,
exercise에서 보여준 procedure는 실행이 되니, 제가 생각한 것은 아니라는 건데...
아무리 생각해도 모르겠네요 ㅠㅠ 이것 때문에 이틀 동안 다음 문제로 못넘어갔네요.
알려주시면 감사하겠습니다.
본인삭제금지
글쓰기