This problem has an intriguing history, even if we restrict it to the task of inverting an Excel formula...
Mathematicians will say (without putting their brains in gear) that an expression defines a function, and that there's a vast literature on inverses. Ergo, problem solved. (Mostly). Alas no one in Microsoft has applied the available theory systematically to inverting formulas. Although there is a function in trend analysis called hill-climbing. A planner in IBM Cosham called George Kunzle invented an Excel-like grid which would actually invert any formula you could type into it. Some of these formulae actually used IF/THEN/ELSE! Thus, you could overtype the "formula cell" with a different value, and the inputs would be adjusted to compute this value, instead of losing the formula, which is what happens in today's Excel. Yes, the backfit wasn't always unique. But the package offered a single solution, calculated on a "rational basis". In practice this solves most requirements you'd care to place on it, which blows some mathematicians' eyebrows off, who claim it isn't (generally) possible. The result was marketed as Adaytum Planning (AP) which swiftly became popular in planning circles. The algorithm used to "invert" any formula was called "break-back" and was proprietary. You could implement a 10% cut across an enterprise by typing a 90% value into the bottom right hand corner of an immensely complex balance sheet and: hey presto: the cut broken down to fine detail. Since many companies wanted to do just that, the recession benefitted Adaytum just like a plague benefits an undertaker, and its value soared. Adaytum was eventually bought by Cognos Corp, with about 700% gain to its (private) shareholders. However far more would have been made had the company gone public, as it was all set to when the Internet Bubble burst in 2000. Cognos has since been bought by IBM, which has thus re-purchased its old (banished) Cinderella. I worked on the break-back algorithm (which was pretty klunky and ad-hoc!), and offered Adaytum an alternative which I considered more analytically rational (though not fully worked out theoretically). Since this algorithm is my own I haven't seen any reason not to popularise it, which I have done in TABULA: http://www.jsoftware.com/jwiki/IanClark/TABULA (There are still outstanding problems of a theoretical nature, I ought to admit, so until I've solved them I'm not pushing it overmuch.) My method used Newton-Raphson, which is a bit of a cheat. However the Kunzle algorithm precisely inverts each operator offered to the user to compose a formula, and so corresponds more closely to algorithm inversion as you postulate. It can do some pretty smart things, including breaking-back multiple simultaneous changes. Many J primitives have "inverses" and these would seem to me a good basis for re-implementing (rediscovering?) Kunzle's invention. I've not had time to look closely into that, however. The story continues... On Mon, Feb 21, 2011 at 6:16 AM, Steven Taylor <[email protected]> wrote: > Hi, > > Just sharing a thought. > > I was flicking through this old text book "The Science Of Programming" by > David Gries (1981), while thinking that it was one of the few I remembered > -- it made an impression on me. > > Here's a quote: "Wouldn't it be nice to be able to run a program backwards > or, better yet, to derive from one program P a second program P-1 that > computes the inverse of P? That means that running followed by P-1 would be > the same as not running any program at all! Also, if we had the result of > executing P, but had lost the input, we could execute P-1 to determine that > input. " > > -Steven > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
