계산기코어 2.1 뜯어보기 4강. 나눗셈
안녕하세요? noname01입니다.
이번에는 나눗셈 알고리즘을 한번 살펴보도록 합시다. 사실 나눗셈 알고리즘은 앞에서도
언급된 적이 있듯이 2.0버전에서 2.1버전으로 업데이트 되면서 수정되었습니다. 하지만
2.0 버전의 나눗셈 알고리즘은 제곱근을 구하는 알고리즘과 동일하므로 제곱근의 알고리즘을
소개할때 설명하도록 하겠습니다.
먼저 '계산기코어 2.1' 의 나눗셈 알고리즘은 구글링을 통해 열어본 어느 게시글에서
가져왔습니다. 아래 링크는 그 게시글과 연결됩니다.
Blastic :: Binary Division (이진 나눗셈)
제가 설명하면 더 어려워질지도 모르지만(?) 여기서 다시한번 예를 들어 설명해 보겠습니다.
사실은 저 링크로 때우려 했다는건 비밀
여기서는 예제로 "1011101(2) / 101(2)" 를 저 방식대로 계산해 봅시다. 32비트 크기의
수 끼리 나눗셈을 하려면 32번의 과정을 거쳐야 하지만 나누어지는 수의 유효한 자릿수만큼만
반복해도 나눗셈을 할 수 있기 때문에 먼저 나누어지는 수의 유효 자릿수를 알아야 합니다.
지금 우리가 나누려는 수는 1011101(2) 입니다. 이 수의 유효 자릿수 는 7자리입니다. 즉 7번
반복으로 나눗셈을 할 수 있습니다.
(실제 트리거로 구현하면 자잘한 다른 작업 때문에 트리거 주기가 4번 더 필요합니다.)
먼저 나누어질 수의 가장 큰 자릿수를 나누는 수와 비교합니다.
①
빨간색으로 표시된 수와 파란색으로 표시된 수를 비교해보니 파란색으로 표시된 수가 더
작습니다. 그러므로 몫과 나누어지는 수(파란색 + 검은색)의 비트를 왼쪽으로 한칸씩 이동
합니다.(2진수에서 왼쪽으로 한칸 비트이동은 ×2)
※파란색 수 오른쪽의 검은색 수의 최상위비트는 파란색 수의 최하위 비트로 이동합니다.
②
역시 빨간색으로 표시된 수와 파란색으로 표시된 수를 비교해보니 파란색으로 표시된 수가 더
작습니다. 위와 마찬가지의 과정을 반복합니다.
③
이번에는 파란색으로 표시된 수가 빨간색으로 표시된 수보다 같거나 커졌습니다. 그러므로
몫에다 1을 더해주고 파란색 수에서 빨간색 수를 빼버립니다. 뺀 뒤 다시 빨간색 수와 파란색
수를 비교해보니 파란색 수가 작으므로 ①에서 수행한 과정을 수행합니다.
④
다시 빨간색 수와 파란색 수를 비교해보니 파란색 수가 작습니다. 그러므로 ①에서 수행한
과정을 반복합니다.
⑤
역시 빨간색 수와 파란색 수를 비교해보니 파란색 수가 작습니다. 그러므로 ①에서 수행한
과정을 반복합니다.
⑥
또 파란색 수가 빨간색 수보다 같거나 커졌습니다. 역시 몫에다 1을 더해주고 파란색 수에서
빨간색 수를 빼버립니다. 다시 파란색 수와 빨간색 수를 비교해보니 파란색 수가 작습니다.
그러므로 다시 ①에서 수행한 과정을 반복합니다.
⑦
이제 계산이 끝났습니다. 남은 파란색 수[11(2) = 3]가 나머지가 되고 위에 적힌 검은색 수
[10010(2) = 18]가 몫이 됩니다.
이것은 직접 연필(혹은 볼펜)으로 연습장에 나눗셈을 할 때와 유사하게 표현한것인데, 잘
보시면 비트를 왼쪽으로 이동시키는 수는 파란색 수, 파란색 수의 오른쪽에 있는 검은색 수,
몫, 이렇게 3개가 있습니다. 여기서 파란색 수의 오른쪽에 있는 검은색 수와 몫을 하나로
묶어버립시다.(왼쪽으로 1칸 이동하는 비트연산을 줄이기 위해) 이렇게 묶어서 다시 위
과정을 한번 더 살펴봅시다.(거의 비슷한데 연습이라 생각하고 한번더 봐주세요.)
①
※검은색 수의 최상위비트는 파란색 수의 최하위비트로 이동합니다.
②
③
④
⑤
⑥
⑦
자 이제 이걸 트리거로 구현해 보아야겠죠?? 자 먼저 0으로 나누었을때의 오류 처리와 초기화
부분을 먼저 살펴봅시다.
이번에는 나누어지는 수의 자릿수(2진수)를 구하는 트리거를 살펴봅시다.
이때 t값과 C값 두개의 값에 대입한 것을 볼 수 있는데 이렇게 한 이유는 나누어지는 수의
자릿수가 두가지 용도를 갖기 때문입니다. 한가지 용도는 자릿수 만큼 비트이동을 해야
하므로 반복횟수를 정하는데 사용되고 나머지 하나는 위의 설명에서 검은색 수의 최상위
비트를 구하는데 사용됩니다. 즉 나누어지는 수가 n자리수(2진수)라면 검은색 수의 최상위
비트는 왼쪽에서 n번째 비트가 될 것입니다.
또한 둘중 하나는 C값에다가 저장했는데 이것은 C값의 나눗셈 제어변수 구간에서 또 자릿수
를 저장하기 위한 구간으로 세분화 시킨 것입니다.
이제 이 나눗셈 알고리즘을 위해 필요한 트리거들을 호출해 봅시다. 먼저 위의 알고리즘은
미리 만들어둔 트리거로 표현다면 다음과 같이 됩니다.
참고로 여기서 검은색 수의 역할은 A가, 파란색 수의 역할은 R이, 빨간색 수의 역할은 B가
하게 됩니다. 그리고 t가 루프의 반복횟수를 제어합니다.
※주소가 올 자리에 " X "라고 표시된 부분은 호출식이 아니라 제어변수가 동작을 제어
할때 직접 수행
◎시작
X : t와 C에 나누는 수 A의 자릿수를 대입;
※물론 C의 기존에 있던 데이터가 손상되지 않는 형식으로 대입하며
t에는 자릿수보다 1이 더 큰 수를 대입(제어역할때문)
①
X : t값을 비교한다.
t의 값이 1 이하일 경우 ②동작
t의 값이 2 이상일 경우 ③동작
------------------------------------------------
② //비트 이동을 끝낸 뒤에 B값과 R값을 비교하교 연산하기 위한 과정
X : --t;
8^10 * 3 : r=R; R*=2; //여기서 비트이동된 R값은 버리고 r값만 취급
8^9 * 4 : a=b=r; r=0;
8^8 * 1 : b=B;
8^7 * 3 : x=compare(&a, &b); //부득이하게 값을 비교하며 차까지 구함 [주3]
8^7 * 1 : X=a+b; a=b=0;
X : 루프탈출후 ④동작
------------------------------------------------
------------------------------------------------
③ //비트 이동과정과 B값과 R값을 비교하고 연산하는 과정
X : --t;
8^10 * 3 : r=R; R*=2; //먼저 R값을 r값에 복사한뒤 R을 왼쪽으로 한칸 비트이동
8^9 * 4 : a=b=r; r=0; //두배가 되기전의 R값인 r을 a에 대입 [주1]
8^8 * 1 : b=B; //B값을 b에 대입
8^7 * 3 : x=compare(&a, &b); //두 값을 비교
8^7 * 1 : X=a+b; a=b=0; //두 값의 차를 X에 대입
8^6 * 7 : if(x<=2) { R=2*X; X=0; ++A; } //[주2]
8^5 * 7 : if(A>=2^n) { ++R; A-=2^n; } //A의 최상위비트를 R의 최하위비트로 옮김
8^4 * 2 : A*=2; //A를 왼쪽으로 한칸 비트이동
X : ①동작
------------------------------------------------
④
X : x값을 비교한다.
x의 값이 2 이하일 경우 ⑤동작 //r값이 B값보다 크거나 같은 경우
x의 값이 3 이상일 경우 ⑥동작 //r값이 B값보다 작은 경우
------------------------------------------------
⑤
X : ++A; //r이 B보다 크거나 같은 경우 이므로 몫에다 1을 가산
8^5 * 2 : x=X; X=0; //②과정에서 구한 차(나머지)를 x에 대입
X : ⑦동작
------------------------------------------------
------------------------------------------------
⑥
8^9 * 5 : a=X;
8^8 * 1 : b=B;
8^7 * 3 : x=compare(&a, &b); //파괴된 r값을 복구하기위해 다시 B와의 차를 구함 [주3]
8^7 * 2 : x=a+b; a=b=0; //복구한 r값(나머지)를 x에 대입
X : ⑦동작
------------------------------------------------
------------------------------------------------
⑦
X : b=0;
8^9 * 1 : a=A;
8^7 * 1 : X=a+b; a=b=0; //A에 대입된 몫을 X로 옮기기 위한 작업 [주4]
X : 계산완료
------------------------------------------------
※[주1] 비트이동을 하기전의 값이 B보다 클 수 있기 때문에 r에 값을 복사해두고 비트이동을
합니다.
※[주2] 비트이동을 하기전의 값인 r값보다 B값이 더 클 경우 r값과 B값의 차를 구해 그 차를
비트이동합니다. B값보다 r값이 같거나 클 경우 이미 비트이동된 R값을 그대로 사용
하면 되구요.
※[주3] 비교연산(compare함수)을 수행하면 항상 a값과 b값이 보존되지 않는데, 마지막
비트이동을 한 이후 r값(초과 비트이동이 일어나기전의 R값)과 B값을 비교하게 되면
부득이하게 r값과 B값의 차가 구해져 버립니다. 이때 다행이 r값이 더 크거나 같은
경우였다면 해야할 연산을 수행한것이지만 r값이 더 작은 경우였다면 r은 이미
그 자체로 나머지값인데 이 값과 B값의 차를 구한게 됩니다. 이때 r이 작은 경우
이므로 다음 식이 성립됩니다.
|B - |B - r|| = |B - B + r| = r
그렇기 때문에 ⑥에서 다시한번 B와의 차를 계산해 주어 r값을 복구해 냅니다.
※[주4] 원래는 X=A; 라는 트리거를 만들면 되겠지만 최대한 트리거를 줄이기 위해 기존에
있는 트리거들을 활용했습니다.
이렇게 복잡한 과정을 거치는데 왜 이렇게 복잡해졌냐하면 최대의 계산속도를 위해서는
③번 과정을 트리거 한주기만해 해치우는 것이 관건인데다가 기존에 존재하는 트리거들을
최대한 활용하려 하다보니 이렇게 복잡하게 되었습니다.
혹시나 더 좋은 방법 떠오르시는 분은 저에게 살짝...
사실 트리거 갯수 따위 생각하지 않고 루퍼로 막 찍어내면 더 편하고 빠르게 만들수 있는데
트리거 갯수 최소화까지 고려해서 만들다 보니 이렇게 되었네요.
근데 왜 내가 트리거 갯수까지 고려했지??
여튼 트리거로 살펴봅시다. 점프하는 부분은 생략하고 나누어지는 수의 자릿수(2진수)를
구하는 트리거와 오류 처리 트리거, 그리고 초기화 트리거는 위에서 살펴봤으니 호출 부분만
보면 되겠네요.
이렇게 나눗셈 알고리즘을 살펴보았습니다. 다음 강에선 제곱근을 구하는 알고리즘을
살펴 보도록 합시다.
[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강. 난수 생성
