[JavaScript] 바빌로니아 방법으로 제곱근 구하기

오늘 드디어 알고리즘 문제에 도전하기 시작했다.
오늘 풀었던 문제들 중에서 흥미로운 내용이 있어서 따로 정리해보려 한다.

문제

2 이상의 정수를 입력받아 제곱근 값을 소수점 두 자리까지 리턴하는 함수를 만들자.
주의! Math.sqrt 사용은 금지됩니다.

Math.sqrt를 사용하지 않고 제곱근을 구하는 방법은 여러가지가 있다.

• 여기에 제곱근을 구하는 다양한 방법이 자세히 정리되어 있으니 참고할 것

나는 그 중 바빌로니아 방법을 사용하기로 했다.

바빌로니아 방법(Babylonian method)이란?

$\sqrt{S}$ 의 근사값 $x_{n}$을 찾고 다음으로 $x_{n+1}$을 아래와 같은 점화식으로 찾아나가는 방식이다.

$x_{n+1}$ $=$ $1\over 2$ $(x_{n}$ $+$ $S\over x_{n}$ $)$

여기에서, $x_{n}$은 말 그대로 근사값이다. $\sqrt{S}$에 가장 가까울거라 생각하는 근사값을 넣어주면 되는데, 어떤 값을 넣든지 점화식을 반복하다보면 결국 $x_{n+1}$이 $\sqrt{S}$에 가장 가까워지는 순간이 온다. 얼마나 런타임이 빨라지는지 여부는 달라지겠지만..

제곱근 구하기

본격적인 내용에 앞서 내가 작성한 코드부터 보자면 아래와 같다.

function computeSquareRoot(num) {
  let approx = 1;

  while (approx ** 2 !== num) {
    if ( Number((approx*approx).toFixed(2)) === num) {
      break;
    }
    approx = (approx + (num / approx)) / 2;
  } 

  return Number(approx.toFixed(2));
}

가장 먼저 한 일은 점화식을 코드로 바꾸는 일이었다.

변수부터 정리

• ${S}$ = num
• $x_{n}$ = approx
• $x_{n+1}$은 따로 변수를 선언한다기보다는 재할당의 개념으로 생각했다.

JavaScript 코드로 작성

변수가 의미하는 바를 정리했다면 점화식을 코드로 바꾸는 일은 간단하다.

approx = (approx + (num / approx)) / 2;

$\sqrt{S}$ 의 근사값 $x_{n}$(approx)은 ${S}$를 안다면 느낌적인 느낌으로 지정할 수 있겠으나, ${S}$값(num)을 알 수 없으므로 단순하게 $1$을 대입하기로 했다.

let approx = 1;

이제 $x_{1}$부터 $x_{n}$까지 점화식을 반복해나가야 하는데, 정확히 $n$값을 알 수 없으니 while을 사용해서 반복문을 돌려주기로 했다.
while문의 body가 수행되는 조건은 approx의 제곱이 num과 같지 않을 경우로 한다.

⚠ 주의! 이때 그냥 while문을 돌리면 무한루프 지옥에 빠지게 된다. (경험담이다)
무한루프를 도는 이유는 approx가 근사값이기 때문이다. 즉, num이 정수의 제곱이 아닌 이상 num과 완벽히 같아질 수는 없다는 말이다.

무한루프 지옥에 빠지지 않기 위해 while문 안에서 조건을 걸어 break를 적용해주어야 한다. 조건은 approx의 제곱이 num에 가장 근사했을 경우로 정했는데, 나는 그 기준을 "approx의 제곱을 소수점 둘째 자리 이하에서 반올림 했을 때 num과 같아진다"로 정했다.

while (approx ** 2 !== num) {
  if ( Number((approx*approx).toFixed(2)) === num) {
    break;
  }
  approx = (approx + (num / approx)) / 2;
} 

• number.toFixed(n)
  숫자를 문자열로 변환하면서 지정된 소수점 이하 숫자를 반올림하여 출력한다.

return Number(approx.toFixed(2));

while문을 거치며 변수 approx에는 문자열 형태의 num의 제곱근의 근사값이 담기게 된다. 최대 소수점 둘째 짜리까지만 구하기 위해 approx에 .toFixed(2)를 사용하고, 함수의 리턴값은 number 타입이어야 하므로 Number() 함수를 사용해 문자열을 숫자형으로 바꾸어 리턴해주면 끝.

마치며

수학 법칙을 이용해서 코드를 작성하는 것이 마냥 어려운 일일거라 생각했는데, 차근차근 단계를 나눠 적용하니 생각보다 단순한 과정이었다. 하다보면 더 간결하고 좋은 코드를 적용할 수 있을거라 기대하며
-끝- 💕