2. Divide and Conquer : Multiplication

SoYeong Gwon·2022년 6월 12일
0

Algorithms

목록 보기
1/2
post-thumbnail

본 게시물은 교재 “Algorithms,” Sanjoy Dasgupta(2008)를 참고하여 구현한 알고리즘을 공유하는 게시물입니다.

머릿말

Divide-and conquer(분할정복) 알고리즘에 대해 간략히 이야기해보고, 2.1절 Multiplication에 해당하는 내용을 소개하고, 파이썬 코드를 공유하고자 한다.

분할정복 알고리즘의 전략

  1. 주어진 문제와 동일하지만 작은 규모의 서브 문제로 분할한다.

  2. 분할된 서브 문제들을 재귀적으로 해결한다.

  3. 해결된 정답들을 적절하게 정복(통합)한다.

2.1 Multiplication

이진수 곱셈에서 분할정복 알고리즘을 적용하여 문제를 해결하고자 한다.

주어진 이진수는 어떻게 분할될 수 있을까?

how to?

x=xLxR=2n2xL+xRx= x_{L}*x_{R}=2^\frac{n}{2}*x_{L}+x_{R}

위의 식으로 이진수를 분할할 수 있다.

예를 들어 x=101101102x=10110110_{2}에서, xL=10112x_{L}=1011_{2} , xR=01102x_{R}=0110_{2} 이다.

이때 xx1011224+011021011_{2} * 2^4+0110_{2}로 표현할 수 있다.

이를 참고하여,

xxyy의 곱을 다음과 같이 표현할 수 있다.

xy=(2n2xL+xR)(2n2yL+yR)=2nxLyL+2n2(xLyR+xRyL)+xRyR(1)xy=(2^\frac{n}{2}x_{L} + x_{R})(2^\frac{n}{2}y_{L} + y_{R})=2^{n}x_{L}y{L}+2^\frac{n}{2}(x_{L}y_{R}+x_{R}y_{L}) + x_{R}y_{R} - (1)

그리고 아래 식을 통해,

xLyR+xRyL=(xL+xR)(yL+yR)xLyL+xRyR(2)x_Ly_R+x_Ry_L=(x_L+x_R)(y_L+y_R)-x_Ly_L+x_Ry_R -(2)

(1) 식의 두번째 항에 해당하는 식을 한번 더 분할할 수 있다.

위의 원리를 통해 두 이진수 xxyy의 곱셈을 구하는 파이썬 코드를 구현했다.

pseudo code

function multipy(x,y)
Input: Positive integers x and y, in binary
Output: Their product

n=max(size of x, size of y)
if n=1: return xy

xl,xr=leftmost [n/2], rightmost[n/2] bits of x
yl,yr=leftmost [n/2], rightmost[n/2] bits of y

P1=multiply(xl,yl)
P2=multiply(xr,yr)
P3=multiply(xl+xr,yl+yr)

return P1*2^n + (P3-P1-P2)*2^(n/2) + P2​

위의 식을 참고해서 P1,P2,P3를 구하고, 재귀적으로 문제를 푸는 방식이다. 생각보다 어렵지 않아 보이지만, 비트 연산을 통해 구현하는 점이 다소 까다로웠다.

python code

def multiply(x,y):
  n = max(x.bit_length(), y.bit_length())

  # trivial
  if n <= 1:
    return x*y

  # divide
  k = (n + 1) >> 1
  x1 = x >> k
  x0 = x - (x1 << k)
  y1 = y >> k
  y0 = y - (y1 << k)

  # recursions
  a = karatsuba(x1, y1)
  c = karatsuba(x0, y0)
  p = karatsuba(x0 + x1, y0 + y1)
  b = p - a - c

  # conquer
  return (a << (n + (n & 1))) + (b << k) + c

print(karatsuba(10,20))

multiply 함수를 통해 10과 20의 곱을 구하였다.

Details

이 코드에서 가장 중요한 부분인 divide 파트를 설명하고자 한다.
설명에 앞서 비트 연산을 잠깐 짚고 넘어가겠다.

  • <<
    변수의 값을 지정된 비트 수 만큼 왼쪽으로 이동한다.
    곱하기
  • >>
    변수의 값을 지정된 비트 수 만큼 오른쪽으로 이동한다.
    나누기

예시를 들자면

print(10<<3) # 10 * 2^3
>> 80
print(10>>2) # 10 * 2^2
>> 2

이제 코드를 살펴보겠다.

# divide
k = (n + 1) >> 1

주어진 n의 값(x와 y의 최대 비트 수)를 2로 나눠준 값 k를 구한다. 이때 비트는 0부터 시작하니, n에 1을 더해준다.

x1 = x >> k
x0 = x - (x1 << k)

각 변수의 left most, right most를 구한다. x1은 xLx_L을, x0은 xRx_R을 의미한다.

우선 x 값을 k 등분 내서 left를, 전체 x에서 left를 빼서 right를 구한다. (y의 경우도 동일하다.)


맺음말

2.1절 multiplication에 해당하는 부분을 공부해보았다.
분할정복의 경우, 처음에는 이해하는데 시간이 꽤 걸렸다. 손코딩을 계속하면서 알고리즘 원리를 숙지하고, python으로 구현하는데에도 오래 걸렸다. 그치만 '재귀'가 한번 눈에 보이면 꽤 익숙해지고, 센스도 생기는 듯하다. 눈으로 보는 것 보다 손으로 쓰면서 익혀보자.

다음에는 2.3절 Merge sort에 해당하는 부분을 공유하고자 한다.

0개의 댓글