FFT를 사용하는 문제들을 풀다보면 삼각함수의 연산 때문에 생기는 실수 오차 때문에 범위가 큰 문제들에 대해서는 사용하기가 조금 부담스럽다.
또한 적당히 큰 수 p로 나눈 나머지를 계산하는 등의 문제를 만나면 건드리기가 무서워진다.
이번 글에서는 하나의 해결방법인 실수를 사용하지 않는 알고리즘, NTT에 대해 알아보고자 한다.
FFT를 사용하는 문제들을 풀다보면 삼각함수의 연산 때문에 생기는 실수 오차 때문에 범위가 큰 문제들에 대해서는 사용하기가 조금 부담스럽다.
또한 적당히 큰 수 p로 나눈 나머지를 계산하는 등의 문제를 만나면 건드리기가 무서워진다.
이번 글에서는 하나의 해결방법인 실수를 사용하지 않는 알고리즘, NTT에 대해 알아보고자 한다.