Отделение БПФ для быстрого полиномиального подразделения ⇐ Python

[Anonymous]

Я пытаюсь реализовать быстрое полиномиальное разделение, используя Fast Fourier Transform (FFT). < /p>

Вот что я получил до сих пор: < /p>

from numpy.fft import fft, ifft
def fft_div(C1, C2):
# fft expects right-most for significant coefficients
C1 = C1[::-1]
C2 = C2[::-1]
d = len(C1)+len(C2)-1
c1 = fft(list(C1) + [0] * (d-len(C1)))
c2 = fft(list(C2) + [0] * (d-len(C2)))
res = list(ifft(c1-c2)[:d].real)
# Reorder back to left-most and round to integer
return [int(round(x)) for x in res[::-1]]
< /code>

Это хорошо работает для полиномов одинаковой длины, но если длина отличается, то результат неверен (I эталон против Rosettacode extended_synthetic_division () < /code> function): < /p>

# Most signficant coefficient is left
N = [1, -11, 0, -22, 1]
D = [1, -3, 0, 1, 2]
# OK case, same length for both polynomials
fft_div(N, D)
>> [0, 0, 0, 0, 0, -8, 0, -23, -1]
extended_synthetic_division(N, D)
>> ([1], [-8, 0, -23, -1])

# NOT OK case, D is longer than N (also happens if shorter)
D = [1, -3, 0, 1, 2, 20]
fft_div(N, D)
>> [0, 0, 0, 0, -1, 4, -11, -1, -24, -19]
extended_synthetic_division(N, D)
>> ([], [1, -11, 0, -22, 1])
< /code>

Что странно, так это то, что кажется очень близким, но все же немного отключено. Что я сделал не так? Другими словами: Как обобщить быстрое полиномиальное разделение (с использованием FFT) для векторов разных размеров .

также бонус, если вы можете сказать мне, как вычислить разделение (в настоящее время у меня есть только ).>

Подробнее здесь: https://stackoverflow.com/questions/447 ... l-division