계산기코어 2.1 뜯어보기 5강. 제곱근
안녕하세요? noname01입니다.
지난강에선 '계산기코어 2.1' 의 나눗셈 알고리즘에 대해 살펴보았는데요, 이번강에서는
'계산기코어 2.0'의 나눗셈 알고리즘, 즉 제곱근을 구하는 알고리즘을 살펴봅시다. 나눗셈을
계산하거나 제곱근을 구하는것 외에도 다른 용도로 사용할 수도 있지만 일단 여기서는
'계산기코어 2.1'의 주 용도인 제곱근을 구하는데 초첨을 맞춰서 설명하도록 하겠습니다.
이 알고리즘의 근본은 '이진 검색 알고리즘' 에서 시작됩니다. '이진 검색 알고리즘'이
뭐냐구요?
------------------------------------------------------------------------------------
이진 검색 알고리즘
위키백과, 우리 모두의 백과사전.
이진 검색 알고리즘(binary search algorithm)은 정렬된 리스트에서 특정한 값을 찾는
알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고
작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그
값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색이 반복될 때마다
목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다.
------------------------------------------------------------------------------------
에.. 무슨말인지 잘 모르겠다구요?? 쉽게 말하면 우리가 사전을 찾을때를 생각해
보면 됩니다. 사전은 가나다순으로 정렬이 되어있죠. 이때 우리는 사전 중간 아무곳이나
펼칩니다. 그런뒤 펼쳐진 페이지가 어떤 문자로 사작하는지를 살펴보고 찾고자 하는 단어가
더 뒤쪽에 있는 단어인지 더 앞쪽에 단어인지 봅니다.
그리고 나서 앞쪽에 있는 단어라면 펼친 페이지부터 맨 첫 페이지 사이중 임의의 페이지를
다시 펼쳐봅니다. 이러한 과정을 반복하여 우리가 찾고자 하는 단어를 찾게 되는 것이죠.
자 이제 이걸 제곱근을 구하기 위해 응용을 해봅시다. 여기서는 25의 제곱근을 계산해
보면서 이 알고리즘이 어떻게 작동하는지 살펴봅시다. 먼저 초기 구간을 정합니다.
'계산기코어 2.1'에서는 초기 구간은 [0, 1] 로 지정되어 있습니다.
이 구간의 최댓값인 1을 제곱합니다. 그리고 그 값을 25과 비교합니다. 25이 커도 한참
크네요 한참 멀었습니다. 구간을 변경해 줍니다. 새 구간을 구하는 기준은 다음과 같습니다.
※현재 구간
[a, b]
※다음 구간
[b, 2*b]
이 기준대로라면 두번째 구간은 [1, 1*2] 즉 [1, 2]가 됩니다. 이렇게 구간의 길이를 2배로
늘이면서 구하고자 하는 제곱근이 포함된 구간을 최대한 빠르게 검색합니다.(배수가 크면
더 빠르게 검색되어 더 큰 수의 제곱근을 구하는데 유리해 집니다.)
역시 아까와 마찬가지로 이 구간의 최댓값을 제곱하여 25과 비교합니다. 최댓값이 2이니
제곱한 값은 4로 역시 아직 멀었군요. 이 과정을 구간 최댓값의 제곱이 25보다 커질때까지
반복 합니다.
만약 이 과정을 수행하는 도중 구간 최댓값의 제곱이 25와 같아지면 그 값이 25의 제곱근이니
바로 계산을 중단하고 그 값을 X에 대입후 계산을 마칩니다.
자 이렇게 25의 제곱근이 존재하는 구간이 [4, 8]이라는 것을 알았습니다. 지금부터는 원래
이진 검색 알고리즘을 그대로 사용할겁니다. 그러므로 이번에는 구간의 최댓값이 아니라
구간의 가운데에 있는 값의 제곱과 25를 비교합니다. 즉 [a, b]구간이라면 ((a + b) / 2)^2
와 25를 비교합니다. 계산해보면 36과 25를 비교하게 되는데 36이 더 큽니다. 그러면 25의
제곱근은 [4, 6]이라는 구간내에 존재한다는 것을 알 수 있습니다.따라서 다음 구간은
[4, 6]이 됩니다.
이 과정에서도 마찬가지로 구간 가운데에 있는 값의 제곱이 25와 같다면 그 값이 25의
제곱근이니 바로 계산을 중단하고 그 값을 X에 대입후 계산을 마칩니다.
이 과정을 구간의 최댓값과 구간의 최솟값의 차이가 1이 될때까지 반복합니다.
구간의 최솟값과 최댓값의 차가 1이 될때까지 구간을 좁혀 나가 25의 제곱근은 구간 [4, 5]
에 있는것을 알았습니다. 이때 구간 최댓값의 제곱과 25를 비교해보니 일치하므로 5가
25의 제곱근이 된 것을 알 수 있습니다.
사실 이 경우에는 구간의 최댓값과 최솟값의 차이가 1인것을 인식하기 이전에 이미 구간
[4, 6]에서 가운데값인 5를 비교할때 이미 원하는 값이 구해져 계산이 끝나게 되는데 만일
그렇지 않으면서 구간의 최솟값과 최댓값의 차이가 1이 된 경우 구간의 최솟값이 우리가
구하고자 하는 제곱근이 됩니다.
이 알고리즘을 나눗셈에 이용하려면 단순히 제곱을 하는 대신 나누는 수와의 곱을 하여 그
결과를 나누어지는 수와 비교하는 작업을 반복하면 된답니다. 물론 비슷한 방식으로
n제곱근도 구할수 있죠(계산은 n이 커진만큼 느리겠지만...)
어쨌든 알고리즘을 알아봤으니 이 알고리즘을 구현하기 위해 호출해야 하는 트리거들을
살펴봅시다.
참고로 여기서 제곱근을 구하고자 하는 수는 A에 대입되며, B에는 쓰레기값이 대입됩니다.
(변수 B는 사용안함) 또한 구간의 최솟값은 r에 대입되고 구간의 최댓값은 R에 대입됩니다.
※주소가 올 자리에 " X "라고 표시된 부분은 호출식이 아니라 제어변수가 동작을 제어
할때 직접 수행
◎시작
X : R=1; //초기 구간을 [0, 1]으로 지정
X : ①동작
------------------------------------------------
① //구간 최댓값 R의 제곱 계산
8^9 * 2 : a=b=R;
8^6 * 1 : X=a*b; t=a; a=b=0;
X : ②동작
------------------------------------------------
------------------------------------------------
②
X : t=0;
8^9 * 1 : a=A; //제곱근을 구하고자 하는 값
8^8 * 2 : b=X; //계산한 구간 최댓값 R의 제곱
8^7 * 3 : x=compare(&a, &b); //위의 두 수 a와 b를 비교
X : ③동작
------------------------------------------------
③
X : x값을 비교한다.
x의 값이 1일 경우 ④동작 //a > b 인 경우로 아직 제곱근이 포함된 구간이 아님
x의 값이 2일 경우 ⑤동작 //a = b 인 경우로 R이 제곱근이 됨
x의 값이 3일 경우 ⑥동작 //a < b 인 경우로 제곱근이 포함된 구간임
------------------------------------------------
④ //제곱근이 포함된 구간을 구하기 위해 길이가 2배인 다음 구간을 구함
X : X=0;
8^10 * 3 : r=R; R*=2; //[주1]
8^9 * 2 : a=b=R;
8^6 * 1 : X=a*b; t=a; a=b=0; //새 구간 최댓값의 제곱을 계산
X : ②동작 //계산한 구간 최댓값의 제곱과 제곱근을 구하고자 하는 값을 다시 비교
------------------------------------------------
------------------------------------------------
⑤ //구해낸 제곱근 R을 X에 대입시키기 위한 과정
8^10 * 3 : r=R; R*=2; //R을 두배로 만드는건 R을 r에 대입하는것과 묶여있어서...
8^5 * 1 : X=r; r=0;
X : 계산완료
------------------------------------------------
------------------------------------------------
⑥ //제곱근이 포함된 구간을 찾았으므로 이제 이진검색 알고리즘으로 제곱근을 구함
X : ⑦동작
------------------------------------------------
------------------------------------------------
⑦ //구간의 최댓값과 구간의 최솟값의 차이를 비교
8^9 * 2 : a=b=R;
8^8 * 3 : b=r;
8^7 * 3 : x=compare(&a, &b);
8^7 * 2 : x=a+b; a=b=0;
X : ⑧동작
------------------------------------------------
⑧
X : x값을 비교한다.
x의 값이 1 이하일 경우 ⑨동작 //구간 최댓값과 최솟값의 차이가 1로 계산완료
x의 값이 2 이상일 경우 ⑩동작 //이분검색 시작
------------------------------------------------
⑨ //[주2]
8^5 * 1 : X=r; r=0; //구한 제곱근을 X에 대입
X : 계산완료
------------------------------------------------
------------------------------------------------
⑩ //구간 최댓값과 최솟값을 합산
8^9 * 2 : a=b=R;
8^8 * 3 : b=r;
8^7 * 1 : X=a+b; a=b=0;
X : ⑪동작
------------------------------------------------
------------------------------------------------
⑪
8^9 * 3 : a=b=X/2; X=0; //⑩과정에서 합산한 값을 2로 나누어 구간 가운데 값을 구함
8^6 * 1 : X=a*b; t=a; a=b=0; //구간 가운데 값을 제곱, 구간 가운데 값을 t에 대입
X : ⑫동작
------------------------------------------------
------------------------------------------------
⑫
8^9 * 1 : a=A; //제곱근을 구하고자 하는 값
8^8 * 2 : b=X; //계산한 구간 가운데값
8^7 * 3 : x=compare(&a, &b); //위의 두 수 a와 b를 비교
X : ⑬동작
------------------------------------------------
⑬
X : x값을 비교한다.
x의 값이 1일 경우 ⑭동작 //a > b 인 경우 [주3]
x의 값이 2일 경우 ⑮동작 //a = b 인 경우로 구간 가운데 값인 t가 A의 제곱근
x의 값이 3일 경우 ⓐ동작 //a < b 인 경우 [주3]
------------------------------------------------
⑭ //이분 검색 알고리즘에 의해 다음 구간의 최솟값은 현재 구간의 가운데 값이 됨
8^10 * 2 : r=t; t=0; //현재 구간의 가운데 값이 대입된 t를 구간 최솟값 r에 대입
8^9 * 2 : a=b=R;
8^8 * 3 : b=r;
8^7 * 3 : x=compare(&a, &b); //구간의 최댓값과 구간의 최솟값의 차이를 비교
8^7 * 2 : x=a+b; a=b=0;
X : ⑧동작
------------------------------------------------
------------------------------------------------
⑮ //구해낸 제곱근 t을 X에 대입시키기 위한 과정
8^10 * 2 : r=t; t=0;
8^5 * 1 : X=r; r=0;
X : 계산완료
------------------------------------------------
------------------------------------------------
ⓐ //이분 검색 알고리즘에 의해 다음 구간의 최댓값은 현재 구간의 가운데 값이 됨
8^10 * 1 : R=t; t=0; //현재 구간의 가운데 값이 대입된 t를 구간 최댓값 r에 대입
8^9 * 2 : a=b=R;
8^8 * 3 : b=r;
8^7 * 3 : x=compare(&a, &b); //구간의 최댓값과 구간의 최솟값의 차이를 비교
8^7 * 2 : x=a+b; a=b=0;
X : ⑧동작
------------------------------------------------
※[주1] 이 과정을 통해 현재 구간의 최댓값이 다음 구간의 최솟값
이 되고 현재 구간의 최댓값을 2배한 값이 다음 구간의 최댓값이 됩니다.
이를 통해 단계가 넘어갈 수록 구간의 길이가 2배로 늘어나서 빠르게 제곱근이
포함된 구간을 찾아낼 수 있습니다.
※[주2] 구간의 최솟값과 최댓값의 차가 1이 될 경우 구하고자 하는
제곱근을 구했으며 이때 구간의 최솟값인 r이 구하고자 하는 제곱근이 됩니다.
R이 제곱근이 될 수도 있지만 이보다 앞선 과정인 구간 최댓값의 제곱과 제곱근
을 구하고자 하는 수를 비교할때나 구간의 가운데값의 제곱과 제곱근을 구하고자
하는 수를 비교할때 R이 제곱근이 되는 경우는 모두 걸러집니다.
※[주3] a > b 일 경우 구하고자 하는 제곱근은 구간의 가운데 값
보다 크므로 다음 구간의 최댓값은 그대로 두고 다음 구간의 최솟값을 현재 구간의
가운데 값으로 정합니다.
반대로 a < b 일 경우 구하고자 하는 제곱근은 구간의 가운데 값보다 작으므로 다음
구간의 최솟값은 그대로 두고 다음 구간의 최댓값을 현재 구간의 가운데 값으로
정합니다.
이런 식으로 구간의 길이가 1이 될때까지 구간의 길이를 반씩 줄여 나갑니다.
이제 트리거를 직접 살펴봅시다. 여기서도 점프 부분은 생략하고 초기화 부분부터 살펴
봅시다.
이렇게 이진 검색 알고리즘을 응용한 제곱근을 구하는 알고리즘을 살펴보았습니다.
다음 강에선 정수끼리의 지수연산과 팩토리얼, 그리고 순열을 구하는 트리거를 살펴보도록 합시다.
[50]계산기코어 2.1 뜯어보기 1강. 전체구조와 호출방식
[50]계산기코어 2.1 뜯어보기 2강. 오류와 입력처리
[50]계산기코어 2.1 뜯어보기 3강. 덧셈, 뺄셈, 곱셈
[50]계산기코어 2.1 뜯어보기 4강. 나눗셈
[50]계산기코어 2.1 뜯어보기 5강. 제곱근
[50]계산기코어 2.1 뜯어보기 6강. 거듭제곱, 팩토리얼, 순열
[50]계산기코어 2.1 뜯어보기 7강. 조합
[50]계산기코어 2.1 뜯어보기 8강. 난수 생성
