What-if algorithm

[gamo]

In excel you have a menu function that consist of given one
cell input and one cell output no matter how are related one
to other, you could search for the input that correspond to
a given value of the output.

That is, if I set $input and have a (complicated)
$output = f ( $input );
I can search in the reverse direction for a solution to
$output = XXX;

Do you know the subyacent algorithm or module to cover this?
TIA

 

[Scott Bryce]

In excel you have a menu function that consist of given one cell
input and one cell output no matter how are related one to other, you
could search for the input that correspond to a given value of the
output.

That is, if I set $input and have a (complicated) $output = f (
$input ); I can search in the reverse direction for a solution to
$output = XXX;

Do you know the subyacent algorithm or module to cover this?

If I understand your question correctly, this will not always be
possible. There may be more than 1 input to the function that will give
a particular result.

3 = |x|

What is x? Do you want both solutions, or is there some way to specify
which solution is preferred?

 

[Jürgen Exner]

In excel you have a menu function that consist of given one
cell input and one cell output no matter how are related one
to other, you could search for the input that correspond to
a given value of the output.

That is, if I set $input and have a (complicated)
$output = f ( $input );
I can search in the reverse direction for a solution to
$output = XXX;

Do you know the subyacent algorithm or module to cover this?

Because in the general case it is impossible to create the reverse
function f^-1 (it may not even exist) the only way is to enumerate and
loop over all $input values and compare the results to the desired
output value.
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

jue

jue

 

[ccc31807]

In excel you have a menu function that consist of given one
cell input and one cell output no matter how are related one
to other, you could search for the input that correspond to
a given value of the output.

