Determining the inverse function operation from a function definition

Hi.
I am working on a small project to evaluate and execute unit conversion
expressions. I started wondering whether it was possible  to determine what
the reverse conversion rules might blook like.

For example, one might want to define the classic Celsius to Fahrenheit
convesrion expression along the lines of:

F(  c  ) = ( 9 / 5 ) * c  + 32.

It seems as though there's enough information there  to deduce the inverse
Fahrenheit  to Celsius conversion:

C(  f  ) =  ( f  -  32 )  /  ( 5 / 9 )


It "feels" as though the inverse operation could be accomplished by
backing-out the original operation steps in reverse order, but it appears
that such an approach could also be fraught with peril.

The problem appears to lie in the domain of ( one to one )  function
inversion or maybe equation solving.

I presume that such an algorithm has been implemented a hundred or so times,
but my research is coming up dry.

I'd appreciate it if someone could point me to some relevant material.

TIA

"Ron Foster" <rlfoster1@cox.net> writes:

> Hi.
> I am working on a small project to evaluate and execute unit conversion
> expressions. I started wondering whether it was possible  to determine wha
t
> the reverse conversion rules might blook like. ....

> The problem appears to lie in the domain of ( one to one )  function
> inversion or maybe equation solving.
>
> I presume that such an algorithm has been implemented a hundred or so time
s,
> but my research is coming up dry.
>
> I'd appreciate it if someone could point me to some relevant material.

Some relevant references (in alphabetical order):

