The cost of Java object orientation in mathematical calculations (ctd 2)

On the previous page, we introduced the notion of complex numbers. As we'll see in a moment, calculation using complex numbers is an example of a task where the most intuitive and maintainable implementation is to encapsulate a complex number as an object, but where potentially, object orientation can be "optimised" away. Before we examine such optimisation, we next take an overview of Newton's method, an algorithm that we can use with complex numbers.

Newton's method

Newton's method is also sometimes called the Newton-Raphson method. Essentially, given a particular expression such as x³ + x² - 7, it is a method for finding the value of the variable (x) so that the expression evaluates to zero. Or put another way, it is a method of solving an equation such as x³ + x² - 7 = 0. We start with an initial guess of x. Then we run a number of iterations, each time improving the guess until it converges on the value (or one of the possible values) of x that makes the original expression evaluate to zero. On each iteration, the new value of x is calculated as follows:

So what does this mean? Well, f(x) is simply our original function or expression: x³ + x² - 7 in this case. And f ' (x) is the derivative of that expression. In this case, that means 3x² + 2x. (See the previous link for details if you're not familiar with the concept of derivation.) So we can write a program such as the following to solve the equation:

public static void solveEquation() {
  double x = 100d;
  for (int i = 0; i < 20; i++) {
    double num = x*x*x + x*x - 7;
    double den = 3*x*x + 2*x;
    double diff = num / den;
    if (diff == 0) break;
    x -= diff;
    System.out.println(x);
  }
}

66.55652317880795
44.261527769226035
29.399396150117532
19.493589776799954
12.89422696811397
8.503846749947622
5.596117895611999
3.6980385402133633
2.515779831648314
1.8807871665240836
1.658826764000141
1.63149449022277
1.6310993793754962
1.6310992975389933
1.6310992975389897

It's worth noting that because floating point calculations are only accurate to a certain number of significant figures, strictly speaking the comparison with zero isn't always desirable— once the number in question gets extremely small, the point at which it equals exactly zero to the precision of a double is essentially arbitrary.

For now, we'll leave that problem aside and live with the comparison with zero for simplicity's sake. And so we'll say that, as accurately as can be represented in a double, 1.6310992975389897 is the value of x where x³ + x² - 7 = 0. Or more precisely, it is one of the real values of x where this is the case.

In general, for a polynomial (essentially, a function of this form), we expect as many roots (values of x where the function evaluates to zero) as the highest power. In this case, there are therefore 3 roots. But not all of the roots (or even any of them) are necessarily real numbers. In this case, 2 of the roots are actually complex numbers.

Newton's method with complex numbers

Newton's method works in essentially the same way as above with complex numbers: we use exactly the same calculation on each iteration, but with x being a complex number at each stage along the way. Java doesn't have complex number primitives, but one way of tackling the problem is to encapsulate a complex number as an object. On the next page, we define a complex number class to show how this would work.