问如何用CGAL和CORE精确计算sin(2mPi/n)？
EN

Stack Overflow用户

提问于 2014-04-14 23:41:04

回答 1查看 410关注 0票数 3

使用Chebyshev多项式，我们可以使用CGAL和核心库精确计算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是整数，我应该使用的多项式的公式是什么？谢谢。

c++

cgal

polynomials

音视频低代码开发方案最快1天上线

推出 TUICallKit 和 TUIRoomKit 低代码集成方案，最快1天接入在线教育、语聊房、在线客服等应用

回答 1

Stack Overflow用户

发布于 2014-04-15 17:36:26

(部分解决方案。)

这本质上是计算单位根的实部和虚部作为代数数字。让我们表示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))。

CGAL可以计算多元多项式的结式，所以你可以计算这个结式，你只需要选择正确的实根。(最大的显然是w(0) = 1，最小的是2*Re(w(floor(n/2)。)

不幸的是，结果具有很高的复杂度(n^2级)，并且结果计算不会是您见过的最快的操作。此外，尽管您的实例非常稀疏和结构化，但您将为密集多项式买单。YMMV；我对你的用例一无所知，如果你需要更高的学位。

然而，我在一个计算机代数系统中做了一些测试，我发现结果分裂成更合理大小的因子，并且它的所有实根实际上只属于一个更简单的次数下限(n/2)+1的多项式。(没有证据，只是观察。)

我不知道一个直接的公式来写下这个因子，我也不想去猜测它。但也许mathoverflow或math.stackexchange的一些人可以提供帮助？

编辑:以下是至少一个递归公式的猜测。

我写s(n，x)表示包含除0之外的所有实根的合成多项式的有效因子。这意味着s(n，x)以m != n/4，3*n/4的所有值2*Re(w(m))为根。

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