Finding the «truncated» polynomial that is closest to a function - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2003

Finding the «truncated» polynomial that is closest to a function

Abstract

When implementing regular enough functions (e.g., elementary or special functions) on a computing system, we frequently use polynomial approximations. 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 method for finding the best polynomial approximation under this constraint.
Lorsque l’on implante des fonctions suffisamment régulières (par exemple des fonctions élémentaires ou spéciales) dans un système de calcul, on utilise souvent des approximations polynomiales. La plupart du temps, le polynôme qui approche le mieux (pour une distance et dans un intervalle donnés) une fonction a des coefficients qui ne sont pas représentables sur un nombre fini de bits. Cependant, les approximations polynomiales utilisées en pratique ont des coefficients écrits sur un nombre fini – souvent petit – de bits : ceci est dû à la finitude des représentations virgule flottante (pour les implantations logicielles) et au besoin d’avoir des circuits multiplieurs de petite taille, donc rapides et/ou peu coûteux (pour les implantations matérielles). Nous devons donc considérer des approximations polynomiales dont le ième coefficient a au plus mi bits fractionnaires (autrement dit, est un nombre rationnel de dé-nominateur2mi). Nous proposons une méthode permettant d’obtenir le polynôme de meilleure approximation d’une fonction sous cette contrainte
Fichier principal
Vignette du fichier
RR-4787.pdf (176.66 Ko) Télécharger le fichier
RR2003-21.pdf (254.58 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00071799 , version 1 (23-05-2006)

Identifiers

  • HAL Id : inria-00071799 , version 1

Cite

Nicolas Brisebarre, Jean-Michel Muller. Finding the «truncated» polynomial that is closest to a function. [Research Report] RR-4787, LIP RR-2003-21, INRIA, LIP. 2003. ⟨inria-00071799⟩
130 View
373 Download

Share

Gmail Facebook Twitter LinkedIn More