MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

complexity function for computer code

  • To: mathgroup at
  • Subject: [mg14900] complexity function for computer code
  • From: Topher Cawlfield <cawlfiel at>
  • Date: Wed, 25 Nov 1998 17:48:21 -0500
  • Organization: University of Illinois at Champaign-Urbana
  • Sender: owner-wri-mathgroup at


I'm working on trying to simplify an ugly expression using Mathematica,
and could use some help.  I'm trying to use Mathematica to optimize a
small piece of code that does a lot of number crunching.  With
Mathematica I can put together the desired expression, and then use
Simplify and FortranForm to get efficient code.  Well, sort of.  My
first problem is that Simplify takes too long to work.  For all I know,
it might even take longer than the age of the universe.  My second
problem is that even if I could get Simplify to do its job in a day or
two, it most likely would not give me an expression that required
minimal CPU time to evaluate.

After some thinking, the correct way to do this is to write a
"complexity function" that Simplify can use, which accurately
represents the computation time to evaluate the expression. 
Multiplication is more time consuming than addition, for example
(though by how much greatly depends on the architecture).  Square roots
take even longer.  This complexity function should also recognize any
subexpressions in the commplete expression which are duplicates of
eachother.  These subexpressions could be calculated and stored into an
intermediate variable.  So any duplicate sub-expressions do not add to
the "complexity".

Assuming I can come up with such a complexity function and can perform
the simplification in less than roughly 10^6 seconds (could be a
problem), then I only need to have some Mathematica program that
identifies the duplicate sub-expressions, substitutes them for a
variable, recursively, and eventually writes my multi-line program for
me (in Fortran :-( or whatever).

So my question is:  Has anyone else done this before?  It seems like
this kind of procedure would be very useful in general.  The most
relevant package I could find that addresses some of these issues is
HeuristicSearch from MathSource.  Where else should I look?

 - Topher Cawlfield

  • Prev by Date: Many data points = frustration
  • Next by Date: Re: PlotLabel question
  • Previous by thread: Re: Way to evaluate D[(1-x^2)y''[x],{x,n}] ?
  • Next by thread: Re: complexity function for computer code