DIMACS TR: 93-07
On Computing Algebraic Functions Using Logarithms and Exponentials
Authors: Dina Grigoriev, Michael Singer, and Andrew Yao
ABSTRACT
Let f be a set of algebraic expressions constructed
with radicals and arithmetic operations, and which generate
the splitting field F of some polynomial. Let N_b(f) be the
minimum total number of root-takings and exponentiations used
in any straightline program for computing the functions in f by
taking roots, exponentials, logarithms, and performing arithmetic
operations. In this paper it is proved that N_b(f) = g(G), where
g(G) is the minimum length of any cyclic Jordan-Hoelder tower
for the Galois group G of F. This generalizes a result of Ja'Ja' [1],
and shows that the inclusion of certain new primitives, such
as taking exponentials and logarithms, does not improve the cost
of computing such expressions as compared with programs which use
only root-takings.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-07.ps
DIMACS Home Page