데이터 타입만을 사용한 복소수와 FFT 구현 (부동 소수점 없이)
2025-05-25
이 글에서는 부동 소수점을 사용하지 않고 대수적 데이터 타입만을 사용하여 복소수와 고속 푸리에 변환(FFT)을 구현하는 방법을 제시합니다. 저자는 먼저 숫자 표현에 대수적 데이터 타입을 사용하는 장점을 설명하고, 기존 FFT 구현의 비효율성을 지적합니다. 그런 다음 대수적 데이터 타입만을 사용한 간결하고 우아한 정수와 복소수 구현을 보여줍니다. 마지막으로, 부동 소수점을 사용하지 않는 순수 함수형 구현 방식의 복소수 FFT를 유도합니다. 이는 균형 잡힌 삼진수 표현으로 정수를 표현하고, 가우스 정수를 확장하여 복소수를 표현함으로써 부동 소수점 연산의 융합 저해 효과를 교묘하게 피하여 알고리즘의 효율성을 높입니다.
개발
대수적 데이터 타입