MIT 컴퓨터 공학 1학년 교재로 사용된다는 SICP. (Structure and Interprecation of Computer Programs)
번역본까지 출판되어 잘 팔리고 있는 책.
문제가 되지 않는 선에서 간략히 필자의 노트 필기 차원에서 여기에 정리함.
책에서는 Lisp 으로부터 파생된 (방언이라 표현하던데) scheme 으로 예제들이 정리가 되어있는데,
필자는 Scala 로 풀어보았음. - scala 소개는 본 블로그의 scala 문법 참고.
초반부 - Lisp 소개와, scheme 의 기본 문법소개, 그리고 전위 연산 표기 소개등.
정의대로 계산법 (normal-order evaluation), 인자 먼저 계산법 (applicative_order evaluation)
def sum_of_square(a: Int, b: Int) = {
a*a + b*b
}
sum_of_square(5+5, 2+3)
와 같이 작성했을때
정의대로 계산법은
1. (5+5)*(5+5) + (2+3)*(2+3)
2. 10*10 + 5*5
3. 100 + 25
4. 125
와 같이 좁혀지며 계산되며
인자 먼저 계산법은
1. 10*10 + 5*5
2. 100 + 25
3. 125
와 같이 계산된다.
예제 1.3
세 숫자중 2개의 큰 숫자를 제곱하여 합하라
def examplePowSum(a: Int, b: Int, c: Int): Int = {
def iter(x: Int, y: Int, last: Boolean): Int = {
def pow(a: Int): Int = {
a * a
}
if (last) if (x > y) x else y
else if (x > y) pow(x) + pow(iter(y, c, true))
else pow(y) + pow(c)
}
iter(a, b, false)
} //> examplePowSum: (a: Int, b: Int, c: Int)Int
examplePowSum(1, 3, 2) //> res0: Int = 13
examplePowSum(2, 1, 5) //> res1: Int = 29
examplePowSum(1, 4, 3) //> res2: Int = 25
좋은 풀이는 아니다. 재귀를 이용하고 싶은 욕구? 에서 작성한 코드.
예제 1.5
정의대로 계산법과 인자 먼저 계산법에서의 다음 연산의 차이
(define (p) (p))
(define (test x y)
(if (= x 0)
0 y))
Then he evaluates the expression
(test 0 (p))
scheme 에서 define 시에 괄호로 감싸면 단순 상수 선언이 아니라 프로시저라는 의미가 있다.
즉 p 는 p 를 리턴하는 프로시저의 선언이며 ( 재귀 )
(test 0 (p)) 와 같을때 ( in scala , - test(0, p) )
정의대로 계산법의 경우 인자 연산을 미루고 test 프로시저(메서드)가 호출된다.
x = 0 이므로 consequent 가 호출된다. ( then - clauses ) 0을 리턴하고 함수호출이 종료되며,
인자 먼저 계산법의 경우 인자 연산부터 수행하므로 if 문에 들어가기 전에 p 를 평가하려고 하며,
자기 자신을 호출하는 p 로 인해 무한루프에 빠지게 된다.
이 문제에서 볼 수 있듯 인자 먼저 계산법의 경우 결국 계산되지 않아도 되는 연산이 이뤄질 수 있으며,
반대로 정의대로 계산법의 경우 중복되는 연산을 불필요하게 수 회 호출 할 수 있다는 문제가 있다.
1.1.7 - Square Roots by Newton's Method
어떤 수 x 의 제곱근을 구하는 방법으로, 뉴튼법이 있다.
일단 어떤 적당한 값으로 나눠보고 (x / guess) , 이 값을 제곱했을때 값과 x 의 차이가 오차범위 이내이면 이 값을 제곱근으로 리턴하고,
그렇지 않으면 나눈 결과 값과 추측값의 평균값을 구한다. ( (x / guess + guess) / 2 )
이 평균값을 다시 추측값으로 하여 전 과정을 오차범위 이내일때까지 반복한다.
-> 장황하지만 간단히 얘기해서, 어떤 값으로 나눠본 결과가 터무니 없으면 그 어떤값과의 평균값으로 보정하는 과정을 반복하는 것이다.
-> 정확한 값이라면 (x/guess + guess) / 2 는
와 같이 전개되어 결국 원하는 값이 된다.
스칼라로 표현하면
def newton = {
def sqrt(x: Int) = {
def iter_sqrt(guess: Float, x: Int): Float = {
def improve(guess: Float): Float = {
println("guess : " + (x / guess + guess)/2)
(x / guess + guess)/2
} // improve
def good_enough(guess: Float):Boolean = {
def pow(a: Float) = {
a*a
}
if (Math.abs(pow(guess) - x) < 0.001) true else false
}
if (good_enough(guess))
guess
else
iter_sqrt(improve(guess), x)
} //iter_sqrt
iter_sqrt(1, x)
}
sqrt(2)
} //> newton: => Float
newton //> guess : 1.5
//| guess : 1.4166667
//| guess : 1.4142157
//| res3: Float = 1.4142157
와 같이 된다.
예제 1.6 new-if 로 scheme 의 if cond 를 다음과 같이 직접 작성했다.
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
만약 이 new-if 를 newton's method 에 적용한다면 ?
인자 먼저 계산법의 경우 무조건 iter_sqrt 를 먼저 호출하려고 할 것이며 따라서 무한 루프에 빠지게 된다.
예제 1.7 뉴튼법은 큰 숫자나 작은 숫자엔 적용하기 어렵다. 그 예를 들어 과정을 설명하고, 개선해보라.
* 작은 숫자
매우 작은 숫자 0.0000001 을 넣었을때, 오차 범위로 주어진 0.001 은 충분한 과정을 진행하지 못한채로 good-enough? 의 값을 true 로 리턴해버릴 것이다.
sqrt(0.0000001f)
를 위 프로그램에 실제로 넣었을때
> guess : 0.50000006
//| guess : 0.25000012
//| guess : 0.12500025
//| guess : 0.06250053
//| guess : 0.031251065
//| res3: Float = 0.031251065
가 리턴되었지만,
이 값의 제곱은 0.0009765625 에 불과하다. 0.0000001 과는 거리가 상당하다.
* 큰 숫자
아주 큰 수를 넣었을때 컴퓨터 산술 연산의 제한된 정확도로 인해 문제가 생긴다.
정확히는 모르겠지만 실제로 돌려본 결과는 다음과 같았으며 improve 의 연산이 제 역할을 못하고 있었다.
improve 는 (x / guess + guess) / 2 였으며, 여기의 나눔연산후 일부 값을 버린다거나 해서 ?
예를들어 7E15/8E7 과 같은 수가 있다고 할때 식은 정확히 8.75E7 + 8E7 / 2 가 된다.
이때 .75가 버려지면 improve 의 결과는 다시 되돌아 오게되며, 즉 8E7 이 되어 무한 루프에 빠진다.
sqrt(7000000000000000f)
//> guess : 3.49999999E15
//| guess : 1.74999999E15
//| guess : 8.75E14
//| guess : 4.37499999E14
//| guess : 2.18749999E14
//| guess : 1.09375E14
//| guess : 5.46875E13
//| guess : 2.73437499E13
//| guess : 1.3671875E13
//| guess : 6.8359375E12
//| guess : 3.41796874E12
//| guess : 1.70898437E12
//| guess : 8.5449218E11
//| guess : 4.27246092E11
//| guess : 2.13623046E11
//| guess : 1.06811539E11
//| guess : 5.3405802E10
//| guess : 2.67029668E10
//| guess : 1.33516145E10
//| guess : 6.6760694E9
//| guess : 3.33855898E9
//| guess : 1.67032781E9
//| guess : 8.3725933E8
//| guess : 4.22809984E8
//| guess : 2.19682944E8
//| guess : 1.2577352E8
//| guess : 9.071456E7
//| guess : 8.393984E7
//| guess : 8.3666448E7
//| guess : 8.3666E7
//| guess : 8.3666E7....
//| Output exceeds cutoff limit.-
* 개선
improve 의 호출로 인한 변화가 아주 미미할때 반복을 멈추는 코드를 작성하라고 한다.
( An alternative
strategy for implementing good-enough? is to watch how guess changes from one iteration to the
next and to stop when the change is a very small fraction of the guess. )
번역을 잘못했는지? ;; 멈추기만 하는것은 무한루프만 벗어나게하는, 결론적으로 원하는 결과(제곱근)를 얻을 수는 없다.
어쨌든 시키는대로? 하면, 다음 라인을 추가하도록 한다.
else{
val new_guess = improve(guess)
if (Math.abs(new_guess - guess) < guess * 0.1)
guess
else
iter_sqrt(improve(guess), x)
}
실행결과는 -1 이다.
예제 1.8 세제곱근을 구하는 공식은 (x/y^2 + 2y)/3 과 같다. 작성해보아라.
good_enough 와 improve 의 내용만 위 공식으로 교체하면 된다.
def newton3 = {
def sqrt(x: Float) = {
def iter_sqrt(guess: Float, x: Float): Float = {
def improve(guess: Float): Float = {
var avg = (x / (guess*guess) + 2*guess)/3
println("guess : " + avg)
avg
} // improve
def good_enough(guess: Float):Boolean = {
def pow(a: Float) = {
a*a*a
}
if (Math.abs(pow(guess) - x) < 0.001) true else false
}
if (good_enough(guess))
guess
else
iter_sqrt(improve(guess), x)
} //iter_sqrt
iter_sqrt(1, x)
}
sqrt(10)
} //> newton3: => Float
newton3 //> guess : 4.0
//| guess : 2.875
//| guess : 2.3199432
//| guess : 2.1659615
//| guess : 2.154496
//| res4: Float = 2.154496
