fft.py

• 이전 버전 코드
• 고속 푸리에 변환 (Fast Fourier Transform, FFT)에 적혀 있듯이, 처음에는 실제로 fft를 구현하는 코드가 있었지만, 지금은 fft 함수 자체는 존재하지 않는다. 그러나 fft를 사용해서 해결할 수 있는 문제에 동일하게 적용하도록 만들어진 함수들이므로, 모듈 이름을 fft로 유지했다.

# N multiply
# I {"version": "2.0", "import": ["decimal"], "typing": ["List", "Sequence"]}
def multiply(a: Sequence[int], b: Sequence[int], digit: int = 0) -> List[int]:
    """Returns the multiplication of two polynomials."""
    decimal.setcontext(
        decimal.Context(prec=decimal.MAX_PREC, Emax=decimal.MAX_EMAX))
    if digit == 0:
        digit = min(20, len(str(min(len(a), len(b)) * max(a) * max(b))))
    f = f'0{digit}d'
    a_dec = decimal.Decimal(''.join(format(x, f) for x in a))
    b_dec = decimal.Decimal(''.join(format(x, f) for x in b))
    c_dec = a_dec * b_dec
    total_digit = digit * (len(a) + len(b) - 1)
    c = format(c_dec, f'0{total_digit}f')
    return [int(c[i:i + digit]) for i in range(0, total_digit, digit)]

• 고속 푸리에 변환 (Fast Fourier Transform, FFT) 참고
• digit가 명시적으로 주어지지 않는 경우, 계수가 2^64보다 작을 것을 가정해서 필요한 digit를 계산한다. 만약 계수가 2^64를 초과할 수 있다면, digit를 명시적으로 주어야 한다.
• 이 함수를 사용해서 얻은 결과에 반복적으로 이 함수를 다시 적용해야 할 경우, 문자열→int, int→문자열 변환이 불필요하게 반복되는 단점이 있다. 이 부분을 생략할수 있도록 직접 구현하는 편이 더 효율적이다.