stepthom/math-fun — pull request #48 by jgus (2013-12-04 01:07:35+00:00)
Title: Issue 38

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 points, or between them, and only one root can exist between two neighboring inflection points. The problem can then be broken down into finding all inflection points, and searching for zero or one roots between pairs of inflection points. Inflection points can be found by recursively solving the derivative of the function. For searching between inflection points, we can use Newton's method (which converges for the supported simple polynomials.) Because each range between inflection 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 point, so we check either end, and every inflection 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.