제곱근 계산법

기호 참고 : https://jeo96.tistory.com/entry/%EC%88%98%ED%95%99-%ED%91%9C%EA%B8%B0

 

1. 뉴턴-랩슨 근사법(바빌로니아법)

2. 이분 탐색

3. 테일러 전개

세가지 방법을 주로 사용하는 것 같다.

 

1. 뉴턴-랩슨 근사법

구간 $\left[a, b\right]$에서 미분 가능한 함수 f(x) = 0의 근의 근사값을 구하는 방법을 사용한다.

상수 c에 대해 제곱근을 구하고자 한다면, $\sqrt{c}$는 $x^2-c=0$의 근으로 표현할 수 있다.

$f(x)=x^2-c$

$f'(x)=2x$

$\displaystyle x_{n}=x_{n-1}-\frac{f( x_{n-1})}{f'( x_{n-1})}$

$\displaystyle x_{n}=x_{n-1}-\frac{(x_{n-1})^2-c}{2x_{n-1}}$

원소 $x_0$는 구간 $\left[a, b\right]$에서 임의로 선택한다.

좀 더 정리해보자면

$\displaystyle x_{n} = x_{n-1} - \frac{x_{n-1} - \frac{c}{x_{n-1}}}{2}$

$\displaystyle x_{n} = \frac{x_{n-1} + \frac{c}{x_{n-1}}}{2}$

가 된다. 이를 코드로 작성해보면

def sqrt(c, n=4):
  x = c
  
  for i in range(0, n):
    x = (x + c / x) / 2
  
  return x
  
sqrt(2)

로 나타낼 수 있게 된다.

 

2. 이분탐색

알고리즘에서 이분탐색은 너무 유명하기도 하고 간단해서 코드만 보여주겠다.

0부터 c 사이의 범위에서 이분탐색을 진행하면 된다.

def sqrt(c, n=100):
  l = 0
  r = c
  for i in range(0, n):
    mid = (l + r) / 2
    if mid * mid == c:
      break
    if mid * mid < c:
      l = mid
    if mid * mid > c:
      r = mid
  return mid

 

3. 테일러 전개

테일러 급수를 통해서 sin, cos 함수를 근사하는데 자주 사용하는데, 이러한 근사를 제곱근에서도 활용할 수 있다.

$f(x) = x^{\frac{1}{2}}$를 테일러 급수로 만들면

$f(x) = x