바빌로니아법으로 제곱근 값 구하기

문제 : Math.sqrt 없이 제곱근 구하기

루트4 = 2 처럼 한번에 구할 수 있는 수도 있지만

루트2 = 1.414213... 이 무리수인 것 처럼 근사값을 구하는 방식도 존재합니다.

그래서 이러한 경우를 위해 바빌로니아 법을 사용합니다.

 

우선 바빌로니아 법이 뭔지를 알아봅시다.

 

* 바빌로니아 법

임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근삿값을 구하는 방법입니다.
아래의 과정에 따라 양의 실수 a에 대하여 다음 과정을 따라 제곱근a의 근삿값을 구할 수 있습니다.



- 포인트는 다음과 같습니다.

 

1) x는 임의의 양의 실수

2) x는 항상 루트a보다 크므로 하한이 있는데 계속 감소하여 수렴

3) n이 높아질수록 정밀도가 올라감

 

위의 수식을 코드로 작성하기전에 적어보면 

X2 = Xn+1 , X1 = Xn 으로 가정하고,
X2 = 1/2 * (X1 + a/X1) = X1 * X1 + a / 2 * X1

그러면 위의 수식을 이용해 자바코드로 알고리즘을 풀어보도록 하겠습니다.

 

public class Babylonian {
    private double x,m;
    private double result;
    private int count;
    private double guess;

    // 근사값 구하기
    public double computeRoot(double a) {
        x = a;
        m = 0;
        while (m <= x) {
            // 제곱했을 때 딱 떨어진다면 바로 리턴
            // 제곱했을 때 수가 더 커진다면 제곱한 수의 -1을 리턴
            result = Math.floor((m+x) / 2);
            if (result * result > x) {
                x = result - 1;
            }
            else {
                m = x + 1;
            }
        }
        return x;
    }

    // 바빌로니아 공식
    public double BL(double num) {
        guess = computeRoot(num);
        if((num * num) == x) return num;
        while (guess * guess < num ) {
            guess += 0.01;
        }
        return guess;
    }
    
    public static void main(String[] args) {
        int num = 6;
        double b = BL(num);
        String res = String.format("%.2f",b);
        System.out.println(res);
    }
}