Re: complexity function for computer code

• To: mathgroup at smc.vnet.net
• Subject: [mg14954] Re: [mg14900] complexity function for computer code
• From: hanssen at zeiss.de
• Date: Fri, 27 Nov 1998 03:49:51 -0500
• Sender: owner-wri-mathgroup at wolfram.com

Hi, Topher

There is a package Optimize.m in MathSource (indeed, there are two
versions of it). These packages try to optimize the computation, by
assigning variables for intermediate results.  The output is not
optimum, but it is a good starting point for further manual
optimization.

One problem is, that e.g. if an expression has x^2 somewhere in the
numerator and also in the denominator, it assigns an o-variable to x^2,
another one to x^(-2). Also some other "obvious optimizations" are not
done automaticly. But anyway, the package relieves one from the stupid
simple work.

Also, one can easily play around, trying to feed it with Factor-ed,
Expand-ed Together-ed or in other ways manually preprocessed
subexpressions of what one is dealing with. Looking at optimize's
output easily shows, if one or the other trial yields "faster"
computations.

In the comment-header if the package, it says, the oputput is not
guaranteed to be the numerical optimum. An educated look at the result
is still necessary.

One of the abovementioned Optimize packages gives rules, e.g. {o1->x+y,
o2->x*y, o3->o1*o2/(o1+o2)}, the other one gives assignments. As I was
using
the output to write "C"-programs, I used an editor and "search/replace"
to generate the final result, it did not matter, if I had to replace
"->" by "=".

A nice trick was, to let Optimize work on more than one expression at
once (e.g. a function and some partial derivatives of it, which by
nature have similar subexpressions in them).

One other trick is, to read the final result of manually optimizing back
into Mathematica and check, if the manual operations were done right or
have introduced any error.  Expand the to be optimized expressions and
subtract Expand of the manually optimized result.

Happy optimizing (and if you improve the package or hear from an
improved version, let us know about it).