2的冪的統一的精確根源？

單位的第n個根是多項式方程x^n = 1的解。 n = 2^k是否有一個很好的已知算法，對於某些k（即n是2的冪）？2的冪的統一的精確根源？

有許多用於計算統一的第n個根的算法。例如，這是一個Python實現，使用Numpy的「根」函數返回一個根數組。

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權力的統一的根源是什麼？

來源

2014-01-06 leewz

這些根是可以修復的，所以你可以用平方根表示它們。你需要所有的「2^n」根嗎？或者只是最小正角度的那個？這個小錯誤真的很糟嗎？ – Teepeemm

讓我們說是的，爲了這個問題，我需要所有的「2^k」。我們還要說，我希望數值與浮點數一樣準確。平方根的總和可能會失去準確性。 – leewz

用半角公式，也許你可以導出2 **（ - n）pi的sin和cos的精確表達式？ –

您可能喜歡圖書館Sympy。嘗試在http://live.sympy.org/

解決在控制檯統一

solve(x**5-1)

的第五根的精確解轉換爲浮點近似，做[x.evalf() for x in solve(x**5-1)]

來源

2014-01-08 01:08:15

說明明確;對sympy.solve（x ** 8-1）中的x做了x = sympy.symbols（'x'）; sympy.solve（x ** 8-1）; [abs（x.evalf（）） - ]'。我認爲使用符號數學是一樣好。 – leewz

你可以編輯這個到你的答案？ '[sympy.exp（sympy.I * 2 * sympy.pi * k/n）.evalf（）for k in range（n）]' – leewz

下面是一個遞歸算法，它通過取n/2個根和中間的點來生成n個根。如果n等於或小於4，則硬編碼結果（因爲在複平面上永遠不會找到-1和1的兩個中點）。否則，它會找到n/2根，每隔兩個連續的根，在它們的角平分線上找到一個點，並將該點縮放到單位圓。

import numpy as np 
#power of 2 roots of unity 
#computed by recursively taking the averages of the n/2 roots 
def omegas_2(n): 
    #base cases 
    if n == 1: 
     return np.array([1]) 
    if n == 2: 
     return np.array([1,-1]) 
    if n == 4: # need three points to specify the plane 
     return np.array([1,1j,-1,-1j]) 

    halfroots = omegas_2(n//2) 
    result = np.empty(n) 
    for i in range(n//2): 
     result[2*i] = halfroots[i]; 

     #take the center of the i'th and the i+1'th n/2-root 
     result[2*i+1] = (halfroots[i]+halfroots[(i+1)%(n//2)]); 
     result[2*i+1] /= abs(result[2*i+1]); #normalize to length 1 
    return result

來源

2014-01-06 16:02:54 leewz

（但是沒有更好的方法嗎？） – leewz

+1。您可以採用根的幾何平均值來避免重新縮放。但是這將涉及複雜的平方根，這可能不會更準確。 – Teepeemm

據我所知，它也比較慢。 – leewz

千里馬實現：

omegan(n):=block([ hr, hn, q, j ], 
    local(ret), 
    if n=1 then return([1]), 
    if n=2 then return([1, -1]), 
    if n=4 then return([1, %i, -1, -%i]), 
    if oddp(n) then error ("length must be power of 2; found ", n), 
    hn:fix(n/2), 
    hr: omegan(hn), 
    for i:1 thru hn do (
     ret[2*i]:hr[i], 
     j: if i+1>hn then i+1-hn else i+1, 
     q:hr[i]+hr[j],   
     ret[2*i+1]:rectform(q/abs(q)) 
    ), 
    listarray (ret)  
)

來源

2014-11-28 00:27:47

有人可以比較結果嗎？這將是有趣的 –

2的冪的統一的精確根源？

回答

相關問題