On the sign of a trigonometric expression

Abstract : We propose a set of simple and fast algorithms for evalu-ating and using trigonometric expressions in the form F = d k=0 f k cos k π n , f k ∈ Q, d < n for a fixed n ∈ Z>0: comput-ing the sign of such an expression, evaluating it numerically and computing its minimal polynomial in Q[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 than in the monomial basis) and for computing the minimal polynomial of 2 cos π n in O(n 2 0) bit operations with n0 < n is the odd squarefree part of n. Within such a framework, we can decide if F = 0 in O(d(τ +d)) bit operations , compute the sign of F in O(d 2 τ) bit operations and compute the minimal polynomial of F in O(n 3 τ) bit operations, where τ denotes the maximum bit-size of the f k 's.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01108656
Contributeur : Fabrice Rouillier <>
Soumis le : mercredi 28 janvier 2015 - 11:29:20
Dernière modification le : mardi 17 avril 2018 - 11:23:55
Document(s) archivé(s) le : mercredi 29 avril 2015 - 10:10:25

Fichier

KRT-1-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01108656, version 1

Collections

UPMC | INRIA | USPC | IMJ

Citation

Pierre-Vincent Koseleff, Fabrice Rouillier, Cuong Tran. On the sign of a trigonometric expression. 2015. 〈hal-01108656〉

Partager

Métriques

Consultations de la notice

441

Téléchargements de fichiers

133