I know a pretty good bit about Excel, and your question makes no sense
to me. If you are talking about a function from the function box, you
can always backtrace the input. This is a basic functionality of any
spreadsheet program. Not only can you trace function inputs and
outputs, you can see the formulas using the reveal key (Ctl-`).

That is, if I set $input and have a (complicated)
$output = f ( $input );
I can search in the reverse direction for a solution to
$output = XXX;

Yeah, well, this is what Excel does. You can go backwards and forwards
from any point.

Do you know the subyacent algorithm or module to cover this?

In Excel or Perl? In programming languages you can't always reproduce
the input if you know the output and the function, as in a hash
function where the original value that's hashed can't be calculated
without an enormous effort.

If you are asking about a way to reverse engineer a function or a
script, you may not find much help here. If you are asking about a
particular function or script, it might help to post the code and the
output.

CC

 

[gamo]

Because in the general case it is impossible to create the reverse
function f^-1 (it may not even exist) the only way is to enumerate and
loop over all $input values and compare the results to the desired
output value.
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

jue

Thanks, that's what I was asking. I agree that the problem could
be impossible. But there are methods better than random search
or brute force to generate the candidates. That sistematic search
is what I want to know.

Best regards,

 

[Peter J. Holzer]

Because in the general case it is impossible to create the reverse
function f^-1 (it may not even exist) the only way is to enumerate and
loop over all $input values and compare the results to the desired
output value.
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

That may be a bit impractical if @candidates is the set of all floating
point numbers.

However, for differentiable functions you can use Newton's method
if you start with an estimate which is "close enough".

(I guess this is what Excel does)

hp

 

[gamo]

That may be a bit impractical if @candidates is the set of all floating
point numbers.

However, for differentiable functions you can use Newton's method
if you start with an estimate which is "close enough".

(I guess this is what Excel does)

hp

I don't know. I see the work of

/*
* goal-seek.c: A generic root finder.
*
* Author:
* Morten Welinder ([email protected])
*
*/

included in gnumeric-1.8.3 source.

But I'm unable to discern if root-finding methods are aplicable
to the generic case of non-continous, non-derivable functions.

Best regards,

 

[Xho Jingleheimerschmidt]

In excel you have a menu function that consist of given one
cell input and one cell output no matter how are related one
to other, you could search for the input that correspond to
a given value of the output.

You should probably tell us what that "menu function" is called.
It sounds like either "goal seek" or the add-in "solver". You want some
kind of numeric solver or function minimizer. There are all kinds of
them out there, simplex, Levenberg Marquidt, steepest descent, Newtons
method, conjugate gradient, etc. that have different areas of expertise.
You can find several in "Numerical Recipes in C", for example. I
haven't seen CPAN implementations of these in Perl that I liked.

Xho

 

[sln]

Thanks, that's what I was asking. I agree that the problem could
be impossible. But there are methods better than random search
or brute force to generate the candidates. That sistematic search
is what I want to know.

Best regards,

Linear equations can be solved directly

y = x - 1;
x = y + 1

Single term polynomial's can be solved directly

y = x**2 - 16
x = sqrt(y+16) or (y+16) to the power of 1/n for roots

Multiple term polynomial, for a given y, x cannot be solved directly.
One equation, one unknown (given y), but multiple terms.

y = x**2 + 2*x + 1
y = x(x + 2) + 1
x(x+2) = y-1
x = (y-1)/(x+2)

Here an itteration is required on each given y. If it converges
there is a single solution if y is not 0 where there are two.
And X will probably end up being a non-whole number.

---------------------------
y = some value (constant);
diff = 1;
cnt = 0
Xold = Xnew = 1;
while ( fabs (diff) > .01 && cnt < 20)
{
Xnew = x = (y-1)/(Xold+2);
++cnt;
dif = Xnew - Xold;
}
printf ("count = %d, diff = %d, Xnew = %d\n", cnt, diff, Xnew);
-----------------------------

So when an itteration is required, it could happen that an exact solution is
found quickly, within 7-20 itterations.

If you don't plan to do itterations, some things to think about when your
just guessing trying to solve it, which by the way, is totally illogical.

However it is likely that the solution will be a non-whole number so
@results = grep (f($_) == XXX, @candidates
^^
this would not be reasonable

You would want to get the results of f($_) and compare it to within +/- some percentage
of XXX in range. Or round to a whole number at least. You could flag multiple candidates
that are close to the solution. But, its still not the solution because its a blind,
directionless series of calculations that don't even constitute an itteration.

-sln

 

[sln]

[snip]

Here an itteration is required on each given y. If it converges
there is a single solution if y is not 0 where there are two.
And X will probably end up being a non-whole number.

---------------------------
y = some value (constant);
diff = 1;
cnt = 0
Xold = Xnew = 1;
while ( fabs (diff) > .01 && cnt < 20)
{
Xnew = x = (y-1)/(Xold+2);
++cnt;
dif = Xnew - Xold; Xold = Xnew;
}
printf ("count = %d, diff = %d, Xnew = %d\n", cnt, diff, Xnew);
-----------------------------

-sln

 

[sln]

On Tue, 3 Mar 2009, Jürgen Exner wrote:

[snip]

Here an itteration is required on each given y. If it converges
there is a single solution if y is not 0 where there are two.
And X will probably end up being a non-whole number.

---------------------------
y = some value (constant);
diff = 1;
cnt = 0
Xold = Xnew = 1;
while ( fabs (diff) > .01 && cnt < 20)
{ Xnew = (y-1)/(Xold+2);
++cnt;
dif = Xnew - Xold; Xold = Xnew;
}
printf ("count = %d, diff = %d, Xnew = %d\n", cnt, diff, Xnew);
-----------------------------

 

[Jürgen Exner]

In excel you have a menu function that consist of given one

[...]
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

That may be a bit impractical if @candidates is the set of all floating
point numbers.

True, but it is highly unlikely that the set of all floating point
numbers is stored in an Excel spreadsheet.

jue

 

[gamo]

You should probably tell us what that "menu function" is called.
It sounds like either "goal seek" or the add-in "solver". You want some kind

Certainly I'm not refering to the solver. It is probably "goal seek."

of numeric solver or function minimizer. There are all kinds of them out
there, simplex, Levenberg Marquidt, steepest descent, Newtons method,
conjugate gradient, etc. that have different areas of expertise. You can find
several in "Numerical Recipes in C", for example. I haven't seen CPAN
implementations of these in Perl that I liked.

Xho

If and only if could be reduced to a root finding algorithm there is the
module Math::Function::Roots, that uses varios methods, i.e.

* bisection - Good for general purposes, you must provide a range in
which one and only one root exists. Basically a binary search for
the root.
* fixed_point - Only useful on a set of functions that can be
converted to a fixed-point function with certain properties, see
below. Fast when it can be used.
* secant - A fast converging algorithm which bases guesses on the
slope of the function. Because slope is used, areas of the function
where the slope is near horizontal (f'(x) == 0) should be avoided.

From which, I guess the bisection method it's the most general.

Best regards,

 

[gamo]

On Wed, 4 Mar 2009, gamo wrote:

The question remains open since I suspect that a mathematical
bisection doesn't fit for a goal seek problem. I.e. if max=a
& min=b the bisection method croaks if f(a)*f(b)>0 (It doesn't
garantees the Bolzano's theorem).

f() could be a function with if's max, min, abs, etc. that does
not fit well in a mathematical root-finding schema.

TIA

 

[Ted Zlatanov]

g> But I'm unable to discern if root-finding methods are aplicable
g> to the generic case of non-continous, non-derivable functions.

Look at glpk, http://www.gnu.org/software/glpk/

Depending on your particular data it may be useful; at least you can
learn about the methods it uses to solve a LP problem.

Ted

 

[Ted Zlatanov]

g> But I'm unable to discern if root-finding methods are aplicable
g> to the generic case of non-continous, non-derivable functions.

TZ> Look at glpk, http://www.gnu.org/software/glpk/

TZ> Depending on your particular data it may be useful; at least you can
TZ> learn about the methods it uses to solve a LP problem.

(I hit "Send" too soon)

You can always break a function into continuous chunks and derive in
that interval. In other words, if your discontinuity is at 5, you can
analyze (-inf, 5), 5 itself, and (5, inf). But this has been solved
many times, don't waste your time trying to reinvent the wheel.

You should start at

http://en.wikipedia.org/wiki/Numerical_analysis

then look at the software section

http://en.wikipedia.org/wiki/Numerical_analysis#Software

Depending on your resources and abilities, MATLAB or Mathematica may be
more appropriate than a home-grown solution, but as you'll see this is a
well-researched field with many available solutions.

Ted

 

[Peter J. Holzer]

In excel you have a menu function that consist of given one [...]
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

That may be a bit impractical if @candidates is the set of all floating
point numbers.

True, but it is highly unlikely that the set of all floating point
numbers is stored in an Excel spreadsheet.

I don't think you understood what the Excel feature ("Solver" in
English, "Zielwertsuche" in German) mentioned by the OP
does: You have a cell A with a formula which references (possibly
indirectly) a cell B. Now you can ask Excel to compute the a value of B
so that A has a desired value.

So, yes, the range of possible input values is the whole range of
floating point numbers.

hp

 

[gamo]

In excel you have a menu function that consist of given one [...]
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

That may be a bit impractical if @candidates is the set of all floating
point numbers.

True, but it is highly unlikely that the set of all floating point
numbers is stored in an Excel spreadsheet.

I don't think you understood what the Excel feature ("Solver" in
English, "Zielwertsuche" in German) mentioned by the OP
does: You have a cell A with a formula which references (possibly
indirectly) a cell B. Now you can ask Excel to compute the a value of B
so that A has a desired value.

So, yes, the range of possible input values is the whole range of
floating point numbers.

hp

I'm furious about your recurrency to the solver I never mentioned.

The function is called "buscar objetivo," which could be a translation of
"goal seek."

It does what you had said, BUT it's not the solver. The solver is a LP
solver, basically a objective function with constraints. A task much
more complicated that what I was asking.

Up to now I _suspect_ that the process is related to taking a big interval
and use a modified bisection algorithm.

Best,

 

[Peter J. Holzer]

In excel you have a menu function that consist of given one
[...]
And you can do that with a simple grep():

@results = grep (f($_) == XXX, @candidates);

That may be a bit impractical if @candidates is the set of all floating
point numbers.

True, but it is highly unlikely that the set of all floating point
numbers is stored in an Excel spreadsheet.

I don't think you understood what the Excel feature ("Solver" in
English, "Zielwertsuche" in German) mentioned by the OP
does: You have a cell A with a formula which references (possibly
indirectly) a cell B. Now you can ask Excel to compute the a value of B
so that A has a desired value.

So, yes, the range of possible input values is the whole range of
floating point numbers.

I'm furious

Some people are quick to anger.

about your recurrency to the solver I never mentioned.

The function is called "buscar objetivo," which could be a translation of
"goal seek."

Yes, I misremembered Xho's posting. The builtin function is indeed
called "goal seek" in English Excel, "Solver" is a plugin. I thought it
was the other way around.

I don't have an English Excel to check the name (and no, I won't buy
one just because of the off-chance that someone might take my ignorance
of Microsoft products as a personal insult) so I mentioned the German name
of the function "Zielwertsuche" - I also expect that German name is more
useful to Jürgen than the English one.

It does what you had said, BUT it's not the solver.

Which is probably completely irrelevant to my argument. The function you
and I meant (however it is called) does not grep over some values stored
in a spreadsheet but tries to find a root of the equation (by whatever
means - this is irrelevant, too). So Jürgen's reply that "it is highly
unlikely that the set of all floating point numbers is stored in an
Excel spreadsheet" missed the point.

hp

 

[gamo]

Which is probably completely irrelevant to my argument. The function you
and I meant (however it is called) does not grep over some values stored
in a spreadsheet but tries to find a root of the equation (by whatever
means - this is irrelevant, too). So Jürgen's reply that "it is highly

No, it's not irrelevant. It's the key to solve the problem.
Playing with a financial function, the bisection method works, but
how could I garantize that every function could be reformulated as
f()-XXX and expect the method works?

unlikely that the set of all floating point numbers is stored in an
Excel spreadsheet" missed the point.

hp

Yes, but it was an elegant response with a grep in the hand.