complexity function for computer code

*To*: mathgroup at smc.vnet.net*Subject*: [mg14900] complexity function for computer code*From*: Topher Cawlfield <cawlfiel at uiuc.edu>*Date*: Wed, 25 Nov 1998 17:48:21 -0500*Organization*: University of Illinois at Champaign-Urbana*Sender*: owner-wri-mathgroup at wolfram.com

Hi, 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