快速傅里叶逆变换的实现

Question

我正在尝试用 Python 编写 FFT 算法，并且初始变换已经开始工作。它接受向量形式的多项式，并在复数单位根处输出该向量的评估。这个问题出现在我的逆 FFT 中。这应该在复根处评估函数并返回通过这些点的多项式。后半部分几乎与前半部分相同，但它使用复数根的逆。其输出按输入点数缩放，因此每个系数都除以该数字。

我的代码如下所示：

import math

from cmath import sqrt


def getNthRoots(n):
    # Determines how many roots are needed. Only works for powers of two.

    targetLength = math.pow(2, math.ceil(math.log(n, 2)))
    newOutput = [1.0 + 0j]

    # Starting with just 1, it takes the sqrt of each term and appends it. Then it appends a negative copy of the list.

    while len(newOutput) < targetLength:
        previous = newOutput
        newOutput = []

        for item in range(len(previous)):
            newOutput.append(sqrt(previous[item]))

        for item in range(len(newOutput)):
            newOutput.append(newOutput[item] * -1)

    return newOutput

这非常有效。

def FFT(inputList, rootsOfUnity):
    # End case for the loop

    if len(inputList) == 1:
        return [inputList[0]]

    # Splits the input list into two parts, one even and one odd

    evenList = [inputList[2 * x] for x in range((len(inputList) // 2))]

    oddList = [inputList[(2 * x) + 1] for x in range(len(inputList) // 2)]

    # Takes the "square" of the roots of unity. This is the same as just taking every other entry.

    newRootsOfU = [rootsOfUnity[2 * x] for x in range((len(rootsOfUnity) // 2))]

    # Calls itself with the even and odd halves and the shortened roots of unity

    evenTransform = FFT(evenList, newRootsOfU)

    oddTransform = FFT(oddList, newRootsOfU)

    outputs = []

    # Calculates the output for each root of unity

    for x in range(len(rootsOfUnity)):
        outputs.append(evenTransform[x % (int(len(rootsOfUnity) / 2))] + rootsOfUnity[x] * oddTransform[
            x % (int(len(rootsOfUnity) / 2))])

    return outputs

PolyVec1 = [1, 5, 3, 2]

# addZeros just attaches zeros until the length of the list is a power of two
PolyVec1 = addZeros(PolyVec1)

# Converts PolyVec1 into point form
rootsOfUnity = getNthRoots(len(PolyVec1))

PolyPoint1 = FFT(PolyVec1, rootsOfUnity)
toBeInverted = getNthRoots(len(PolyVec1))
InvertedRoots = [1 / i for i in toBeInverted]
reversedFFT1 = FFT(PolyPoint1, InvertedRoots)
print(reversedFFT1)
reversedFFT1Final = [abs(i) / len(reversedFFT1) for i in reversedFFT1]
print(reversedFFT1Final)

该代码可以很好地将多项式转换为一系列点。然而，当我尝试用它来求逆时，它不适用于次数大于 3 的多项式。

知道为什么吗？

编辑：

我有了一些新的见解。 的输出

任何多项式[a, b, c, d, e, f, g, h]

是

[a, y, c, z, e, y, g, z]

a, c, e, 和 g 都是一致插值，但 b、d、f 和 h 则不然。 b和f被相同的值替换，d和h被不同的值替换。只要 b 和 f 相同且 d 和 h 相同，输出就是正确的。

编辑：

更多见解。它与复数有关。无论输入如何，a、c、e、g 始终没有复数分量，并且当 b 和 f 或 d 和 h 相同时，输出没有复数分量。当存在复杂的组件时，输出不正确。