뉴턴법 이전의 제곱근 구하기 알고리즘

근대까지도 널리 쓰이던 '개방술'

def easy_sqrt(n: float, precision: int = 10)-> float:
    if n < 0:
        return -1
    if n == 0:
        return 0

    # 고전의 개방술을 그대로 가져온다.

    # square root를 구하기 위해서 ax^2+bx+c = 0 꼴로 두어서
    # a = 1, b = 0, c = -n이라고 한다.

    # 그렇다면 제일 처음 해야 할 것은 정수부를 단순 대입으로 구하는 것이다.
    # 왜 직접 대입하느냐? 어차피 교육용이 아닌 빠른 구현은 뉴턴법을 쓰면 된다.
    # 이것은 알고리즘 기초에 대한 문제이며 Bisection보다 시각적으로
    # 각 자릿수를 구하는 과정을 보여준다.
    # 다만 수렴 속도가 십진 자리수 하나씩 늘어나기때문에 매우 느리다.
    # 고전 수학자들은 이와 같은 알고리즘을 사용하여 자릿수를 구하였으며
    # 에도의 세키 타카카즈와 같은 뛰어난 수학자들은 수렴 시의 패턴을 찾아
    # 가속법을 사용하기도 하였다.

    # 그러나 구장산술은 훨씬 예전에 성립된 방법이며 해석학 등의 것이 필요하지 않으니
    # 쉬운 이해를 위해서 전통을 따른다.

    a = 1
    b = 0

    # 부동소수점 오차 방지
    c = -int(n) if n.is_integer() else -n

    d = 0

    # 정수부
    while (a*(d+1)**2 + b*(d+1) + c) <= 0:
        d += 1

    # y = x - d로 두고
    # 평행이동하라.
    # a(d+y)^2 + b(d+y) + c = a*y^2 + (2ad + b)y + (ad^2 + bd + c)이 된다.
    c = a * d**2 + b * d + c
    b = ((a * d) * 2) + b

    b *= 10
    c *= 100

    digit_count = 0
    i_part = str(d)
    decimal_digits = []

    ## 한번 자릿수가 스케일링될 때마다 한 자리씩 느리게 구해진다.
    # y = Y / 10 대입 후 식에 100 곱하기:
    # x^2이 최고차항이니 10*10 == 100이고, 100 곱한 것과 약분하여 계수 변화는 없음.
    # 그러나 일차항의 경우 10*10 / 10 == 10이니 10만큼 변화.
    # 상수항은 100 그대로 먹어서 100c가 된다.
    # 구장산술 계통의 문헌에 나온다.
    # 구장산술 소광 편의 개평방을 보라.
    # 3차식의 경우 개입방으로 처리 가능하며, 이후 N차 방정식에 대한 근사해를 구하는
    # 개방법으로 일반화되었다.

    while digit_count < precision:


        d_next = 0

        for t_digit in  range(1, 10):
            v = a * t_digit**2 + b * t_digit + c
            # 개방법의 가장 표준적인 절차:
            # 처음으로 다항식에 값을 대입한 것이 음수나 0일 때의 최대 정수를 취하여 자릿수로 쓴다.

            if v <= 0:
                d_next = t_digit
            else:
                break

        # 지정된 정밀도 범위 내에서 1자리씩 수렴한다.
        # 만약 10000자리까지 구한다고 하면 이와 같은 과정을 10000번 반복해야 한다.
        # 임의 정밀도 정수를 쓰면 오차 없이 자릿수를 계속 뽑아낼 수는 있으나,
        # 한 번의 루프에 정확히 1자리씩만 전진하는 선형 수렴(O(N)) 특성 때문에 수렴 속도가 매우 느리다.
        # 매 반복마다 자릿수가 2배씩 늘어나는(2차 수렴) 뉴턴법에 밀려 현대 수치 라이브러리에서 도태된 이유이다.
        # 각 자리는 산대를 두는 산판이나 주판의 한 줄이기 때문에
        # 수를 정밀하게 보장할지언정 속도가 매우 느리다.


        digit_count += 1
        decimal_digits.append(str(d_next))

        ## d 값은 다음 자리로 정밀하게 구하기 위해서 현재의 d_next를 커서로 두어
        ## 파 내려갈 준비를 해야 한다.

        ## d = d_next라고 가정하고
        ## 아까와 같이 평행이동한다.

        c = a * d_next**2 + b * d_next + c
        b = 2 * a * d_next + b
        b *= 10
        c *= 100

    return float(f"{i_part}.{''.join(decimal_digits)}")

