구구단 계산을 덧셈 뺄셈 만으로 하기

중학교 수학만 공부한 사람이면 누구나 아는 계산식

             ab = ((a + b)^2 - (a - b)^2)/4

를 이용하는 곱셈 계산법에 대해서 알아 보자.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
G(n)	0	0	1	2	4	6	9	12	16	20	25	30	36	42	49	56	64	72	81

(위의 표에서 G(n) = n*n/4 = (n^2)/4 이다, )
G(n) = k^2  if n = 2k (짝수), G(n) = k(k+1) = k^2 + k if n = 2k + 1 (홀수) 임을 이용해도 된다.
이 때는 제곱수만 기억하고 있으면 된다.



예를 들어 8*7 의 값을 구한다고 하자. 먼저 8과 7의 합과 차를 구한다.

   8 + 7 = 15
   8 -  7 = 1

이다. 위의 표에서 G(15)와 G(1)을 구하여 각각 구하여 빼면 8*7과 같은 값이 된다.
즉,

    G(15) - G(1) = 56 - 0 = 56 = 8*7

이다,

4*8 계산을 다시 해보자.
G(8 + 4) - G(8 - 4) = F(12) - G(4) = 36 - 4 = 32 = 4*8 = 8*4

이는 우연의 일치가 아니다.

G(9 + 9) - G(9 - 9) = G(18) - G(0) = 81 - 0 = 81 = 9 *9
G(9 + 2) - G(9 - 2) = G(11) - G(7) = 30 - 12 = 18 = 9*2 = 2*9

 

만일  19단표를 만든다고 하면 G(0) 부터 G(38) 까지의 표만 만들어 두면 이런 방법으로
1*1 부터 19*19 까지의 361 가지 곱셈을 할 수 있다.

컴퓨터 프로그래밍으로 1만 이하의 두 자연수 곱셈 결과를 모두 저장해 두고 저장한 표에서 값을 가져 올려면 표에는 1만 곱하기 1만 가지(즉 1억 가지)의 곱셈 결과를 저장해 두어야 한다. 이것은 엄청난 메모리량을 요구한다. 그런데 위와 같은 표를 만들어서 한다면, G(0) 부터 G(20000) 까지의 표만 만들어 두면 된다. a와 b가 1만 이하의 자연수 이고 a 가 b 보다 크거나 같다면 a*b 의 값은 G(a + b) - G(a - b)로 구할 수 있다. 덧셈 한 번, 뺄셈 두 번, 표에서 찾아오기 두번이면 된다.




이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.