[Python] FFT 구현 안하고 FFT 문제 풀기?

이번 글에서 다뤄볼 주제는 FFT를 구현 안하고 FFT 문제를 빨리 푸는 방법이다.

얼마전에 FFT를 알고리즘 스터디 시간에 열심히 증명하고, 파이썬으로 구현체를 열심히 만들었던 기억이 있다.

물론, 구현체는 아직도 외우지 못해서 내가 예전에 만든걸 복붙하고 있다.

 

하지만, , , , , 가끔씩 숏코딩을 들어가보면 터무니없이 짧은 길이의 코드들이 있다.

도대체 어떻게 푼 것일까????

 

---

1. 파이썬 언어의 특징

파이썬에서는 C++과 달리 매우 큰 수 연산이 쉽게 가능하다.

파이썬 내부적으로 큰 수 연산을 어떠한 방법을 써서 하기 때문이다.

곱셈을 예를 들자면, 

 

자리수가 적당히 작으면 파이썬은 그냥 우리가 알고있는 곱셈 방법을 쓴다.

다만, 자리수가 적당히 커지면

파이썬은 FFT를 기반으로 한 알고리즘이나 카라추바 알고리즘을 쓴다

 

파이썬은 내부적으로 FFT를 쓴다고 할 수 있다!!!

 

그러니까, 이 '큰 수 곱셈'을 잘 응용하면 FFT 코드를 굳이 구현 안하고도 FFT의 기능을 쓸 수 있다.

 

2. 원리

조사해본 결과(그리고 테스트해본 결과) 파이썬은 매우매우 터무니없이 큰 정수(거의 천만~억자리)의 곱셈도 지원을 한다.ㅋㅋㅋㅋㅋ

다만, 기본적으로 파이썬 정수 곱셈에는 4300자리인가? 제한이 있다.

sys 모듈을 어떻게 써서 이 4300자리 제한을 풀 수 있다.

 

아니면 또 다른 방법은 decimal 모듈을 쓰는 것이다.

decimal 모듈에서도 정밀도를 최대로 설정하면 무지막지하게 큰 수의 곱셈도 할 수 있는데 얘는 대신 4300자리 제한이 없다.

그래서 decimal 모듈을 이용해보자.

 

예를 들어 두 다항식의 곱셈을 하는데, 각 계수가 1,000,000 이하의 자연수라고 해보자.

이론상 나올 수 있는 최대 계수가 1,000,000 * 1,000,000 * (길이) 해서

대충 20자리라고 하자.

 

이 자릿수가 굉장히 중요한데, 왜냐하면 이 '자릿수 블록'을 넘어가면(Overflow) 다른 수와 연산이 겹쳐서 정보가 손실된다.

 

예를들어서 x+2와 3x+2, 두 일차식을 더한다 하면

우리는 이 두 개의 식을 다음과 같이 바꿔줄 수 있다. (x에 10**20을 대입한거다)

 

 

그리고 이렇게 얻은 두 수를 decimal.Decimal 형태로 바꿔준 다음 그냥 곱해버린다!

그러면 그 결과가

100000000000000000002 * 300000000000000000002

= 30000000000000000000800000000000000000004

이걸 20자리씩 끊으면 그 계수가 된다.

 

이걸 구현할 때

Decimal이 string으로 저장된다는 점과, 포맷스트링 f'0{20}d'를 이용하면 쉽고 간단하게 구현할 수 있다.

물론 뭐 이건 쉬워서 여러분 마음대로 구현하면 된다.

 

이 트릭을 바로 이용할 수 있는 예제로는 다음이 있다.

https://www.acmicpc.net/problem/11385