3

使用切比雪夫多项式，我们可以使用 CGAL 和 CORE 库精确计算 sin(2*Pi/n)，如下面的代码：

#include <CGAL/CORE_Expr.h>
#include <CGAL/Polynomial.h>
#include <CGAL/number_utils.h>
//return sin(theta) and cos(theta) for theta = 2pi/n
static std::pair<AA, AA> sin_cos(unsigned short n) {
    // We actually use -x instead of x since root_of will give the k-th
    // smallest root but we want the second largest one without counting.
    Polynomial x(CGAL::shift(Polynomial(-1), 1));
    Polynomial twox(2*x);
    Polynomial a(1), b(x);
    for (unsigned short i = 2; i <= n; ++i) {
        Polynomial c = twox*b - a;
        a = b;
        b = c;
     }
     a = b - 1;
     AA cos = -CGAL::root_of(2, a.begin(), a.end());
     AA sin = CGAL::sqrt(AA(1) - cos*cos);
     return std::make_pair(sin, cos);
}

但是，如果我想精确计算 sin(2*m*Pi/n)，其中 m 和 n 是整数，我应该使用的多项式公式是什么？谢谢。

4

1 回答 1

2

（部分解决方案。）

这实质上是将单位根的实部和虚部计算为代数数。让我们表示 w(m) = exp(2*pi*I*m/n)。那么，w(m) 本身就是 En(x) = x^n-1 的复根。

您需要找到 Re(w(m)) 的定义多项式。结果是找到这样一个多项式的工具：2*Re(w(m)) 是 Res (En(xy), En(y); y) 的根。
要解释为什么会这样：请注意 2*Re(w(m)) = w(m) + conj(w(m))，并且 En 的复根以共轭对形式出现；因此，conj(w(m)) 也是 En 的根。现在松散地说，En(y) 部分“约束” y 为 En 的任何（复）根，并将其与第一个参数结合允许 x 采用任何复值，使得 xy 也是 En 的根。因此，可能的赋值是 y = conj(w(m)) 和 xy = w(m)，因此 x = w(m)+conj(w(m)) = 2*Re(w(m))。
CGAL 可以计算多元多项式的结果，所以你可以计算这个结果，你只需要选择正确的实根。（最大的显然是 w(0) = 1，最小的是 2*Re(w(floor(n/2)))。）

不幸的是，结果的复杂度很高（n^2 度），结果计算不会是你见过的最快的运算。此外，尽管您的实例非常稀疏且结构化，但您将为密集多项式付费。YMMV；我不知道你的用例，如果你需要更高的学位。
然而，我在计算机代数系统中做了一些测试，我发现结果分裂成更合理大小的因子，并且它的所有实根实际上都属于一个更简单的次数 floor(n/2)+1 多项式只要。（没有证据，只是观察。）
我不知道写下这个因素的直接公式，我不想推测它。但也许 mathoverflow 或 math.stackexchange 的一些人可以提供帮助？

编辑：这是对至少一个递归公式的猜测。
我将 s(n,x) 写成包含除 0 之外的所有实根的合成多项式的重要因子。这意味着 s(n,x) 对于 m != n/ 具有所有值 2*Re(w(m)) 4, 3*n/4 作为根。

s(0,x) = 0
s(1,x) = x - 2
s(2,x) = x^2 - 4
s(3,x) = x^2 - x - 2
s(4,x) = x^2 - 4
s(5,x) = x^3 - x^2 - 3*x + 2
s(6,x) = x^4 - 5*x^2 + 4
s(7,x) = x^4 - x^3 - 4*x^2 + 3*x + 2
s(8,x) = x^4 - 6*x^2 + 8

s(n,x) = (x^2- 2)*s(n-4,x) - s(n-8,x)

等待证明...

于 2014-04-15T17:36:25.957 回答