1.5 예제: 뉴턴의 방법을 사용한 제곱근

뉴턴의 방법

알고리즘

sqrt(x) = y 를 구하기 위해
1. 초기 예측값 선정 (y=1 로 선택)
2. 다음 예측값 = mean(y, x/y) 을 반복하다 보면 점점 정확해 짐

 

예제

sqrt(2) 를 계산해 보자.

EstimationQuotientMean

Estimation	Quotient	Mean
1	2 / 1	1.5
1.5	2 / 1.5 = 1.333	1.4167
1.4167	2 / 1.4167	1.4142
1.4142	...	...

 

코드

def abs(x: Double): Double = if x > 0 then x else -x

def isGoodEnough(x: Double, guess: Double): Boolean =
  abs(guess * guess - x) < 0.001

def improve(x: Double, guess: Double): Double =
  (guess + x / guess) / 2

def sqrtIter(x: Double, guess: Double): Double =
  if isGoodEnough(x, guess) then guess
  else sqrtIter(x, improve(x, guess))

def sqrt(x: Double) = sqrtIter(x, guess = 1.0)

@main def Main(): Unit = {
  println(sqrt(2))  // 1.414
}

 

 

Exercise

1. isGoodEnough 는 작은 숫자에 대해서는 정확하지 않고, 아주 큰 숫자에 대해서는 종료되지 않을 수도 있다. 왜 그런지 설명해 보라. (hint: 부동 소수점 숫자)
2. 위의 문제를 보완할 수 있는 isGoodEnough 를 다시 설계해 보라.
3. 보완한 isGoodEnough 를 이용해 다음 숫자들로 테스트 해 보라.

0.001
0.1e-20
1.0e20
1.0e50