在Python中计算单位的n根

Question

所以，我试图写一个算法croot（k，n），它返回n==n的单位的第k个根。我得到的答案基本上是正确的，但是它给了我一些非常奇怪的表示，对于某些数字来说似乎是错误的。这里有一个例子。在

import cmath

def croot(k, n):
    if n<=0:
        return None
    return cmath.exp((2 * cmath.pi * 1j * k) / n)


for k in range(8):
    print croot(k, 8)

输出为：

^{pr2}$

喔喔喔喔喔喔喔。所以k=2和n=8时的根是错误的，因为它应该是i，它可以表示为1j，或者j，或者1.00000j，等等，有人能帮我吗？我正在写一个FFT算法，因为我在写这个。我对复数和Python不是很有经验，所以我很可能会犯一个简单的错误。在

谢谢

如果你们需要更多的信息，尽管问。在

Answer 1

下面是unity的立方根和第四根的用法示例。输入数组应解释为多项式系数。在

>>> import numpy as np
>>> np.roots([1, 0, 0, -1])
array([-0.5+0.8660254j, -0.5-0.8660254j,  1.0+0.j       ])
>>> np.roots([1, 0, 0, 0, -1])
array([ -1.00000000e+00+0.j,   5.55111512e-17+1.j,   5.55111512e-17-1.j,
         1.00000000e+00+0.j])

---

编辑：多项式系数按以下顺序在输入数组p到np.roots(p)中给出：

p[0] * x**n + p[1] * x**(n-1) + ... + p[n-1]*x + p[n]

例如，要返回第n个单位根，即方程1 * x**n - 1 == 0的解，可以使用类似p = [1] + [0] * (n - 1) + [-1]的输入。在

Answer 2

看看这个数字

(6.12303176911e-17+1j)

6.12303176911e-17=0.0000000000000000612303176911非常小（接近于零）。您看到的是由于浮点数的有限表示而导致的舍入错误

这个误差相当于测量到太阳的距离在10微米左右。如果你对来自真实世界的数据运行FFT，测量误差通常远大于此。在

Answer 3

在使用Python3.5.2时，numpy.roots内存不足，当我试图确定unity的第1200个根时，我的Chromebook崩溃了。崩溃发生在他们构造多项式的伴随矩阵时，所以我不认为他们使用的是稀疏表示。从文件中：

The algorithm relies on computing the eigenvalues of the companion matrix

如果您只需要计算单位根，三角法方法在时间和空间复杂性方面都是渐进式的更好：

def nthRootsOfUnity1(n): # linear space, parallelizable
    from numpy import arange, pi, exp
    return exp(2j * pi / n * arange(n))

如果您愿意放弃并行化，可以使用生成器为每个额外的根实现恒定的空间和恒定的时间，而第一种方法必须在返回之前计算所有n个根：

^{pr2}$

在我的机器上，在不使用并行化的情况下，这些方法在numpy.roots计算第1000个根所需的时间内计算出第10000000个根：

In [3]: n = 1000

In [4]: %time _ = sum(numpy.roots([1] + [0]*(n - 1) + [-1]))
CPU times: user 40.7 s, sys: 811 ms, total: 41.5 s
Wall time: 10.8 s

In [5]: n = 10000000

In [6]: %time _ = sum(nthRootsOfUnity1(n))
CPU times: user 4.98 s, sys: 256 ms, total: 5.23 s
Wall time: 5.23 s

In [7]: %time _ = sum(nthRootsOfUnity2(n))
CPU times: user 11.6 s, sys: 2 ms, total: 11.6 s
Wall time: 11.6 s