자료구조 & 알고리즘

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

2023. 6. 2. 14:51
목차
  1. 제곱근
  2. 바빌로니아 법(The Babylonian Method)
  3. 유도 과정
  4. 알고리즘으로 구현
  5. N = 7
  6. N = 4375

제곱근

제곱근을 구하려면 자바에서 손쉽게 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번째에는 소수점 아래 여섯째 자리까지 같아진 것을 볼 수 있다.

반응형
저작자표시

'자료구조 & 알고리즘' 카테고리의 다른 글

[JAVA/자료구조] Stack 스택  (0) 2023.06.04
[Algorithm/Java] 이진탐색 Binary Search / UpperBound / LowerBound  (0) 2023.06.04
[기초수학/JAVA] 약수, 최대공약수, 최소공배수 알고리즘  (0) 2023.05.18
[Algorithm/Java] 삽입 정렬 (insertion sort)  (0) 2023.05.13
[Algorithm/Java] 선택 정렬 (selection sort)  (0) 2023.05.08
  1. 제곱근
  2. 바빌로니아 법(The Babylonian Method)
  3. 유도 과정
  4. 알고리즘으로 구현
  5. N = 7
  6. N = 4375
'자료구조 & 알고리즘' 카테고리의 다른 글
  • [JAVA/자료구조] Stack 스택
  • [Algorithm/Java] 이진탐색 Binary Search / UpperBound / LowerBound
  • [기초수학/JAVA] 약수, 최대공약수, 최소공배수 알고리즘
  • [Algorithm/Java] 삽입 정렬 (insertion sort)
HSRyuuu
HSRyuuu
Web Backend Developer happyhsryu
HSRyuuu
HS_dev_log
HSRyuuu
전체
오늘
어제
  • 전체 글 보기 (230)
    • Java (24)
    • Spring (25)
    • JPA & QueryDSL (13)
    • Database (17)
    • 자료구조 & 알고리즘 (30)
    • DevOps (10)
    • [ Computer Science ] (47)
      • Web & Network (14)
      • 프로그래밍 이론 (11)
      • 운영체제 (3)
      • 데이터베이스 이론 (5)
      • Linux 리눅스 (7)
    • [ Frontend ] (16)
      • Vue.js & Nuxt.js (8)
      • JSP_Thymeleaf (7)
    • [ 기타 ] (48)
      • 오픈소스 라이브러리 (5)
      • 코딩테스트 (13)
      • Trouble Shooting (7)
      • Tech Interview (6)
      • Book Review (9)
      • 끄적끄적... (6)
      • 개인 프로젝트 (2)

블로그 메뉴

  • 홈
  • 태그
  • github

공지사항

  • GitHub
  • 공부한 내용을 정리하고 기록하는 블로그 입니다.

인기 글

태그

  • MySQL
  • 제로베이스
  • cleancode
  • Java
  • 기술면접
  • 자료구조
  • 백엔드기술면접
  • 트랜잭션
  • 개발자
  • Redis
  • Nuxt3
  • 백엔드공부
  • 클린코드
  • 백준
  • Database
  • mybatis
  • SQL
  • HTTP
  • 백엔드
  • JPA
  • Linux
  • vue3
  • springsecurity
  • TechInterview
  • web
  • SpringBoot
  • Spring
  • 리눅스
  • Redisson
  • 백엔드스쿨

최근 댓글

최근 글

hELLO · Designed By 정상우.
HSRyuuu
[JAVA / 수학 / 점화식] sqrt 제곱근 직접 구하는 알고리즘 (바빌로니아 법)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.