Computing machine-efficient polynomial approximations

Jean-Michel Muller 1, 2 Nicolas Brisebarre 3 Arnaud Tisserand 4
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits: in other words, it is a rational number with denominator $2^{m_i}$. We provide a general and efficient method for finding the best polynomial approximation under this constraint. Moreover, our method also applies if some other constraints (such as requiring some coefficients to be equal to some predefined constants, or minimizing relative error instead of absolute error) are required.
Type de document :
Article dans une revue
ACM Transactions on Mathematical Software, Association for Computing Machinery, 2006, 32 (2), pp.236-256. 〈10.1145/1141885.1141890〉
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00086826
Contributeur : Jean-Michel Muller <>
Soumis le : jeudi 20 juillet 2006 - 08:14:53
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:19:01

Identifiants

Citation

Jean-Michel Muller, Nicolas Brisebarre, Arnaud Tisserand. Computing machine-efficient polynomial approximations. ACM Transactions on Mathematical Software, Association for Computing Machinery, 2006, 32 (2), pp.236-256. 〈10.1145/1141885.1141890〉. 〈ensl-00086826〉

Partager

Métriques

Consultations de la notice

380

Téléchargements de fichiers

838