Mixed Precision (1) 정수 표현법

Intro

Mixed Precision을 사용하려 보니, 옛날 컴공때 나를 스쳐 지나간 개념이 사용됬다. 제한된 bit로 어떤 숫자를 어찌 표현 가능할까? 다시 확인해보자.

정수의 표현

부호가 없는 정수

컴퓨터는 정수를 이진수로 표현한다. 가령, 8 bit는 00000000 ~ 11111111 까지 표현가능하다. 10 진수로 하자면 0 ~ 255 범위를 표현 가능하다는 사실이다. 마찬가지로 N bit는 아래만큼 표현 가능하다.

$$0 \sim 2^{N}-1$$

하지만, 이는 어디까지나 부호가 없는 정수의 표현에 해당한다. 

부호가 있는 정수

Sign magnitude

부호 정보까지 표현 하려면, 주어진 bit중 하나의 bit에 부호 정보를 표시하는 방법이 있다. 예를들어, 아래처럼 가장 앞자리 bit에 1을 넣으면 음수라는 의미로 약속하는 것이다.

$$10001000_2=-8_{10}$$

이 경우 8 bit으로 표현 가능한 숫자는 11111111 ~ 01111111, 10진수로는 -127 ~ 127 이 될 것이다. 일반화하자면, N bit에서는 아래의 범위 만큼 표현 된다는 것이다.

$$ - 2^{N-1} + 1 \sim 2^{N-1}-1 $$

웃긴건 이렇게 정수를 표현하면 0이 +0 과 -0으로 두가지로 표현된다.

이 방법은 sign magnitude로 불리며, 직관적이라는 장점이 있지만, 계산시 뺄셈에 대한 고려가 따로 되어야 하여 비용의 효율문제가 발생한다. 예를들어, 10 + (-8)을 한다면 00001010 + 10001000을 해야하는데, 일반적인 2진법의 덧셈으로는 $10010010_2=-19_{10}$가 나오게 되어 오답이 됨으로, 뺄셈에 대한 고려가 따로 되어야 한다. 위의 예제에서 10001000를 00001000으로 바꾸고 2진수의 뺄셈을 해줘야한다는 이야기이다.

Complement

보수계산법을 이용하면 이 문제는 해결된다. 보수계산법이란, 보수를 사용하여 빼기를 따로 고려하지 않으며 연산가능하게 하는 방법으로, 아래의 예시를 보면 이해하기 쉽다.

예를들어, $500 - 310$의 계산에서 세자리수만 고려한다했을 때, 310의 보수는 999 - 310 + 1 = 690 이다. 999 - 310 = 689부분은 가보수 라고한다. 가보수는 N진법 기준 N-1 진법으로, 10진법 기준 9의 보수 그리고 2진법 기준 1의 보수라 생각하면 된다.

 

$500 + (-310)$

> $500 + 689 + 1$

> $1190$

> Carry는 고려대상 아님, 날리자. (1)$190$

 

참고로 자리수를 넘어가는 수는 carry라고 하며 이 수가 나온다면 고려대상이 아님으로 날린다.

 

이 방법은 2진법에서도 그대로 적용되는데, 재미있는 점은 2진법에서 보수계산법을 사용하기 위해 가보수를 구하면 모든 bit를 그저 반전한 것이됨으로, 각 bit에 대한 not 연산과 같아 진다는 것이다. 음수를 위해 보수를 해봤더니, not(-)이 된다고...?! 뭔가 거대한 원리같은게 숨겨져있나...?! 예를들어, 1010의 가보수는 1111 - 1010 = 0101이 된다.

 

$15 + (-10)$

> $1111_2 - 1010_2$

> $1111_2 + 0101_2 + 0001_2 $

> $10101_2$

> (1)$0101_2$ 

> $5$

 

쨘!

 

그렇다면, 결과값이 음의 값이 나오는 경우도 커버 가능할까? 

 

$-15 + 10$

> $-1111_2 + 1010_2$

> $0000_2 + 0001_2  + 1010_2 $

> $0001_2 + 1010_2 $

> $1011_2$ 

> $11$

 

오답이 나온다. 이는 carry가 없는 경우로 결과값을 음수라 처리한다. 이때에는 보수가 아닌, 가보수를 사용하여 계산하고, 2진법의 마지막 단계에서 not 연산을 한번 더 해주어야 한다. 아래 참고.

 

$-15 + 10$

> $-1111_2 + 1010_2$

> $0000_2  + 1010_2 $ (가보수 사용)

> $1010_2 $

> $0101_2$ (not 연산)

> $-5$ (케리 없으니 음수 취급)

 

이에 따라 표현 가능한 정수의 범위는 아래와 같다.

 

$$ - 2^{N-1} \sim 2^{N-1}-1 $$

 

기존의 방법보다 음수를 하나 더 표현 가능하다. 그 이유는 +0 과 -0 두개를 표현하지 않으며, 0으로 표현 할 수 있기때문이다. 여러 이유에서 이 방법이 더 나아보인다. 그래서인지 대부분의 컴퓨터 정수 표현은 complement를 이용한다고 한다.

Outro

Mixed precision을 위해 정수 부분에 대한 컴퓨터의 표현을 복습했다. 오랜만에 컴퓨터 구조에서 배웠던 이진법 연산을 하니 재미있었다. ALU에서 이게 처리됬었나...? 벌써 가물가물하다... 그리고 여기서 사용된 2진법에서의 가보수는 영어로 1's complement, 보수는 2's complement라 보통 표현한다. 그리고 not 연산이라고는 했지만, xor 연산이 더 어울리는 표현 같다.

 

여러 예제를 다루며 깊게 보지는 않았지만, 다음 내용을 이해하기에는 충분한듯하다. 이를 이해하면, 상황이 맞을 때 계산시 필요한 자원을 절반으로 할 수도 있을것 같다는 생각이든다. 예를들어, 비음수행렬의 표현시, 행렬의 원소들이 모두 비음수이기 때문에 아래와 같이 8비트의 표현으로 커버되는 상황에서 4비트로 반토막 내어 기존과 동일하게 표현가능 할 수도 있지 않나 싶기 때문이다. 

물론 NMF같은 작업에는 실수영역이라 조금 다르겠지만...  그래서!! 다음 단계는 부동소수점에 대한 표현을 복습할 예정이다.

Source

(Image) https://medium.com/@1206_90373/twos-complement-and-negative-numbers-for-integers-cf20a45bf098

Two’s complement and negative numbers for integers