How to find function range?

Question

I have an arbitrary function or inequality (consisting of a number of trigonometrical, logarithmical, exponential, and arithmetic terms) that takes several arguments and I want to get its range knowing the domains of all the arguments. Are there any Java libraries that can help to solve a problem? What are the best practices to do that? Am I right that for an arbitrary function the only thing can be done is a brute-force approximation? Also, I'm interested in functions that can build intersections and complements for given domains.

Upd. The functions are entered by the user so the complexity cannot be predicted. However, if the library will treat at least simple cases (1-2 variables, 1-2 terms) it will be OK. I suggest the functions will mostly define the intervals and contain at most 2 independent variables. For instance, definitions like

y >  (x+3), x ∈ [-7;8]
y <= 2x, x ∈ [-∞; ∞]
y =  x, x ∈ {1,2,3}

will be treated in 99% of cases and covering them will be enough for now.

Well, maybe it's faster to write a simple brute-force for treating such cases. Probably it will be satisfactory for my case but if there are better options I would like to learn them.

Answer 1

I would have thought that this is a natural problem to tackle with a Computer Algebra System. I googled around and JAS seems to be the most-cited Java CAS.

If I had to confine myelf to numeric approaches, then I'd probably tackle it with some variety of interval computations. So: the codomain of sin is [-1,1], the codomain of exp is (0,+Inf), and the codomain of exp(sin(expression)) is ...

over to you, this is where I'd reach for Mathematica (which is callable from Java).

Answer 2

Notational remark: I assume you want to find the range of the function, i.e. the set of values that the function can take.

I think this problem is not simple. I don't think that "brute force" is a solution at all, what does "brute force" even mean when we have continuous intervals (i.e infinitely many points!).

However, there might be some special cases where this is actually possible. For example, when you take a sin(F(x)) function, you know that its range is [-1,1], regardless of the inner function F(x) or when you take Exp(x) you know the range is (0,+inf).

You could try constructing a syntax tree with information about the ranges associated to each node. Then you could try going bottom-up through the tree to try to compute the information about the actual intervals in which the function values lie.

For example, for the function Sin(x)+Exp(x) and x in (-inf, +inf) you would get a tree

   +          range: [left range] union [right range]
  / \
sin  exp      range [-1, 1]  ,   range: (0,+inf)
 |    |
 x    x       

so here the result would be [-1, 1] union (0, +inf) = [-1, +inf).

Of course there are many problems with this approach, for example the operation on ranges for + is not always union. Say you have two functions F(x) = Sin(x) and G(x) = 1-Sin(x). Both have ranges [-1,1], but their sum collapses to {1}. You need to detect and take care of such behaviour, otherwise you will get only an upper bound on the possible range (So sort of codomain).

If you provide more examples, maybe someone can propose a better solution, I guess a lot depends on the details of the functions.

@High Performance Mark: I had a look at JAS and it seems that its main purpose is to deal with multivariate polynomial rings, but the question mentioned trigonometric, logarithmic and other transcendental functions so pure polynomial arithmetic will not be sufficient.

Answer 3

Here's another approach and depending on how crazy your function can be (see EDIT) it might give you the universal solution to your problem.

1. Compose the final expression, which might be rather complex.

2. After that use numerical methods to find minimum and maximum of the function - this should give you the resulting range.

EDIT: Only in the case that your final expression is not continuous the above would not work and you would have to divide into continuous sections for each you would have to find min and max. At the end you would have to union those.