On the Generation of Precise Fixed-Point Expressions

摘要: Several problems in the implementations of control systems, signal-processing and scientific computing systems reduce to compiling a polynomial expression over reals into an imperative program using fixed-point arithmetic. Fixed-point arithmetic only approximates real values, its operators do not have fundamental properties arithmetic, such as associativity. Consequently, naive compilation process can yield that significantly deviates from polynomial, whereas different order evaluation result is close value on all inputs domain. We present scheme for real-valued expressions programs. Given t, we find t' equivalent t reals, but whose implementation series operations minimizes error between space inputs. show corresponding decision problem, checking whether there less than given constant, NP-hard. then propose solution technique based genetic programming. Our evaluates fitness each candidate static analysis affine our tool set linear system benchmarks. For example, found errors are one half original expressions.