계산기코어 2.1 뜯어보기 3강. 덧셈, 뺄셈, 곱셈
안녕하세요? noname01입니다.
지난강까지 '계산기코어 2.1'의 구조와 작동방식에 대해 살펴보았는데요, 이번에는 좀더
세부적으로 들어가서 각 연산이 어떤방식으로 수행되는지 한번 살펴 보도록 합시다.
덧셈과 뺄셈은 간단하므로 곱셈과 한꺼번에 설명하도록 하겠습니다.
리셋에 관한 트리거는 C의 값이 1일경우 12개의 변수(셋데스) 모두를 0으로 만든다 라는
간단한 트리거이므로 설명을 생략합니다.
아니 이미 설명한거나 다름없잖소.
제일 간단한 덧셈부터 살펴봅시다. 우리가 지금부터할 작업은 A의 값과 B의 값을 더해
X에다가 그 결과를 대입하는 작업입니다. A와 B에는 더할 값이 이미 들어있고 C에도 덧셈에
해당하는 코드인 2가 들어있다고 가정합시다. 이 상태에서 가장 먼저 할 작업은 C의 값을
덧셈 제어변수 범위의 시작값인 1000으로 점프시키는 작업입니다. 이때 먼저 c의 값을 초기화
시킨뒤 C의 값을 1000으로 만들어 줍니다.
그리고 C가 1000일 경우 먼저 다른 변수들을 0으로 초기화 합니다. 당연히 이미 유효값이
들어있는 A, B, C, c는 초기화하지 않습니다. 초기화 직후 '함수'의 역할을 하는 트리거들을
호출하여 덧셈을 수행해야 합니다. 덧셈을 수행하기 위해 호출해야 하는 트리거의 순서는
다음과 같습니다.
------------------------------------------------
①
8^9 * 1 : a=A;
8^8 * 1 : b=B;
8^7 * 1 : X=a+b; a=b=0;
------------------------------------------------
식 왼쪽에 있는 값들은 앞서 1강에서 살펴 보았던 표에서 '함수' 역할을 하는 트리거의
작업 단위에 배정된 c값을 나타냅니다. 이것을 편의상 '주소'라고 부르도록 하겠습니다.
그리고 "-------" ←이 경계선을 한 단위로 구분 하는데 이러한 하나의 단위 안에 있는
트리거들은 트리거 동작주기 1주기 만에 동작을 완료할 수 있도록 되어 있습니다.
(1강에서 언급된 "리스트식 디스플레이 텍스트 메시지 트리거" 팁을 참고하세요.)
저 함수들을 호출하기 위해 c값에 주소들을 더해주고 마지막으로 C값을 다음값인 1001로
넘겨줍니다.
호출한 트리거가 모두 동작을 완료하게 되면 c의 값은 0이 됩니다. 그러므로 C값이 1001이고
c값이 0이라면 계산이 완료되었다고 할 수 있겠죠? 따라서 두 조건을 만족할때 계산 결과가
대입되는 X를 제외한 나머지 변수들을 0으로 초기화 시켜 줍니다. 물론 C값도 0으로 초기화
시켜 계산이 완료되었음을 알리고 다음 계산을 대기합니다.
(사실 절대로 0이 아닌 값을 갖지 않는 c와 같은 변수들도 있는데 한꺼번에 만들어 복사해
쓰다보니 그냥 그대로 남아있습니다.)
이러한 과정을 거쳐서 계산을 수행하게 됩니다. 나머지 연산들도 기본 틀은 동일하되,
알고리즘이 다르기 때문에 호출하는 트리거와 조건문 등이 추가되기도 합니다.
이번엔 뺄셈(비교연산)을 살펴볼까요? C값을 점프시키는 과정과 계산완료후 변수들을 초기화
하는 과정은 동일하니 생략하고 트리거도 덧셈과 거의 유사하므로 글로만 설명하도록 하겠
습니다.
(계산완료후 변수들을 초기화 할때에 뺄셈과 나눗셈은 X뿐만 아니라 x도 초기화하지 않고
남겨둡니다. 당연한 것이지만 뺄셈과 나눗셈 계산에서는 x에도 결과값이 대입되기
때문입니다.)
뺄셈을 수행하기 위해 호출해야 하는 트리거의 순서는 다음과 같습니다.
------------------------------------------------
①
8^9 * 1 : a=A;
8^8 * 1 : b=B;
8^7 * 3 : x=compare(&a, &b);
8^7 * 1 : X=a+b; a=b=0;
------------------------------------------------
x=compare(&a, &b); ←이것이 추가된 것만 빼면 덧셈과 동일한 것을 알 수 있습니다.
이 함수는 1강에서 설명한 적이 있는데 한번더 언급해 보겠습니다.
※C언어 주의
포인터의 개념이 사용되어서 포인터를 공부하지 않으신 분은 이해하기 힘들 수 있습니다.
int compare(int* a, int* b)
{
if(*a > *b) {
*a -= *b;
*b = 0;
return 1;
} else if(*a == *b) {
*a = *b = 0;
return 2;
} else {
*b -= *a;
*a = 0;
return 3;
}
}
C언어를 공부해 보신 분들은 이해하시겠지만 C언어를 잘 모르시는 분들을 위하여, 그리고
굳이 왜 C언어로 보기엔 이렇게 복잡해 보이는 과정을 만들었는지를 살펴봅시다.
우선 트리거에 대한 이해가 필요한데, 트리거에는 특정 변수에 상수를 더하고 뺄 수는
있어도 변수와 변수를 더하고 뺄수는 없습니다. 그렇기 때문에 덧셈을 하려면
a의 값이 1 이상 있으면, a의 값에서 1을 빼고 b의 값에 1을 더한다.
이런식으로 만들어야 합니다. 이것을 빠르게 만들기 위해 2진법 등분을 응용해 사용하는데
이것에 관한 자세한 내용은 다음 글을 참고해 주세요.
→(Archonex)3강 -《스타안의 수학 - 2진법 등분》(수정판)←
이것을 응용하여 두 수의 차를 구하는 트리거를 다음과 같이 만들 수 있습니다.
a의 값과 b의 값이 각각 2^31 이상일때, a의 값과 b의 값 각각을 2^31만큼 감소시킨다.
a의 값과 b의 값이 각각 2^30 이상일때, a의 값과 b의 값 각각을 2^30만큼 감소시킨다.
.
.
.
a의 값과 b의 값이 각각 2^0 이상일때, a의 값과 b의 값 각각을 2^0만큼 감소시킨다.
이 계산을 완료하고 나면 a와 b중 큰 값이 대입되어있던 변수에 두 수의 차가 대입되고,
더 작은 값이 대입되어있던 변수는 0이 대입됩니다. 마지막으로 a, b 둘 중에 어느수가 0이고
어느수가 1 이상인지를 인식하여 x값에 비교값을 대입합니다. 즉
a의 값이 1이상이고 b의 값이 0일 경우(a > b), x에 1을 대입한다.
a의 값과 b의 값이 모두 0일 경우(a = b), x에 2를 대입한다.
a의 값이 0이고 b의 값이 1이상일 경우(a < b), x에 3을 대입한다.
이것이 바로 compare함수의 정체입니다. 위에 설명에도 있듯이 a와 b의 크기 차이에 따라
a에 두 수의 차가 대입될 수도 있고, b에 두 수의 차가 대입될 수도 있습니다. 그런데
우리는 두 수의 차를 X에 대입하는것이 목표이므로 덧셈트리거인 'X=a+b; a=b=0;'
를 한번 더 호출해주면 우리가 원하는대로 X에 두 수의 차가 대입되겠죠??
자 그럼 오늘의 핵심인 곱셈을 한번 살펴볼까요?
먼저 곱셈 트리거의 알고리즘은 속도를 위해 용량(트리거갯수 최소화)을 포기한 무식한
방법을 사용합니다. 그렇다고 해서 모든 경우의 수를 다 구해놓는 정도로 무식한 방법은
아닌데, 바로 다음과 같은 방식을 사용합니다.
① 먼저 곱한 결과값이 2^32 미만이 되는 범위 내에서 모든 경우의, 2의 제곱수끼리의 곱셈
결과를 미리 계산하여 트리거로 저장해 둡니다.(여기에만 528개의 트리거 필요.)
당연하지만 이걸 노가다로 만들지는 않았고 루퍼를 이용해서 찍어냈습니다.
(현재의 모방루퍼가 있기 이전에 제가 파이썬으로 만든 구형 모방루퍼와 수열생성기를
사용했었죠. ※현재의 모방루퍼 = 구형 모방루퍼 + 수열생성기)
② 그다음 곱할 두 수를 2의 제곱수의 합으로 나타냅니다. 여기서는 3*5를 예로 들어
보겠습니다.
3 = 2^1 + 2^0
5 = 2^2 + 2^0
∴ 3 * 5 = (2^1 + 2^0) * (2^2 + 2^0)
③ 그리고 위에서 세운 식을 분배법칙으로 전개합니다.
(※대활호는 보기 편하라고 넣은것으로 이외의 다른 의미는 없습니다.)
3 * 5 = [ 2^1 * 2^2 ] + [ 2^0 * 2^2 ] + [ 2^1 * 2^0 ] + [ 2^0 * 2^0 ]
④ 마지막으로 처음에 저장해둔 2의 제곱수끼리의 곱셈 결과를 불러와 합산하여 결과를
구합니다.
3 * 5 = 8 + 4 + 2 + 1
∴ 3 * 5 = 15
이것을 트리거 상으로 구현하려면 다음과 같은 과정을 거치면 됩니다. 먼저 사용할 변수들
입니다.(나머지 변수들은 생략하며 A에서 a로 값을 복사하는 과정과 B에서 b로 값을 복사하는
과정은 이미 이루어져있다고 가정합니다.)
t
↕
a * b = X
a, b에는 곱할값이 들어있고 X는 계산 결과를 대입할 것입니다. 그리고 t는 a의 값을 임시로
저장할 임시 저장 공간 입니다. 먼저 2의 제곱수끼리의 곱을 저장하는 트리거는 다음과 같이
만듦니다.
<<※flag 1>>
이 트리거들을 트리거 한주기만큼 동작시키고 나면 b의 값을 2의 제곱수의 합으로 나타냈을
때의 수들 중에서 제일 큰 숫자와 a의 곱이 X에 가산되며 a값은 0이되고 대신 t가 a의 값을
대입 받게 됩니다.
이제 b값을 2의 제곱수의 합으로 분해했을때의 가장 큰 숫자는 더이상 필요가 없으므로
(이미 a와 곱한 값이 X에 가산됨) b에서 이 수를 빼줍니다. 이 트리거는 어떻게 짜느냐
하면 바로 이진수로 등분해서 빼는 트리거의 순서를 거꾸로 해서 만들어 줍니다. 중요한건
이렇게 거꾸로 트리거를 짤 경우에는 조건부에 최대한도까지 지정해 줘야 합니다.
트리거는 다음과 같습니다.
이 과정을 거치고 난 뒤에 b값을 0과 비교합니다. 만약 b값이 0이라면 b값을 2의 제곱수의
합으로 나타냈을때의 수들과 a끼리의 모든 곱을 구해 X에 가산했으므로 곱셈이 완료된
것입니다. 하지만 b값이 0 이상일 경우에는 아직 모든 b의 요소들이 a와 곱해지지 않았으므로
t에 대입된 a의 값을 다시 a로 옮겨 준 뒤 다시 위에<<※flag 1>>표시가 된 부분부터의 과정을
b가 0이 될때까지 반복하면 X에 a*b 의 값이 대입되게 됩니다.
자 이때 b의 값이 1 이상일 경우 t의 값을 a로 옮기는 트리거를 어떻게 호출시키느냐 하면,
먼저 1강에서 보았던 '함수'역할을 하는 트리거 목록의 일부를 다시 보여드립니다.
8^6 * 3 : -
8^6 * 2 : a=t; t=0;
8^6 * 1 : X=a*b; t=a; a=b=0;
※경고 A
사실 위의 목록에서 X=a*b; 라는 표현은 사실 잘못되었지만 마땅히 간편하게 표현할 방법이
떠오르질 않아서 그냥 저렇게 표현하였습니다. 그리고 호출할때 상황으로만 보면 틀린
표현도 아닙니다. 그래도 이 상황에서 정확히 표현하자면
X+=a*(b의 2진수에서 가장 큰 자릿수); b-=(b의 2진수에서 가장 큰 자릿수);
가 되어야 합니다.
저 목록을 잘 보면 '8^6 * 3' 부분이 아래 두 트리거에 종속되어 있는 것을 알 수 있는데,
이는 즉 c값이 8^6 * 3이면 아래의 두 함수가 연달아 호출된다는 의미가 됩니다. 따라서
계산후 b의 값이 1 이상일 경우엔 c에다가 8^6 * 2만큼을 더해주면 이미 c에는 8^6 * 1만큼의
값이 있었으므로 다음번 트리거 동작주기에서 저 두 트리거가 연달아 동작하게 되어 계속
b값을 2의 제곱수로 분해한 요소들과의 a의 곱셈결과를 X에 가산하는 연산이 수행됩니다.
그러므로 b를 2의 제곱수로 분해한 요소들 중 가장 큰 수를 뺀 뒤 b의 값이 1 이상이면
c에다가 8^6 * 2만큼을 더해주고, b가 0일 경우 c에다가 8^6 * 1만큼을 빼서 곱셈 계산을
완료하는 트리거를 넣어 주면 됩니다.
자 내부는 이렇게 복잡했지만 저는 이것을 단 하나의 주소 호출로 이 모든 과정이 이루어
지도록 포장해놨으므로, 우리는 a와 b에 곱할 값들을 넣은 뒤 c값에다 8^6 * 1(곱셈 트리거의
호출주소)만 더해주면 a와 b가 곱해져 X에 대입되는 결과를 얻을 수 있습니다.
따라서 곱셈 전체를 제어해주는 트리거의 구조를 보면 우선 덧셈과 동일하게 C값이 곱셈
코드인 4일 경우 곱셈 과정을 제어하는 제어변수 범위인 1020으로 C값이 점프되며
C값이 1020일 경우 사용할 변수들을 초기화 한뒤 ①번부터 실행됩니다.
------------------------------------------------
②
8^6 * 2 : a=t; t=0;
①
8^9 * 1 : a=A;
8^8 * 1 : b=B;
8^6 * 1 : X=a*b; t=a; a=b=0; ※표현이 좀 이상한데 위의 "경고 A" 를 참고하세요.
b의 값이 1 이상일 경우 ②로 가서 위에서 아래로 다시 실행
b의 값이 0 일 경우 계산종료.(C값을 1021로 점프)
------------------------------------------------
그리고 c값이 0이고 C값이 1021일 경우엔 계산결과를 제외한 변수들을 초기화 하고 계산을
종료합니다. 이때 한 단위라서 한 주기만에 동작하긴 하지만 조건에 따라 이 한 단위를
여러번 반복하므로 한주기 만에 곱셈이 수행되지는 않습니다.
트리거는 덧셈이나 뺄셈과 유사해서 생략하도록 하겠습니다.
이렇게 덧셈, 뺄셈, 곱셈의 알고리즘과 그 구현을 알아봤습니다. 다음편에서는 나눗셈
알고리즘을 분석해 보도록 하겠습니다.
[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강. 난수 생성
