Data Structure / Algorithm - Newton Raphson 알고리즘

---

루트 연산

---

수학에서의 제곱근 연산을 프로그래밍에서 하려면 어떻게 해야 할까?

일반적으로 수학을 할 때 만약 ‘루트 2’의 값을 어떻게 구할 수 있을지 생각해 보자
‘루트 2’는 1.4인 것으로 많은 사람들이 알고 있다.
하지만 이 값이 어떻게 계산해서 나온 값인지는 모르는 사람이 대부분일 것이다.

‘루트 2’의 값을 구하기 위해서 이 값에 대해 정의해 본다면
루트 2는 ‘제곱해서 2가 나오는 값’이다.
x라는 변수를 둔다면 x가 1과 2의 사잇값 중 하나가 될 것이다.

왜냐하면 1의 제곱은 1이고 2의 제곱은 4이기 때문에,
‘제곱해서 2가 되는 수’는 1과 2 사이의 ‘실수’이다.

이번에는 소수점 아래 한자리까지 계산해보자

x = 1.1 -> x^2 = 1.21
x = 1.2 -> x^2 = 1.44
x = 1.3 -> x^2 = 1.69
x = 1.4 -> x^2 = 1.96
x = 1.5 -> x^2 = 2.25

여기까지만 해보면 x가 1.4 ~ 1.5 사이의 값인 것을 알 수 있다.

하지만 이것 또한 정확한 값이 아니다.
애초에 제곱해서 2가 되는 수인 ‘루트 2’는 ‘무리수’이다

무리수란 ‘순환하지 않는 무한소수’라는 뜻

그럼 소수점 아랫자리가 무한하게 나오는 무리수는 어떻게 구해야 할까?
‘오차 범위’를 정의해 두고 그만큼의 오차를 감안해 계산을 끝마쳐 근삿값을 구하는 것이다.

컴퓨터에서 어떻게 계산하는지 살펴보자

double Sqrt_NewtonRaphson(double number)
{
	// 오차 범위 입실론 설정
	const double epsilon = 0.00001;
	// 초기 추정값 설정 (가장 합리적인 시작점)
	double guess = number / 2.0;
	// guess^2과 number의 차이가 오차범위 밖에 있는 동안 반복한다
	while (std::abs(guess * guess - number) > epsilon)
	{
		// guess가 오차범위 밖에 있는 동안 number에 가까워져야 한다
		// 그러기 위한 방법으로 'Newton-Raphson(뉴튼-랩슨)' 알고리즘을 사용한다
		guess = (guess + number / guess) / 2.0;
	}
	// guess^2과 number의 차이가 오차범위 안에 들어왔으니
	// guess를 근사값으로 반환한다
	return guess;
}

이렇게 Newton-Raphson 알고리즘을 통해 무리수를 근삿값으로 계산할 수 있다.
제곱근 하나 구하는데 설정한 오차범위에 따라서 While문을 계속해서 돌려줘야 하므로 오버헤드가 예상된다.