신촌우왕 소개

수학자, 천재작곡가, 요가수행자

계산기를 만들기 위해

필요한 가장 기본적인 지식은

나눗셈의 몫과 나머지에 대한 지식이다.

파이썬 계산기(13):

분수 대신 뺄셈을 이용한 몫과 나머지

b = aq + r

0 ≤ r < ｜a｜

위와 같이 몫을 구하기 위해서는 우선 b/a의 값을 계산해야 한다.

문제는 프로그래밍 언어들이 분수 계산을 잘 못한다는 것이다.

z / 1 = z와 같은 뻔한 분수 계산에서도 문제가 발생한다.

다음 두 코드는 같은 결과값이 출력되기를 기대한다.

그러나...

print(math.floor(10000000000000000000000000))
print(math.floor(10000000000000000000000000 / 1))

출력:

10000000000000000000000000

10000000000000000905969664

다른 값이 나왔으므로

문제가 발생했다.

나눗셈의 몫과 나머지를 구하기 위한 다른 대안

따라서 math.floor(b/a) 혹은 math.ceil(b/a)을 이용하여

나눗셈의 몫과 나머지를 구하는 것은 문제가 발생한다.

다른 대안은 덧셈 혹은 뺄셈을 이용하는 것이다.

보통 곱셈은 덧셈과 잘 대등되고

분수셈은 뺄셈과 잘 대응되므로

여기에서는 뺄셈을 이용하여 몫과 나머지를 구하는 대안을 제시한다.

(※ 2씩 더해가면서 넘어설 때까지 덧셈 과정을 진행하는 것도 생각할 수 있다.)

(예1) 6을 2로 나누어 몫과 나머지를 구해보자.

다음과 같이 2를 빼는 과정을 반복한다.

6 - 2 = 4

4 - 2 = 2

2 - 2 = 0

3번의 뺄셈 과정을 거쳐 0이 남았다.

3은 몫이고 0은 나머지이다.

(예2) 7을 2로 나누어 몫과 나머지를 구해보자.

다음과 같이 2를 빼는 과정을 반복한다.

7 - 2 = 5

5 - 2 = 3

3 - 2 = 1

3번의 뺄셈 과정을 거쳐 1이 남았다.

3은 몫이고 1은 나머지이다.

위의 두 경우 모두 한 번 더 빼면 남는 수가 음수가 된다.

나머지는 음수가 될 수 없다.

따라서 뺐을 때 음수가 나오면 그 전 단계까지가 유효한 몫과 나머지를 제공하게 된다.

두 양의 정수 a, b에 대하여

b를 a로 나눈 몫과 나머지를 리턴하는 메소드는 다음과 같다.

b가 a보다 엄청 클 때는 빼는 횟수가 급격하게 늘어나

몫과 나머지를 리턴하는데 곤란해질 수 있으므로

외부에서 사용하도록 허락할 수 없는 메소드라고 할 수 있다.

따라서 외부에서 접근할 수 없도록 메소드명을 두 개의 언더바로 시작하였다.

클래스 내에서

언더바 두 개로 시작하는 메소드는 외부에서 접근할 수 없다.

굳이 접근하고 싶다면

객체변수명과 클래스명을 함께 동원하여 접근할 수 있다.

model = CalcModel()

print(model._CalcModel__qr_positive_integer(27, 4))

출력은 다음과 같다.

(6, 3)

즉 27을 4로 나누면

몫은 6, 나머지는 3이다.

뺄셈법을 이용하여

몫과 나머지를 구하였다.

뺄셈을 이용한 몫과 나머지 구하기 문제점

10을 1로 나누어 몫과 나머지를 구하려면 10회의 뺄셈을 해야 한다.

(마지막 1회 추가 뺄셈은 제외)

100을 1로 나누어 몫과 나머지를 구하려면 100회의 뺄셈을 해야 한다.

1000을 1로 나누어 몫과 나머지를 구하려면 1000회의 뺄셈을 해야 한다.

자리수가 하나 늘어날 때마다 빼는 회수가 10배로 늘어난다.

즉 뺄셈 회수가 기하급수적으로 늘어나고 있음을 알 수 있다.

math.floor(b/a), math.ceil(b/a)의 값에 오류가 있는 문제점 대신에

이제는 구하는 속도에 문제가 생긴 셈이다.

10000000(천만)을 1로 나눌 때 천만번의 뺄셈을 해야 하며

이때 걸리는 시간이 약 1초라면

10억을 1로 나눌 경우 약 100초가 걸리는 셈이고

천억을 1로 나눌 경우에는 약 10000(1만)초가 걸리는 셈이다.

천억을 1로 나눈 나머지를 구하기 위해 2~3일 걸리는 셈이다.

위와 같이

뺄셈법은 정확하지만 시간이 많이 걸린다.

다음 정보에서

이를 극복하기 위한 방법을 제시하기로 한다.