On the number of segments needed in a piecewise linear approximation

✍ Scribed by C.L. Frenzen; Tsutomu Sasao; Jon T. Butler

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 526 KB
• Volume: 234
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2009.12.035

✦ Synopsis

The introduction of high-speed circuits to realize an arithmetic function f as a piecewise linear approximation has created a need to understand how the number of segments depends on the interval a ≤ x ≤ b and the desired approximation error ε. For the case of optimum non-uniform segments, we show that the number of segments is given as

Experimental data shows that this approximation is close to the exact number of segments for a set of 14 benchmark functions. We also show that, if the segments have the same width (to reduce circuit complexity), then the number of segments is given by s(ε) ∼ c √ ε , (ε → 0 + ), where c = (b-a) √ |f |max 4 .