[JAVA / 수학 / 점화식] sqrt 제곱근 직접 구하는 알고리즘 (바빌로니아 법)

제곱근

제곱근을 구하려면 자바에서 손쉽게 Math.sqrt() 메서드를 이용해서 구할 수 있다.

이 메서드를 이용하지 않고 제곱근을 구하는 방법을 알아보자.

---

바빌로니아 법(The Babylonian Method)

출처 : 위키백과

---

유도 과정

쓸땐 몰랐는데 사진을 업로드하고 보니 글씨가 개판이다...

1. N은 7일때, N의 제곱근을 구해보자.
2. N의 제곱근은 아마 2와 3 사이에 있을 것이다. (3에 가까울 것 같다.)
3. 따라서 N의 제곱근을 임의의 수 Xn과 아주 작은 수 ε 의 합으로 나타낸다.
4. 위의 식을 ε에 대해 정리 한 뒤, 다시 3번의 식에 대입한다.
5. 4번의 식을 정리하면 위의 위키백과 캡쳐본의 공식이 나온다.

맨 처음에 Xn=2라고 놓고 시작해서 3번만 반복했는데도 실제 값과 매우 유사하게 나왔다.

임의의 값 Xn이 점점 구하고자 하는 제곱근 값에 점점 근사해진다.

---

알고리즘으로 구현

N = 7

위에서 손으로 풀었을 때의 조건과 같이 N = 7, Xn = 2로 시작해 보자.

int N = 7;
double answer = 2;
System.out.println("=== (N = 7) ===");
for (int i=1;i<=10;i++) {
    answer = (answer+(N/answer))/2;
    System.out.printf("반복 %d번째 : %.6f | 실제 값 : %.6f\n",i,answer,Math.sqrt(N));
}

(출력)

=== (N = 7) ===
반복 1번째 : 2.750000 | 실제 값 : 2.645751
반복 2번째 : 2.647727 | 실제 값 : 2.645751
반복 3번째 : 2.645752 | 실제 값 : 2.645751
반복 4번째 : 2.645751 | 실제 값 : 2.645751
반복 5번째 : 2.645751 | 실제 값 : 2.645751
반복 6번째 : 2.645751 | 실제 값 : 2.645751
반복 7번째 : 2.645751 | 실제 값 : 2.645751
반복 8번째 : 2.645751 | 실제 값 : 2.645751
반복 9번째 : 2.645751 | 실제 값 : 2.645751

3번째부터 이미 매우 가까워진 것을 볼 수 있다.

---

N = 4375

이번엔 훨씬 큰 수로 해보자.

System.out.println("=== (N = 4375) ===");
N = 4375;
answer = 1;
for (int i=1;i<=10;i++) {
    answer = (answer+(N/answer))/2;
    System.out.printf("반복 %d번째 : %.6f | 실제 값 : %.6f\n",i,answer,Math.sqrt(N));
}

(출력)

=== (N = 4375) ===
반복 1번째 : 2188.000000 | 실제 값 : 66.143783
반복 2번째 : 1094.999771 | 실제 값 : 66.143783
반복 3번째 : 549.497603 | 실제 값 : 66.143783
반복 4번째 : 278.729711 | 실제 값 : 66.143783
반복 5번째 : 147.212960 | 실제 값 : 66.143783
반복 6번째 : 88.465905 | 실제 값 : 66.143783
반복 7번째 : 68.959993 | 실제 값 : 66.143783
반복 8번째 : 66.201287 | 실제 값 : 66.143783
반복 9번째 : 66.143808 | 실제 값 : 66.143783
반복 10번째 : 66.143783 | 실제 값 : 66.143783

이번엔 7번째 반복부터 거의 가까워 지다가 10번째에는 소수점 아래 여섯째 자리까지 같아진 것을 볼 수 있다.