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

Nicolas Brisebarre 1 Jean-Michel Muller 2
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071799
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:49:58 PM
Last modification on : Thursday, May 16, 2019 - 10:21:06 AM

Identifiers

  • HAL Id : inria-00071799, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

232

Files downloads

433