[알고리즘/JavaScript] 제곱근 구하기

어제 코플릿 문제를 풀다가 재밌는 문제와 마주쳤다. Math.sqrt() 메서드를 사용하지 않고 제곱근을 구하는 알고리즘을 짜는 문제였다. 어제 풀때는 페어 프로그래밍을 하고 있어서 그냥 코드만 이해하고 넘어갔고, 오늘 그 원리에 대해 좀 더 살펴보았다.

제곱근 근삿값 구하기

- 5의 제곱근을 직접 구하자

핵심은 점점 근삿값의 범위를 줄여나간다는 데에 있다.

5.14의 제곱근을 구한다면..

1) 5.14의 제곱근의 정수 자리를 구한다.
우리는 루트5가 대강 2와 3 사이에 있다는 것을 안다. 정확한 루트5의 값은 몰라도, 루트5를 제곱한 5가 2의 제곱과 3의 제곱 사이에 있기 때문에 그렇게 유추할 수 있다.

(2의제곱)4 < 5 < (3의제곱)9

2 < 루트5 < 3

2) 이제 5의 제곱근이 2.xxxx..라는 것을 알게 되었다. 이것을 바탕으로, 제곱근 값을 소숫점 첫번째자리까지 구한다.
소숫점 첫번째자리까지면 2.0~2.9 사이일 것이다. 따라서, 2.0과 2.1 사이에 있는지, 2.1과 2.2 사이에 있는지 계속 비교하다보면 소숫점 첫번째자리를 알 수 있다.

(2.2의 제곱) 4.8 < 5 < (2.3의 제곱) 5.3

2.2 < 루트5 < 2.3

5.14의 제곱근은 2.2와 2.3 사이에 있을 것이다.

3) 이제 5의 제곱근이 2.2xxx...라는 것을 알게 되었다. 이것을 바탕으로 제곱근 값을 소숫점 두번째자리까지 구한다. 2.20부터 2.29까지 제곱한 값을 살펴 보면서, 5가 중간에 들어갈 수 있는 값을 찾는다.

(2.23의 제곱)4.97 < 5 < (2.24의 제곱)5.01

2.23 < 루트5 < 2.24

4) 3)까지의 과정을 통해 우리는 5의 제곱근이 2.23xxx임을 알게 되었다. 우리는 소숫점 세번째에서 반올림하여 소숫점 두번째까지 구해야 하므로 소숫점 세번째까지 구해야 한다. 2.230부터 2.239까지 제곱한 값을 살펴 보면서, 5가 중간에 들어갈 수 있는 값을 찾는다.

2.234의 제곱 = 4.9907
2.235의 제곱 = 4.995225
2.236의 제곱 = 4.9996
2.237의 제곱 = 5.04169

(2.236의 제곱) 4.9996 < 루트 5 < (2.237의 제곱) 5.04169
2.236 < 루트5 < 2.237

자, 이제 우리는 5의 제곱근이 2.236xxxxx라는 사실을 알게 되었다. 소숫점 세번째자리에서 반올림을 하면 2.237이다.

-수도코드로 만들어보자

위의 과정을 좀 더 명확하게 정리하면 다음과 같다.

1. 처음에는 a=0으로 두고 num이 a와 a+1 사이의 값인지 확인한다.
   1) a<num<a+1을 만족하는 a를 찾으면 해당 num의 근삿값은 a와 a+1 사이가 된다.
   2) a<num<a+1을 만족하지 않으면, a에 1을 더하고, 1)로 돌아간다.
2. 정수 부분을 확인했으니 이제 소숫점 첫번째 자리를 찾는다. num이 a와 a+0.1 사이의 값인지 확인한다.
   1) a<num<a+0.1을 만족하는 a를 찾으면 해당 num의 근삿값은 a와 a+0.1 사이가 된다.
   2) a<num<a+0.1을 만족하지 않으면, a에 0.1을 더하고, 1)로 돌아간다.
3. 소숫점 두번째 자리를 찾는다. num이 a와 a+0.01 사이의 값인지 확인한다.
   1) a<num<a+0.01을 만족하는 a를 찾으면 해당 num의 근삿값은 a와 a+0.01 사이가 된다.
   2) a<num<a+0.01을 만족하지 않으면, a에 0.01을 더하고, 1)로 돌아간다.
4. 소숫점 세번째 자리를 찾는다. num이 a와 a+0.001 사이의 값인지 확인한다.
   1) a<num<a+0.001을 만족하는 a를 찾으면 해당 num의 근삿값은 a와 a+0.001 사이가 된다.
   2) a<num<a+0.001을 만족하지 않으면, a에 0.001을 더하고, 1)로 돌아간다.
5. 소숫점 세번째 자리에서 반올림을 한다.

보면 알겠지만, 각 단계의 1)과 2) 단계는 거의 똑같다. 단지 자릿수에 따라 1, 0.1, 0.01, 0.001을 더한다는 차이점이 있다. 그러면 1, 0.1, 0.01, 0.01을 변수로 만들고, 이 단계를 하나로 합칠 수 있다.

const digit = [1, 0.1, 0.01, 0.001]
let a = 0;  // 자릿수

for (자릿수 d of digit){
	while ( a의 제곱이 num보다 작은 경우) {
    	a에 d를 더해준다
    }
    if (a*a가 num인 경우){
    	a*a와 num이 같으면 num의 제곱근이 a인 것이다
        a를 리턴한다
    } else {
    	마지막에 a에 한번 더 d가 더해졌기 때문에 다시 빼준다
    }
}

a의 세번째 소숫점에서 반올림
a 리턴

- 코드로 짜기

function computeSquareRoot(num) {
  const digit = [1, 0.1, 0.01, 0.0.1];
  const a = 0;
  
  for (d of digit) {
  	while ( a*a < num ) {
    	a = a+d;
    }
    if (a*a === num) {
      return a;
    }
    else {
      a = a - d;
    }
  }
  return Number(base.toFiexed(2));
}

Number.prototype.toFixed(digit)
숫자를 반올림한 값을 문자열형태로 반환한다. 인자 digit으로 어느 자리까지 소숫점 표기를 할 것인지 정할 수 있으며, 값의 범위는 0에서 20 사이이다. (지정하지 않으면 0)

let num = 123.456789;
num.toFixed();   // 123
num.toFixed(2);  // 123.46 (소숫점 세번째 자리에서 반올림한다)
num.toFixed(4);  // 123.4568 (소숫점 다섯번째 자리에서 반올림한다)

참고자료

• 코드스테이츠 유어클래스 코플릿
• MDN - Number.prototype.toFixed()