On the sign of a trigonometric expression

Abstract : We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form $F=\sum_{k=0}^df_k\cos k\frac{\pi}{n}$, $f_k\in\ZZ$, $d0}$: computing the sign of such an expression, evaluating it numerically and computing its minimal polynomial in $\QQ[x]$. As critical byproducts, we propose simple and efficient algorithms for performing arithmetic operations (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis) and for computing the minimal polynomial of $2 \cos \frac{\pi}{n}$ in $\tcO(n_0^2)$ bit operations with $n_0 \leq n$ is the odd squarefree part of $n$. Within such a framework, we can decide if $F=0$ in $\tcO(d(\tau+d))$ bit operations, compute the sign of $F$ in $\tcO(d^2\tau)$ bit operations and compute the minimal polynomial of $F$ in $\tcO(n^3\tau)$ bit operations, where $\tau$ denotes the maximum bitsize of the $f_k$'s.
Keywords :
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01200820
Contributor : Fabrice Rouillier <>
Submitted on : Thursday, September 17, 2015 - 11:48:46 AM
Last modification on : Friday, April 10, 2020 - 5:23:05 PM

Citation

Pierre-Vincent Koseleff, Fabrice Rouillier, Cuong Tran. On the sign of a trigonometric expression. ISSAC ' 15, Jul 2015, Bath, United Kingdom. ⟨10.1145/2755996.2756664⟩. ⟨hal-01200820⟩

Record views