FWHT(Fast Walsh Hadamard Transform)

본 글은 코드포스 블로그를 번역, 정리한 글입니다. 오타, 오역은 댓글로 피드백 부탁드립니다. 솔직히 번역 진짜 자신 없었습니다..

본 글을 이해하기에 앞서 DFT/FFT에 대한 이해가 무조건 필요합니다.

FWHT가 무엇일까?

만약 두개의 집합$(1,2,2)$와 $(3,4,5)$를 갖고 있고 둘 사이에서 일어날 수 있는 가능한 모든 xor을 구한다면, 결과는 $(1,1,2,4,5,6,6,7,7)$이 될 것이다.

이를 흔히 xor convolution이라 부르고, 이를 naive하게 구현한다면 $O(n^2)$에 할 수 있다.

FWHT는 흑마법 FFT 트릭을 이용해 이를 $O(n\log n)$에 하도록 만들어준다.

그러면 이게 왜 되는 걸까? 그리고 이걸 왜 알아야 할까?

우선 첫 번째 질문에 대답해보자. FFT에 대한 두가지 사실을 알고난 다음이지만..

Fact 1

우선 $(1+2x)$ 와 $(3+4x)$를 곱한다고 하자. 우선 사이즈를 4로 맞춰 줘야 한다. 그리고 나서 point-value form으로 만들고, pointwise 곱셈을 해준뒤, 다시 inverse FFT를 통해 원래 값을 구한다.

첫 단계에서 이 곱셈의 최종 크기가 3인 걸 알기 때문에 우리는 적어도 3개의 point-value 쌍들이 필요할 것이다.

만약 이렇게 크기를 바꾸지 않는다면? 우리는 $(3+10x+8x^2)$ 대신에 $(11+10x)$를 얻게 될 것이다.

그 이유를 찾아보자면 우리가 1과 -1이라는 1의 제곱근밖에 사용하지 않기 때문일 것이다.

여기에는 $x^2=1$이라는 식이 존재하기 때문에 이차 항이 상수항에 기여를 하면서 "사라지게" 된다.

여기서의 교훈은, 만약 우리가 충분히 세밀한 근을 사용하지 않는다면, 더 높은 고차항이 "사라지게" 된다는 것이다.

Fact 2

우리는 일변수 다항식을 서로 곱할때 FFT를 사용하는데, 다변수 다항식의 경우는 어떨까?

모든 것은 전과 같다.

단지 우리가 필요한 것은 다시 그걸 다항식으로 되돌리기 위한 적절한 point-value form인 것이다.

크기 n의 일변수 다항식의 경우 우리는 n개의 값이 필요했다.

(fft에서는 분할정복을 위해 1의 거듭제곱근을 사용한다.)

다변수 다항식에서는 $P(x,y) = (1 + 2x + 3y + 4xy)$를 예로 들어보자.

우리가 필요한 것은 각 변수에 대한 각자 다른 값들일 것이다.

여기에서는 $x$도 1차이고, $y$도 1차이므로 우리는 이것들에 대해서 두개의 distinct value set이 있기만 하면 된다.

예를 들어 10,20과 30,40을 각각 $x$, $y$에 사용한다면, $P(10,30)$, $P(20,30)$, $P(10,40)$, $P(20,40)$이 각각 $1$, $x$, $y$, $xy$로 $P(x,y)$를 유일한 형태로 표현 가능하다.

심지어 우리는 10,20을 $x$, $y$ 둘 다에도 사용할 수 있으며, 이 또한 멀쩡히 작동할 거다.

우리는 이를 다변수 다항식 FFT에 적용하여, $x$에 대한 다항식을 계수로 갖는 $y$의 다항식 형태로 바꿀 수 있다.

$P(x,y) = (1+2x)+y(3+4x)=Q_0(x) + yQ_1(x)$처럼 말이다.

먼저 $Q_i$들에 대해서 FFT를 적용하여 $Q_0(1)$, $Q_0(-1)$, $Q_1(1)$, $Q_1(-1)$ 의 값을 얻을 수 있다.

그리고 $Q_0(1) + yQ_1(1)$ 과 $Q_0(-1) + yQ_1(-1)$에 FFT를 적용하여 $P(1,1)$, $P(1,-1)$, $P(-1,1)$, $P(-1,-1)$을 얻을 수 있다.

여기서의 교훈은 다변수 다항식의 FFT는 그저 값들을 좀 묶어서 계산하는 일반 FFT일 뿐이라는 것이다.

드디어 FWHT

앞에서 말했듯 FWHT는 빈도수 배열을 pointwise 곱셈을 했을때 xor을 수행하는 어떤 굉장히 신비로운 형태로 만들어준다.

여기서 다항식 곱셈과의 유사성을 한번 따져보자.

다항식 곱셈에서 $ax^i$와 $bx^j$의 곱은 $abx^{i+j}$로 합쳐진다.

우리는 이런 병합을 모든 가능한 쌍들에 대해 수행하고 $x$의 차수에 따라 묶어서 정리한다.

FWHT에서 우리가 원하는 것은 $ax^i$와 $bx^j$의 곱이 $abx^{i\oplus j}$가 되는 것이다. 우리는 여기서 굉장히 흥미로운 일을 할 수 있는데, 변수를 더 여러개의 변수들로 쪼개는 것이다!

예를 들어 $ax^3$과 $bx^5$는 $ax_2^0x_1^1x_0^1$과 $bx_2^1x_1^0x_0^1$ 으로 쪼갤 수 있을 것이다.

이 새로운 형태를 이용하면 xor 합성곱이 더 쉬워진다!

$x^0_i⋅x^0_i=x^1_i⋅x^1_i=x^0_i$ 과 $x^0_i⋅x^1_i=x^1_i$ 을 이용해서

$ax_2^0x_1^1x_0^1$과 $bx_2^1x_1^0x_0^1$의 곱이 $abx_2^1x_1^1x_0^0$이 되는 것이다. ($3\oplus 5 = 6$)

이제 마지막 장애물이다. 사실 $x^1_i⋅x^1_i=x^0_i$는 거저 주어지는 게 아니다.

$x^p_i⋅x^q_i=x^{(p+q) \mod 2}_i$가 돼야 한다.

그런데! 앞에서 말했던 Fact 1을 다시 되돌려 생각하면, 우리가 만약 숫자를 1과 -1만 사용한다면 $x^2=1$ 때문에 $x^p_i⋅x^q_i=x^{(p+q) \mod 2}_i$가 저절로 달성된다!

자! 이제 다 합쳐보자!

우리는 $ax^i$라는 항을 지수의 이진수형태로 쪼갤거고, 이 새로운 다항식을 다변수 FFT로 바꿀 거고 각 변수에 대해서는 1과 -1을 사용할 것이다.

이래서 FWHT는 좀 더 쩌는 FFT가 됐다!

그러나 이제 처음에 물어봤던 두 개의 질문중 두 번째, 이걸 왜 알아야 할까?

이유는 간단하다. 이 알고리즘을 좀더 특정한 의도로 사용하기 위해서는 알고리즘을 이해해야 한다.

예를 들자면 or convolution이나 and convolution이 있을 것이다.

정리하며..

진짜 진짜 번역하는 건 세상에서 제일 어려웠는데, 막상 하고나니 내용 자체는 별로 어렵지도 않고 FFT에 대한 지식이 있는 누구든 이해할 수 있는 내용인 것 같다.

빨리 Just as Tic Tac Toe 문제를 풀러 가야겠다..