@InProceedings{AbrGlu02:URAF,
Author     = {Abramov, Sergei M. and Gl{\"u}ck, Robert},
Title      = {Principles of inverse computation and the universal
resolving algorithm},
BookTitle  = {The Essence of Computation: Complexity, Analysis,
Transformation},
Editor     = {Mogensen, Torben {\AE}. and Schmidt, David and
Sudborough, I. Hal},
Publisher  = {Springer-Verlag},
Series     = LNCS # 2566,
Pages      = {269--295},
Year       = {2002}
}

@InProceedings{Dijkstra:78,
Author     = {Dijkstra, Edsger W.},
Title      = {Program inversion},
BookTitle  = {Program Construction: International Summer School},
Editor     = {Bauer, F. L. and Broy, M.},
Location   = {Marktoberdorf, Germany},
Publisher  = {Springer-Verlag},
Series     = LNCS # 69,
Pages      = {54--57},
Year       = 1978
}

@incollection{Dijkstra:book82,
author =    {Dijkstra, Edsger W.},
title =     {{EWD}671: Program Inversion},
booktitle = {Selected Writings on Computing: {A} Personal Perspective},
publisher = {Springer-Verlag},
pages =     {351--354},
year =      1982
}

@inproceedings{Eppstein:IJCAI85,
author =    {Eppstein, David},
title =     {A Heuristic Approach to Program Inversion},
booktitle = {Int.\ Joint Conference on
Artificial Intelligence (IJCAI-85)},
publisher = {Morgan Kaufmann, Inc.},
pages =     {219--221},
year =      1985,
}

@InProceedings{GlueckKawabe:04:LRinv,
AUTHOR       = {Gl{\"u}ck, Robert and Kawabe, Masahiko},
YEAR         = {2004},
TITLE        = {Derivation of deterministic inverse programs based
on {LR} parsing},
BOOKTITLE    = {Functional and Logic Programming. Proceedings},
editor       = {Kameyama, Yukiyoshi and Stuckey, Peter J.},
Location     = {Nara, Japan},
publisher    = {Springer-Verlag},
series       = LNCS # 2998,
pages        = {291--306}
}

@inbook{Gries:81:inv,
author =    {Gries, David},
title =     {The Science of Programming},
chapter =   {21 Inverting Programs},
series    = {Texts and Monographs in Computer Science},
publisher = {Springer-Verlag},
pages =     {265--274},
year =      1981
}

@InProceedings{Harrison:88,
Author     = {Harrison, P. G.},
Title      = {Function inversion},
booktitle  = PEMC,
editor     = BEJ,
Publisher  = N-H,
Pages      = {153--166},
Year       = {1988}
}

@article{HarrisonKoshnevisan:Acta92,
author =  {Harrison, P. G. and Khoshnevisan, H.},
title =   {On the Synthesis of Function Inverses},
journal = {Acta Informatica},
year =    1992,
volume =  29,
pages =   {211--239},
}

@inproceedings{Romanenko:PEPM91,
author =    {Romanenko, A. Y.},
title =     {Inversion and Metacomputation},
booktitle = {Partial Evaluation and Semantics-Based Program Manipulation, Ne
w
Haven, Connecticut (Sigplan Notices, vol. 26, no. 9, September
1991)},
year =      1991,
pages =     {12--22},
publisher = {New York:\ ACM},
}


Torben

On 26 Apr 2005 20:43:21 -0400, Ron Foster wrote:

> I am working on a small project to evaluate and execute unit conversion
> expressions. I started wondering whether it was possible  to determine wha
t
> the reverse conversion rules might blook like. ...

> The problem appears to lie in the domain of ( one to one )  function
> inversion or maybe equation solving.

It all depends on the scales. F and C are linear scales of measurements. So
to convert a value from one scale to another you need a linear function.
You can have logarithmic scales or more complex ones.

> I presume that such an algorithm has been implemented a hundred or so time
s,
> but my research is coming up dry.

> I'd appreciate it if someone could point me to some relevant material.

http://www.dmitry-kazakov.de/ada/units.htm

(it also contains a unit converter sample code)

Basically the approach is to use one scale where possible. That makes life
a lot easier, especially because it allows unit expressions evaluation.
(The pitfall is evaluation accuracy. As long as you are using
floating-point, that's is hardly an issue, but should you switch to fixed
point that would become a problem.)

Basically each scale entails a whole unit system. It is difficult to live
with that. One could say that was the reason why SI was invented. Foot,
lightyear and everything else can be represented in SI. So you just write;

1.5 * foot + 10.3 * meter  -- This is fine

and the result is evaluated in SI units. You can get its numeric equivalent
in yards or furlongs if you want to. Also the factor is not an issue.

With C and F the picture becomes more complex. As I said above they
comprise scales of shifted units. Shifted units form a group for each value
of shift. Note a group, not a field, so they cannot be multiplied to
anything but a dimensionless value:

C / s  -- Meaningless

If temperature delta was meant then it should have been

K / s

Units of different shifts cannot be added:

C + F -- Illegal, because ambiguous, what's the result's shift?

Logarithmic scales could be handled in a similar way.

For parsing infix expressions (with or without units) see:

http://www.dmitry-kazakov.de/ada/components.htm

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On Wed, 26 Apr 2005, Ron Foster wrote:

> It "feels" as though the inverse operation could be accomplished by
> backing-out the original operation steps in reverse order, but it appears
> that such an approach could also be fraught with peril.

Perhaps you could express your equations by means of matrices and invert
the latter.  It seems to me your example using Fahrenheit and Celsius
would be susceptible to such an approach.  However, I'm not a
mathematician, so I might be wrong about this.

There are probably many examples of code for inverting matrices,
but you could use mine if you like (as long as you adhere to
the conditions of the GNU General Public License).
It's in the function `Transform::inverse()' in the file
`transfor.web' at
http://savannah.gnu.org/cgi-bin/vie...ldf/Group/CWEB/

It uses the Gauss-Jordan algorithm with column pivot
search.  I've taken the algorithm from  Stoer, Josef.
_Numerische Mathematik 1_,
Achte, neu bearbeitete und erweiterte
Auflage. Springer-Verlag. Berlin 1999. ISBN 3-540-66154-9,
page 205, and adapted it to C++ for 4 x 4 matrices.  It could
easily be adapted to matrices of other sizes.

The algorithm itself is, of course, in the public domain.

Laurence Finston
http://www.gnu.org/software/3dldf/LDF.html

# It "feels" as though the inverse operation could be accomplished by
# backing-out the original operation steps in reverse order, but it appears
# that such an approach could also be fraught with peril.

Function inversion is simple in affine functions, after dealing with
issues like f(x)=0.  The problem for these kinds of functions is
equivalent to inverting a matrix, which may or may not be singular. If
the function is not affine but is differentiable, then it is locally
affine; you can see if you can invert the differential matrix. Again
be aware of potential singularities.

Prolog does symbolic inversion on some functions.

Some function inversions are thought to be inherently difficult;
cryptography is based on this assumption. For example DES is an
invertible function that is intentionally hard to invert.

# I'd appreciate it if someone could point me to some relevant material.

http://www.google.com/search?rls=en...ction+inversion
Results 1 - 10 of about 1,370,000 for function inversion. (0.35 seconds)

--
SM Ryan http://www.rawbw.com/~wyrmwif/
OOOOOOOOOO! NAVY SEALS!

Ron Foster wrote:
>
> Hi.
> I am working on a small project to evaluate and execute unit conversion
> expressions. I started wondering whether it was possible  to determine wha
t
> the reverse conversion rules might blook like.
>
> For example, one might want to define the classic Celsius to Fahrenheit
> convesrion expression along the lines of:
>
> F(  c  ) = ( 9 / 5 ) * c  + 32.
>
> It seems as though there's enough information there  to deduce the inverse
> Fahrenheit  to Celsius conversion:
>
> C(  f  ) =  ( f  -  32 )  /  ( 5 / 9 )

Using my school math the result should read:
C(  f  ) =  ( f  -  32 )  /  ( 9 / 5 )

You can build an expression tree and implement a transformation
procedure for the reverse expression. Using an appropriate language
with built-in list manipulation will simplify things a lot. I remember
one of my first LISP exercises, a conversion from/to RPN...

Things will become a bit more complicated with exponentiation, sine,
or other non-linear functions, which may require more complex
transformations.

IMO you better ask your questions in a math group. Even if your problem
is related to "symbol manipulation" or "transformation", it's not a
matter of compilers nor grammars.

DoDi

Dr. Diettrich wrote:

(snip)

> Things will become a bit more complicated with exponentiation, sine,
> or other non-linear functions, which may require more complex
> transformations.

Well, there are log() and arcsin() for those cases...

> IMO you better ask your questions in a math group. Even if your problem
> is related to "symbol manipulation" or "transformation", it's not a
> matter of compilers nor grammars.

There are two questions.  One how to actually do the transformation,
and that should belong to a different group.  Mathematica being one of
the more popular symbolic math programs, you might look at that.

The problem of parsing mathematical expressions is still there, and
should still be appropriate here.  As one example, operator precedence
still exists in symbolic math.

-- glen

SM Ryan  <wyrmwif@tsoft.org> wrote:
>
>Some function inversions are thought to be inherently difficult;
>cryptography is based on this assumption. For example DES is an
>invertible function that is intentionally hard to invert.

Yes.  One then gets onto the interesting difference of whether a
function has an efficient inverse and whether there is an efficient
method of find one of its better inverses.  And, in both cases, the
state can be yes, no or unknown.


Regards,
Nick Maclaren.

Ron Foster wrote:
>
> Hi.
> I am working on a small project to evaluate and execute unit conversion
> expressions. I started wondering whether it was possible  to determine wha
t
> the reverse conversion rules might blook like.
>
> For example, one might want to define the classic Celsius to Fahrenheit
> convesrion expression along the lines of:
>
> F(  c  ) = ( 9 / 5 ) * c  + 32.
>
> It seems as though there's enough information there  to deduce the inverse
> Fahrenheit  to Celsius conversion:
>
> C(  f  ) =  ( f  -  32 )  /  ( 5 / 9 )

You did a bit too much, using my school math the result should read:
C(  f  ) =  ( f  -  32 )  /  ( 9 / 5 )

There should't exist too many linear conversion formulas, so a table
with the constants and the two conversion functions should be feasable.
Perhaps all you need is y=a*x+b and y=a/x+b, with the according inverse
functions. Things will become a bit more complicated with
exponentiation, sine, or other non-linear functions.

In the general case you can build an expression tree and implement a
transformation procedure for the reverse expression. Using an
appropriate language with built-in list manipulation will simplify
things a lot. I remember one of my first LISP exercises, a conversion
from/to RPN...

IMO you better ask your questions in a math group. Even if your problem
is related to "symbol manipulation" or "transformation", it's not a
matter of compilers nor grammars.

DoDi