algorithm - 2 的幂的准确单位根？

Question

单位的 n 次根是多项式方程 x^n = 1 的解。对于 n = 2^k，对于某些 k(即，其中 n 是 2 的幂)，是否有一个众所周知的算法？

计算 n 次单位根的算法有很多种。例如，这是一个使用 Numpy 的“roots”函数返回根数组的 Python 实现。

import numpy as np;
def omegas(n):
    #make the n-degree polynomial and solve for its roots
    poly = [0]*(n+1)
    poly[0] = -1; #constant
    poly[-1] = 1; #highest degree
    return np.roots(poly)

您还可以使用三角函数:

import numpy as np
import cmath
def trig_omegas(n):
    return np.array([cmath.rect(1,x*np.pi) for x in range(n)])

但准确性让我很失望。对于 n=4，答案应该是这样的:

array([-1.+0.j,  0.+1.j, -0.-1.j,  1.+0.j])
#or, in counterclockwise order
array([ 1.+0.j,  0.+1.j, -1.+0.j, -0.-1.j])

这是上述函数的结果。

>>> omegas(4)
array([ -1.00000000e+00+0.j,   8.32667268e-17+1.j,   8.32667268e-17-1.j,
         1.00000000e+00+0.j])
>>> trig_omegas(4)
array([ 1. +0.00000000e+00j, -1. +1.22464680e-16j,  1. -2.44929360e-16j,
       -1. +3.67394040e-16j])

尾随零表示末尾有一个小错误。 omegas(4) 的第一个条目实际上比 -1 小一点。

omegas(4)[0] (-1.0000000000000004+0j)

有没有更好的方法求2的幂单位根？

Answer 1

您可能喜欢图书馆 Sympy。尝试求解单位的第五根

solve(x**5-1)

在 http://live.sympy.org/ 的控制台中

要将精确解转换为浮点近似值，请执行[x.evalf() for x in solve(x**5-1)]