컴퓨터 과학에서 제곱근을 구하는 방법

우리는 흔히 제곱 수를 구 할때 언어를 막론하고 sqrt라는 함수를 사용한다. 고맙게도 이러한 내장 함수들이 있기 때문에 별 고민없이, 빠르게 코딩 할 수 있었다. 그러나 궁금했다. 어떻게 제곱수를 구하는지 컴퓨터가 제곱수를 한번에 구하는 것은 아닐테고 분명 간단한 사칙연산을 이용해서 구할텐데 어떻게 구하는지 살펴보자.

제곱근이라는 것은 어떤수 y를 제곱했을 때 x가 나오는 경우, y를 x의 제곱근이라고한다.

즉, x = y^2이다.

여기서 식을 조금 변형하면

x/y = y이다.

여기서 보면 x/y와 y가 같은데, 다시 표현하자면 결국 x의 제곱근인 y를 구하는 것은

x/y와 y가 같게하는 y를 구하는 과정이라고 할 수 있다.

일련의 과정을 통해서 구할 수 있는데 코드는 다음과 같다.

x = int(input())

def test(x, g):
    if closeEnough(g, x/g):
        return g
    else:
        return test(x, betterGuess(x, g))


def closeEnough(a,b):
    return abs(a-b) < 0.001


def betterGuess(x,g):
    return ((g + x/g) /2)

파이썬으로 짠 코드이고 입력 x가 input으로 들어올 때 x의 제곱근을 구한다.

코드에서 g는 guess를 의미한다. 즉 정답이 되는 y를 계속 추측(guess)해 가는 과정이다.

1. g와 x/g가 충분히 비슷한지 확인하고 충분히 비슷하다면 g를 return 한다.

2. 만약 충분히 같지 않다면 더 나은 추측값을 찾고 1번으로 돌아간다.

Q : 더 나은 추측 값을 찾는 방법(betterGuess)에서 왜 (g+ x/g) /2를 하는지?

A : x/g이 g와 충분히 가깝지 않은 경우, 어떻게 가깝게 할 것인지 생각해봐야한다. 가까워 지는게 목표니까 평균을 내는구나!!!!!!! x/g와 g의 평균을 newGuess값으로하면 가까워 질 수있다.

원본 : http://www.cs.wustl.edu/~kjg/CS101_SP97/Notes/SquareRoot/sqrt.html