HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01200820
Contributor : Fabrice Rouillier Connect in order to contact the contributor
Submitted on : Thursday, September 17, 2015 - 11:48:46 AM
Last modification on : Friday, January 21, 2022 - 3:22:14 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

139