Access Restriction

Author Muller, David E. ♦ Preparata, Franco P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1976
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let $\textit{E}$ be an arithmetic expression involving $\textit{n}$ variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 $log2\textit{n}$ + 1 and 2.08 $log2\textit{n}$ for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log2α ≈ 2.88 and $1/log2\textit{β}$ ≈ 2.08, where $\textit{α}$ and $\textit{β}$ are the positive real roots of the equations $\textit{z}2$ = $\textit{z}$ + 1 and $\textit{z}4$ = $2\textit{z}$ + 1, respectively. While these times were known to be of order $log2\textit{n},$ the best previously known coefficients were 4 and 2.15 for the two cases.The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.The paper also gives upper bounds to the restructuring time of a given expression $\textit{E}$ and to the number of processors required for its parallel evaluation. It is shown that at most $\textit{O}\textit{(n}1.44\textit{)}$ and $\textit{O}(n1.82\textit{)}$ operations are needed for restructuring general expressions and division-free expression, respectively. It is pointed out that, since the order of the compiling time is greater than $\textit{n}$ log $\textit{n},$ the numbers of required processors exhibit the same rate of growth in $\textit{n}$ as the corresponding compiling times.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1976-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 23
Issue Number 3
Page Count 10
Starting Page 534
Ending Page 543

Open content in new tab

   Open content in new tab
Source: ACM Digital Library