Issue 38

[jgus]

Fixes #38

Refactored EvaluateTest to use test parameters rather than a bunch of copy&paste, in anticipation of adding a bunch more tests for evaluate(). I also added constructors to Term and Fraction so they could be created more read-ably.

Improved evaluate(), specifically to add support for evaluating the limit of a function at +/- infinity, which I planned to use in my solver.

Added MathFunction.solve(), which finds all roots of a function. The current implementation is limited to polynomials with only non-negative integer exponents. It also doesn't scale well to very high-degree polynomials (it's O(degree^2)) but it does have the advantages of being relatively simple, robust, and it didn't require re-defining MathFunction to use floating-point. (I considered an approach iteratively finding a single root, factoring it out of the polynomial, then finding another, until the remaining polynomial was linear. That would have been O(degree), but would have required either ditching Fraction for Double, or really beefing up Fraction's functionality.)

My approach is fairy simple: polynomial roots can exist at inflection critical points, or between them, and only one root can exist between two neighboring inflection critical points. The problem can then be broken down into finding all inflection critical points, and searching for zero or one roots between pairs of inflection critical points. Inflection Critical points can be found by recursively solving the derivative of the function. For searching between inflection critical points, we can use Newton's method (which converges for the supported simple polynomials.) Because each range between inflection critical points is monotonic, we also know that no root can exist unless one end of the range is positive and the other negative; we can skip other cases.

With solve() in place, findMinimum/findMaximum were fairly simple: An extremum can only exist at either end of the range, or at an inflection a critical point, so we check either end, and every inflection critical point between them.

The issue suggested hard-coding a range for the command-line entry point; adding switches was trivial, and an infinite default range seemed more natural.

[stepthom]

@jgus Overall, this looks really great. Thanks for spending the time to explain this out so clearly.

One minor question. Is the function MathFunction.getInflections() misnamed? I believe the behaviour of your overall implementation is correct, but the naming is a bit confusing.

getInflections() is used by findMaximum() and findMinimum(). In mathematics, the way to find candidate extremum (i.e., maximums and minimums) of a function f(x) is to

• Find the derivative f'(x)
• Find the roots of f'(x) by setting f'(x)=0 and solving for x.

These roots, along with the end points of the domain, are all the possible extremum (ignoring the special case of any singular points on the curve). Inflection points do not come into play.

An inflection point is a similar but different concept. This is a point on the curve where the concavity changes. Inflections points are found by either (a) finding points where the second derivative changes signs or (b) where the first derivative is at an extremum.

Looking at the implementation, it seems like getInflections() returns the roots of the input MathFunction, not the inflection points. If the input MathFunction happens to be the first derivative f'(x) of another function f(x), then getInflections() will return the roots of f'(x), which are indeed inflection points of f(x). Indeed, this is how findMaximum() and findMinimum() work: they pass the derivative into getInflections(). But it might be clearer to either have findMaximum () and findMinimum() call solve(), passing in the derivative, or have findMaximum() and findMinimum() call getInflections() passing in the original function, and let getInflections() differentiation the function.

Whew, that's a lot of text for a very minor issue! I just want to be sure I understand what's happening. Again, great job on this.

[stepthom]

Actually, it would most clear to do both of the following:

• Have findMaximum () and findMinimum() call solve() (or some wrapper), passing in the derivative
• Have getInflections () take in a function, find the derivative, and call solve() on that derivative.

I hope that makes sense.

[jgus]

Sorry - brain hiccup. Wherever I said "inflection point" I meant "critical point". Hope that clarifies things a bit. :-)

Yes, the fact that getInflections() aka getCriticalPoints() (and interiorSolution()) took the derivative as a parameter was optimization - I wanted to avoid calling differentiate() over and over again in solve(). The contract is that the derivative parameter is expected to be the derivative of this. But, you're right, it's pretty bad for grokability, and there's no forcing function that would prevent something other than the derivative from being passed in. I changed it so that both getCriticalPoints() and interiorSolution() just call differentiate() themselves, and addressed the efficiency issue by having differentiate() cache its result across calls. (And, yes, the caching could be smarter/more efficient.)

Also, the main reason that findMaximum() and findMinimum() don't just call solve().differentiate() directly are the "exercises for the reader" in getCriticalPoints(). It keeps a single point of change should we want to add support for more kinds of equations down the road. (Well, ok, two points, since we would have to handle cases when Newton's method diverges or cycles.)

Does that clarify things?

[stepthom]

:+1: Yes, that helps a lot. Thanks @jgus. Good to merge now.