SICP: 뉴턴 방법으로 제곱근구하기

수학의 함수와 비교되는 컴퓨터 함수의 특징은 효과적이라는 것이다.

제곱근을 구하는 함수는 다음과 같이 정의할 수 있다.

수학 함수의 정의

sqrt(x) = y ≥ 0 이고 y ** = x라는 조건을 층족하는 y

컴퓨터 함수의 유사 자바스크립트 함수

function sqrt(x) {
	return y >= 0 && sqaure(y) === x 라는 조건을 충족하는 y
}

이처럼 수학 함수의 정의가 컴퓨터 함수를 서술하지 않는다.

수학 함수와 컴퓨터 함수 사이에는 사물의 성질을 서술하는 것과 구하는 방법을 서술하는 것의 차이가 있다.

수학에서는 주로 선언적 서술이 주를 이루고, 컴퓨터 과학에서는 주로 명령적 저술에 관심이 있다.

뉴턴 방법으로 제곱근을 구하는 방법은 제곱근의 근삿값을 거듭 개선해 나가는 것으로, 먼저 수 x의 제곱근이 될 만한 y의 값을 추측하고, y와 x/y의 평균으로 더 나은 추측값을 구하는 과정을 반복한다.

이러한 과정을 자바스크립트 함수로 구현해보면, 피제곱근수에 해당하는 갑 하나와 추측값에 해당하는 값 하나로 출발해서, 추측값이 충분히 좋다면 과정을 끝내고, 그렇지 않으면 추측과정을 반복한다.

이런 과정을 구현하면 다음과 같다.

function sqrt_iter(guess, x) {
	return is_good_enough(guess, x)
					? guess
					: sqrt_iter(improve(guess, x), x);
}

sqrt_iter 함수는 improve함수와 is_good_enough함수를 사용한다.

improve 함수는 개선된 추측값을 돌려주는 함수로, 추측값과 피제곱근수를 추측값으로 나눈 몫의 평균을 계산한다.

function improve(guess, x) {
	return average(guess, x/guess);
}

function agerage(x, y) {
	return (x + y) / 2;
}

is_good_enough 함수는 현재 추측값이 충분한지 판정하고, 충분을 판정하는 기준은 추측값의 제곱과 피제곱근수의 차이가 0.001 이하이다.

function is_good_enough(guess, x) {
	return abs(square(guess) - x) < 0.001;
}

마지막으로 이러한 과정을 반복해줄 함수가 필요하며, 아래와 같이 구성할 수 있다.

function sqrt(x) {
	return sqrt_iter(1, x);
}

해당 함수 구성은 반복 구조는 하나도 없지만 어떤 작업을 되풀이해서 수행할 수 있도록 루프문 없이 함수를 호출하는 것만으로도 반복을 구현할 수 있음을 보여준다.

삼항 연산자 없이 구성

p1 : e1 ? e2;

해당 삼항 연산자를 함수로 구현하면 다음과 같다.

function conditional(predicate, then_clause, else_clause) {
	return predicate ? then_clause : else_clause;
}

사용 예시

conditional(2 === 12, 0, 12);

conditional(3 !== 12, 3, 12);

삼항 연산자를 함수로 대체하여 sqrt함수를 구현하면 아래와 같이 구현할 수 있다.

function conditional(predicate, then_clause, else_clause) {
  return predicate ? then_clause : else_clause;
}

function sqrt_with_conditional(x) {
  return sqrt_iter_with_conditional(1, x);
}

function sqrt_iter_with_conditional(guess, x) {
  return conditional(
    is_good_enough(guess, x),
    guess,
    sqrt_iter_with_conditional(improve(guess, x), x)
  );
}

하지만 해당 함수는 스택오버플로우 오류가 발생하는데, 그 이유는 sqrt_iter_with_conditional 함수의 인자가 결정되지 않고, 내부적으로 sqrt_iter_with_conditional 계속 호출하여 함수 호출 스택을 쌓아가는 구조가 되며, 할당된 스택 용량을 초과하게 되면 오버플로우 오류가 발생하게 된다.

호출 횟수를 카운팅해보면 다음과 같은 결과가 나온다.

 

 

6127번 호출 후, 오버플로우 오류가 나오는 것을 알 수 있다.

sqrt 함수 간략화

sqrt 함수를 구현하기 위한 여러 내부 함수들은 사용자들에게 노출될 필요는 없다. 따라서 sqrt함수 내부의 블록에 위치시킴으로서 사용자에게 노출되는 것을 방지한다.

또한 sqrt 함수의 인수인 x를 공통으로 사용 함으로서 함수의 인자를 하나 줄여볼 수 도 있다.

function sqrt(x) {
  function sqrt_iter(guess) {
    function improve(guess) {
      return average(guess, x / guess);
    }

    function average(x, y) {
      return (x + y) / 2;
    }

    function is_good_enough(guess) {
      return abs(square(guess) - x) < 0.001;
    }

    function square(x) {
      return x * x;
    }

    function abs(x) {
      return x >= 0 ? x : -x;
    }

    return is_good_enough(guess)
      ? guess
      : sqrt_iter(improve(guess));
  }
  return sqrt_iter(1, x);
}