SICP 연습문제 1.7 풀이
good-enough
Lisp보다 익숙한 Python을 이용해 문제를 다뤄볼 예정이다.
연습문제 1.7
앞서 살펴본 문제 중 good-enough? 로는 아주 작은 수나 아주 큰 수의 제곱근은 구할 수 없다. 문제가 되는 예시를 하나 들어보자.
더 올바른 good-enough?를 만드는 방법으로는 참값에 더 가까운 값 guess를 구하기 위해 어림잡은 값을 조금씩 고쳐 나가면서 그다지 나아지지 않을 때까지 계산을 이어가는 것이다. 더 올바른 good-enough?륾 만들어보자.
해설
문제에 필요한 sqrt 프로시저들을 python으로 아래와 같이 정의할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sqrt(x):
return sqrt_iter(1.0, x)
def sqrt_iter(guess, x):
if good_enough(guess, x):
return guess
else:
return sqrt_iter(improve(guess, x), x)
def good_enough(guess, x):
return abs(guess * guess - x) < 0.001
def improve(guess, x):
return average(guess, x / guess)
def average(x, y):
return (x + y) / 2
문제가 되는 상황 예시
위의 함수를 사용해 0.0001의 제곱근을 구해보자. 실제 정답은 0.01이지만 전혀 엉뚱한 값을 출력한다.
1
2
print(sqrt(0.001))
# 0.03230844833048122
위의 코드에서 임의로 정한 threshold가 0.001이므로 이 근처의 작은 값을 넣으면 올바르게 동작하지 않을 것이 예상된 결과이다.
이번에는 아주 큰 수의 제곱근을 구해보자.
Python에서 maximum recursion 제한을 늘리는 방법
1
2
print(sqrt(123456789012345))
# !infinite loop
sqrt_iter에서 guess 값을 출력해보면 11111111.061111081 에서 더 이상 변하지 않고 무한 루프를 돌게 된다. improve가 더 나은 결과를 돌려주지 못하고 멈추는 이유는 floating point precision 때문인데, floating point의 fraction로 나타낼 수 있는 세밀함의 정도를 넘어서는 값은 표현되지 않는다. 따라서 어느 정도 수렴하는 값에 도달하면 average에서 계산된 값이 이 전 값과 동일한 값이 나오게 되어 더 이상 정답에 근접하지 못하고 수렴하게 된다.
더 나은 good-enough?
위의 예시에서 두가지 문제점을 발견했다. 하나는 threshold로 정한 0.001이 너무 커서 작은 수에 대해 올바른 제곱근을 구하지 못하는 점이고, 또 하나는 floating point recision의 한계로 무한 루프에 빠질 수 있다는 점이다. threshold의 경우 나타낼 수 있는 가장 작은 양의 실수로 설정하여 해결할 수 있을 것이고, 무한 루프의 경우 이 전 guess와 비교하여 값이 수렴한다면 바로 return하도록 수정하면 될 것이다.
1
2
3
4
5
6
7
8
9
10
def better_good_enough(prev_guess, guess):
return abs(prev_guess * prev_guess - guess * guess) <= sys.float_info.min
def sqrt_iter(guess, x):
prev_guess = guess
guess = improve(prev_guess, x)
if good_enough(prev_guess, guess):
return prev_guess
else:
return sqrt_iter(guess, x)
이렇게 적용하고 보니, btter_good_enough를 아래와 같이 정의해도 문제가 없음을 깨달았다.
1
2
def better_good_enough(prev_guess, guess):
return prev_guess == guess
그 결과는 아래와 같다. Python math library로 계산한 값과 일치하는 것을 볼 수 있다.
1
2
3
4
print(sqrt(0.0000001), math.sqrt(0.0000001))
# 0.00031622776601683794 0.00031622776601683794
print(sqrt(12345678901235), math.sqrt(12345678901235))
# 3513641.8288202058 3513641.8288202058