def main():
    # 사전 검증: sqrt(2) 혹은 (루트 2나 개평방 2)의 경우 소수점 10의 자리까지 1.4142135623이다.
    # 이를 assert문을 통해 검증한다.
    # 만약 assert문의 메시지가 나오면 오류이므로 재작성한다.

    assert easy_sqrt(2, 10) == 1.4142135623, "산술이 정확하지 않아 sqrt(2)의 값이 표준적인 뉴턴법으로 구한 것과 맞지 않습니다."
    # 간단한 예제이므로 항상 float를 받는다고 가정하자.
    N = float(input())

    print(easy_sqrt(N, 10))

if __name__ == '__main__':
    main()

네 가지 특징을 갖는다.

대수학적 직관성
반올림의 정확성
느린 수렴 속도
기초적인 알고리즘

이는 고등학교 미적분까지의 교육과정을 들어야 이해 가능한 뉴턴법보다 직관적이지만, 수렴 속도가 매우 느리다. 오히려, 이는 문학적인 교훈이나 예술적인 표현에 가깝다고 생각한다.

각 자리가 직관적으로 떨어진다
단계에 맞게 스케일링이 정밀하게 떨어진다
각 단계별로 떼어 가르치면 어린아이도 이해한다

인류 역사의 오랜 시간 동안 철학과 수학은 분리되지 않았다. 구장산술에서 처음 나오는 이 알고리즘 역시 정밀한 이치와 수의 세계에 대한 통찰을 주지만 기술적으로 해석해 보면 매우 비효율적이다.

뉴턴법의 설명을 듣고 나서 직관적으로 떠오르는 생각은 '이게 정말 정확할까?'라는 본능적인 거부감이다. 그러나 놀랍게도 산술은 직관을 넘어서 몇 번만의 반복만으로 놀라운 정밀도를 가져다 준다.

읽고 나서 개운한 것은 이분법도 뉴턴법도 아닌 고전적인 개방술이다. 각 자릿수가 명확하게 법칙을 따르고, 이해하기도 쉽다.

이분법은 이해가 될 듯하나 엄밀하게 따지면 알기 쉽지는 않고, 뉴턴법은 그 방법이 심오하여 인간의 직관과 감성으로 단번에 알기 어렵다.

가장 오묘한 것은, 수의 세계에서 더욱 선진적인 것은 뉴턴법이라는 점이다.

인간의 손가락은 10개고, 사람 마음은 한 번에 여럿을 알아차릴 수 없다.

그러나 수의 세계는 인간의 이해를 넘어선 광활한 대지이며, 그 뜻을 가슴만으로 헤아리는 것은 요임금부터 파인만까지 누구도 해내지 못했다.

물론 엄격한 받아올림 규격이 요구되는 하드웨어에서 개방술 기반의 파생 알고리즘은 여전히 유효하다.

그러나 당신이 위대한 저수준 프로그래머가 아니라면 접할 일은 드문 특수 하드웨어들의 이야기이다.

이것으로 내가 하고 싶은 말은 아래와 같다.

산술의 법은 인간의 법을 뛰어넘어, 때때로 감정과 직관으로는 헤아릴 수 없다.

뉴턴법 이전의 제곱근 구하기 알고리즘

근대까지도 널리 쓰이던 '개방술'

Comments