Script Programming(스크립트 프로그래밍)

정수의 곱셈을 빨리하기 위한 방법 중의 하나로

기수법으로 표현된 정수를 여러 조각으로 분할하여

덧셈이나 뺄셈 회수는 몇회 증가하는 대신, 곱셈 횟수를 몇회 감소하는

방법입니다. 곱셈이 덧셈이나 뺄셈 보다는 시간이 많이 걸린다는

전제 하에 카라츄바 곱셈(Karatsuba multiplication)을 적용하면

시간복잡도 O(N**2) 의 계산 과정을 을 약 시간복잡도 O(N*&1.5)의 계산 과정으로

줄일 수 있습니다.  (여기서 N은 기수법으로 표현된 정수의 분할 개수입니다.)

예를 들어  두 자리 십진법 수 23과 45의 곱셈 23*45을 생각해 봅니다.

(이 경우 N = 2 입니다.)

                  2  3
          x )     4  5
            -----------
                  1  5
               1  0
               1  2
               8
            -----------
            1  0  3  5

위의 곱셈표에서 보듯이,

   곱셈은 3*5 = 15, 2*5 = 10, 3*4 = 12, 2*4 = 8 로 모두 4회입니다.

   덧셈은 15 + 10 + 12 + 8 로 모두 3회입니다.

그러므로.   곱셈 회수 + 덧셈 회수 = 4(회) + 3(회) = 7(회) 입니다.

덧셈이나 뺄셈을 한 후에 곱셈을 할 때는 분배법칙(혹은 배분법칙)

    (a + b)*(c + d) = a*c + b*d + a*d + b*c = (a*c + b*d) + (a*d + b*c)

이 성립하므로 a 에는 2를, b 에는 3을, c에는 4를, d에는 5를 각각 대입하면 

    (2 + 3)*(4 + 5) = 2*4 + 3*5 + 2*5 + 3*4 = (2*4 + 3*5) + (2*5 + 3*4)

앞에서 했던 계산 중에 2*5 = 10, 3*4 = 12 은 곱셈이 2회인데,

이 계산을 (2 + 3)*(4 + 5) = (2*4 + 3*5) + (2*5 + 3*4)

즉, 2*5 + 3*4  = (2 + 3)*(4 + 5) - (2*4 + 3*5)  임을 이용하면 곱셈을 1회 줄일 수 있습니다. (덧셈과 뺄셈 회수는 조금 불어닙니다.)

왜냐 하면 2*4 = 8 (10의 자리수 곱셈)과 3*5 = 15 (1의 자리수 곱셈)은 미리 했으므로

(2 + 3)*(4 + 5) 만 계산하고 여기에 미리 계산된 (2*5 + 3*4) 을 뺄셈하면 2*5 + 3*4 을

구 할 수 있습니다.

(2 + 3)*(4 + 5) -  (2*4 + 3*5) = 5*9 - (8 + 15) = 45 - 23 = 22

이 계산에는 덧셈 1회, 뺄셈 1회, 곱셈 1회입니다.

                  2  3
          x )     4  5
            -----------
               8  1  5
               2  2          = (2 + 3)*(4 + 5) - (8 + 15) = 45 - 23 = 22
            -----------
            1  0  3  5

위의 곱셈표에서 보듯이,

   곱셈은 2*4 = 8, 3*5 = 15, (2 + 3)*(4 + 5) = 45 로 모두 3회입니다.

   덧셈은 2 + 3 = 5, 4 + 5 = 9, 8 + 15 = 23 으로 모두 3회입니다.

   뺄셈은 45 - (8 + 15) 로 1회,

  그리고  815 + 220 에 덧셈 1회 입니다.

  그러므로 덧셈과 뺄셈은 총 5회, 곱셈은 3회가 됩니다.

그러므로.   곱셈 회수 + 덧셈과 뺄셈 회수 = 3(회) + 5(회) = 8(회) 입니다.

위의 예에서는 두 자리 십진법 수의 곱셈을 보여주었는데,

이 카라츄바 곱셈 방법은 N자리 r진법  수의 곱셈에도 적용할 수 있습니다.

 예를 들어, 4자리 16진법수 곱셈  0xCAFE * 0xABBA 에도 적용할 수 있습니다.

                  C  A  F  E
          x )     A  B  B  A
            ----------------

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

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

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

(위의 표에서 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 대한민국 라이센스에 따라 이용하실 수 있습니다.