Как точно вычислить sin (2 * m * Pi / n) с помощью CGAL и CORE?
Используя полиномы Чебышева, мы можем точно вычислить sin (2 * Pi / n), используя библиотеки CGAL и CORE, как в следующем фрагменте кода:
#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 являются целыми числами, какую формулу полинома мне следует использовать? Благодарю.
Решение
(Частичное решение.)
По сути, это вычисление действительной и мнимой части корней единства как алгебраических чисел. Обозначим 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) + con (w (m)) и что комплексные корни En входят в сопряженные пары; следовательно, также con (w (m)) является корнем En. Теперь, грубо говоря, часть En (y) «ограничивает» y любым (сложным) корнем En, и объединение этого с первым аргументом позволяет x принимать любое комплексное значение, такое, что x-y также является корнем En. Следовательно, возможное присваивание это y = con (w (m)) и x-y = w (m), следовательно, x = w (m) + con (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) имеет все значения 2 * Re (w (m)) для m! = N / 4, 3 * н / 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
с (6, х) = х ^ 4 — 5 * х ^ 2 + 4
s (7, x) = x ^ 4 — x ^ 3 — 4 * x ^ 2 + 3 * x + 2
с (8, х) = х ^ 4 — 6 * х ^ 2 + 8
s (n, x) = (x ^ 2-2) * s (n-4, x) — s (n-8, x)
В ожидании доказательства …
Другие решения
Других решений пока нет …