c++ - 如何使用 CGAL 和 CORE 精确计算 sin(2*m*Pi/n)？

Question

使用 Chebyshev 多项式，我们可以使用 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 是整数，我应该使用的多项式公式是什么？谢谢。

Answer 1

(部分解决方案。)

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

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

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

编辑:这是对至少一个递归公式的猜测。
我将 s(n,x) 写为包含除 0 之外的所有实根的结果多项式的重要因子。这意味着 s(n,x) 的所有值为 2*Re(w(m)) for m != n/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)

等待证明...