Complexities of Graph-Based Representations for Elementary Functions
| Autor: | Shinobu Nagayama, Tsutomu Sasao |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Polynomial Complex-valued function elementary functions Mp-monotone increasing functions Decision diagrams kth-degree polynomial functions Addition theorem μ-recursive function Theoretical Computer Science Algebra BMDs Monotone polygon Computational Theory and Mathematics Hardware and Architecture Elementary function MTBDDs EVBDDs Boolean function Software Mathematics Variable (mathematics) |
| Zdroj: | IEEE Transactions on Computers. 58:106-119 |
| ISSN: | 0018-9340 |
| DOI: | 10.1109/tc.2008.134 |
| Popis: | This paper analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|