Chaos and BigDecimals

  “Relativity eliminated the Newtonian illusion of absolute space and time; quantum theory eliminated the Newtonian dream of a controllable measurement process; and chaos eliminates the Laplacian fantasy of deterministic predictability.” 1

Jonathan Allin is a Senior Java Consultant with Origin IT, a multi-national solutions provider based in Cambridge, UK. He can be contacted at jonathan.allin@uk.origin-it.com.

WE TEND TO think that, in general, random results can only arise from complex systems and that significant changes can only be brought about by a large stimulus. Both ideas are wrong. Most simple systems are capable of producing complex, chaotic results, and, conversely, a small change can produce an arbitrarily large consequence. The butterfly that flapped its wings in Peking did produce a storm in New York. All that is needed is a bit of feedback and a bit of nonlinearity.

What is chaos? In the mathematical sense chaotic behavior has two requirements: (1) results that are sensitive to initial conditions and (2) results that are non-repetitive or random. Chaos should not be confused with noise, which is an unwanted influence on a system.

The simplest equation that produces chaotic behavior is the logistic equation. This equation has been used to model the behavior of various systems from banking to the movement of planets. It can also be used as a simple model of population growth, where this year's population is dependent on last year's (e.g., animals such as birds, which have an annual breeding cycle).

Table 1. Details of rounding options for the BigDecimal class. The numbers in the column headers have been rounded to two decimal places.
Rounding mode Description 1.2367 -1.2367 1.235 -1.265 1.2341 -1.2341
ROUND CEILING Round toward
positive infinity
1.24 -1.23 1.24 -1.26 1.24 -1.23
ROUND DOWN Round toward 0
by truncating
1.23 -1.23 1.23 -1.26 1.23 -1.23
ROUND FLOOR Round toward
negative infinity and below round toward zero, else round away from zero
1.23 -1.24 1.23 -1.27 1.23 -1.24
ROUND HALF DOWN If last digit is 5 1.24 -1.24 1.23 -1.26 1.23 -1.23
ROUND HALF EVEN If last digit is odd, then round half up, otherwise as round half down 1.24 -1.24 1.24 -1.26 1.23 -1.23
ROUND HALF UP If last digit is 5 and above round away from zero, else round toward zero 1.24 -1.24 1.24 -1.27 1.23 -1.23
ROUND UP Round away form zero by incrementing las significant truncating 1.24 -1.24 1.24 -1.27 1.24 -1.24


To model population growth we might start off with the naïve equation:
thisPop = rate * lastPop
i.e., this year's population is last year's population multiplied by the rate of breeding. This equation leads to unrestricted exponential growth but quickly breaks down in the real world because, in practice, growth is limited by lack of food, predation, lack of living room, limited energy supply, etc.

We therefore introduce a new term that reflects this restriction, and this gives us the so called “logistic equation”:
thisPop = rate * lastPop (1 - lastPop)
This also normalizes the population to a value between 0 (extinction) and 1 (saturation).

This simple equation holds unbelievable riches. It cannot be solved analytically, only numerically: if I want to know the population in 10 generations time, I have to apply the equation 10 times.

I originally implemented the equation using doubles, however, I was concerned that rounding errors would introduce noise, and therefore invalidate the results.

What I needed was unlimited precision: this was provided by Java's BigDecimal class. Here, I review the BigDecimal class, and use it in an application with which you can explore the logistic equation.

THE BigDecimal CLASS
BigDecimal, and its companion BigInteger, are part of the java.math package. Both classes extend Number, which means that, along with Integer, Float, Double, etc., they have methods to return an integer, float, or double, representation. A BigDecimal can be used to represent an arbitrary precision rational number, and a BigInteger to represent an arbitrary precision integer.

Table 2. Values from the logistic equation.
Iteration Value
0 0.1
1 0.351
2 0.8884161
3 0.386618439717081
4 0.9248640249724621386134396738121
5 0.271013185108376366200014086640124882498446354809446978470185001
6 0.7705036505625782420100288501800724673002582158090841219337408507
214354984983318832966012404717170683366990906868712244550569961


A BigDecimal should be used when a double does not provide the necessary precision or when more control over rounding is required.

BigDecimals and BigIntegers are immutable, which means that once created, they cannot be modified. “Modifying” a BigDecimal involves creating a new BigDecimal with the correct characteristics (this is generally transparent to the user).

The BigDecimal class defines eight constants, which specify the rounding mode. Seven of these are described in Table 1. (When I was at school we were taught only one method of rounding: round half up!) The numbers have been rounded to two places.

The eighth constant is ROUND_UNNECESSARY. This indicates that truncating the number to the desired number of places will not lose precision. An exception is thrown if this is not true. In practice this means that truncating with ROUND_UNNECESSARY should only remove trailing zeroes.

BigDecimal represents a number as an arbitrary large integer, plus a scale factor that indicates the number of decimal digits. So 1234.568901 is represented as 1234568901 and a scale factor of 6.

Truncating numbers becomes essential. If I multiply a 5-digit number by a 10-digit number, then I will generate a 14- or 15-digit number. Nor does it matter if the number has trailing zeroes, so multiplying 1.0 by 1.0 produces 1.00, i.e., the scale factor is 2.

To illustrate this, I printed out the first few values from the logistic equation, with no truncation set. The initial value was 0.1, and the ratio was 3.9 (see Table 2).

A few more iterations and my PC would have given up! It is therefore necessary to limit the maximum number of decimal places, though in practice this can be quite high: My PC is nothing special, but 100 decimal places calculates about 100 iterations per second.

setScale() is used to set a BigDecimal's scale. It comes in two flavors: setScale(int scale) and setScale(int scale, int roundingMode). The first is generally used to increase the scale. It can be used to decrease the scale but will throw an ArithmeticException if a rounding error occurs, e.g., an exception will be thrown if this method is used to reduce the scale of 3.45 from 2 to 1.

It's often desirable to reduce the scale to remove unwanted trailing zeroes, e.g., 45.3400 has a scale of 4, while a scale of two would be sufficient. However, there is no direct way of doing this. The following code relies on the fact that BigDecimal throws an ArithmeticException if an attempt is made to reduce the scale, when this would result in a loss of precision due to rounding. So it starts with a scale of zero and increases the scale until an exception is no longer generated.
 BigDecimal setSmallestScale(BigDecimal value)
  {
     for(int scale = 0; ; scale++)
     {
        try
        {
            value = value.setScale(scale);
        }
        catch(ArithmeticException e)
        {
            continue;
        }
        return value;
     }
  }
The second variation, setScale(int scale, int roundingMode), is generally used to decrease the scale of a number. (e.g., in the following code):
BigDecimal d1 = new BigDecimal(2.456);
BigDecimal d2 = d1.setScale(1, BigDecimal.ROUND_DOWN);
d2 will have the value 2.4, with a scale of 1.

As you would expect, BigDecimal provides the basic arithmetic functions: add(), subtract(), multiply(), and divide(). A rounding mode must always be specified with divide(). The scale of the quotient will be the scale of this BigDecimal, or as specified in the method call. e.g.,:
BigDecimal dividend = new BigDecimal(5.5);
BigDecimal divisor = new BigDecimal(2.000);
BigDecimal quotient = dividend.divide(divisor,
BigDecimal.ROUND_DOWN);
gives a quotient with a value of 2.7 and a scale of 1. To specify the scale of the quotient use divide(BigDecimal val, int scale, int roundingMode).

Figure 1
Figure 1.
The Chaos user interface. Controls are in the lower panel, results are plotted in the upper panel.


Other methods to watch are hashCode() and equals(). A BigDecimal's hash code is dependent not just on the number's value but also on its scale. This means that 1.5 and 1.50 have different hash codes, and because of the duality between hashCode() and equals(), a test using equals() will return false. However, compareTo() will return 0, because it ignores the scale. In the following code:
BigDecimal d1 = new BigDecimal(2.4);
BigDecimal d2 = new BigDecimal(2.40);
boolean areEqual = d2.equals(d1);
int comparison = d2.compareTo(d1);
areEqual is false because the numbers have different scales but comparison is 0, because they have the same value.

Figure 2
Figure 2.
Class diagram for the Chaos application.


THE CHAOS APPLICATION
User Interface
The Chaos application allows the logistic equation to be plotted and explored. Different initial populations can be chosen as can different growth rates or ratios.

To understand the code, it's best to start with a look at the application
(Figure 1).

The lower panel contains the controls, the upper panel is used to plot the results. From left to right we can set the initial population (0 to 1), the growth rate or ratio (typically 0 to 4), and the number of decimal places (i.e., the scale) to which the calculations will be restricted (a value of 0 will remove any limit, but you won't be able to calculate more than the first few points).

“Zoom” is not really a zoom factor, but the number of pixels (plus one) between successive points. A value of one plots one pixel per point, greater values will join up successive points. If you set the number of decimal places to zero, i.e., unlimited, then set the zoom to something like 80 to 100. This will ensure that only the first few points are plotted.

Plot color is used to set the color of the next plot.

Having set the required values, pressing the Plot button will cause plotting to commence. Multiple plots can be made with the Clear button being used to clear the panel as required.

Experiment with different values and see what happens. Later, I list some interesting values to use and think about.

Program Structure
Figure 2 is a class diagram for the Chaos application. It consists of three classes: GraphPanel, Chaos, and ColorChoice. In the interests of simplicity I have not included any input checking, nor provided axes markers. The complete program is given in Listing 1.

GraphPanel Class
GraphPanel extends Panel and is the class responsible for creating a plot and presenting it.

The plotting is carried out in a for loop (lines 35 to 54), within the makePlot() method. This loops once for each point plotted. The plotting is done into an off-screen image buffer, image. The width of the buffer, and hence the number of points plotted, is determined by the size of the window. g is the buffer's graphics context.

The actual calculation for the logistic equation is carried out on line 36:
newPop = ratio.multiply(oldPop.multiply
(one.subtract(oldPop)));
It's a shame that Java doesn't support operator overloading. The meaning would be much clearer if we could write:
newPop = ratio *  oldPop * (one - oldPop);
It's worth noting that, because BigDecimals are immutable, three new BigDecimals are created for every point.

Next is a try-catch block that limits newPop's scale (i.e., the number of digits after the decimal point) if decimalPlaces is non zero.

Line 45 converts the new population (a number between 0 and 1) to a y coordinate that can be plotted. The height of the plot is scaled to the size of the window.

Figure 3
Figure 3.
The effect of increasing the ratio or rate. Black = 1.5, green = 2.0, red = 2.9, Zoom = 5.


The actual plotting is done in lines 47 to 50: this will plot a single point if the zoom (the point-to-point step size) is 1 or will draw a line from the old point to the new point if the zoom is greater than 1.

At the end of the loop the old values for the population and its plotted value are set to the new values.

Figure 4
Figure 4.
At a ratio of 3.5, the population cycles among four distinct values. Single plot, zoom = 1.


repaint() is called at the end of makePlot(). repaint() schedules a call to paint(), which in turn simply copies the image buffer into the Panel. If an image buffer wasn't used then every time the application was re-sized, or partially obscured, the last graph would be re-plotted, and the others lost. The downside of double buffering like this is that a plot does not become visible until sometime after it has been plotted.

Figure 5
Figure 5.
Chaos! The ratio is 3.9.


clear() is called when the Clear button is pressed. Its main task is to create a new image buffer that matches the size of the GraphPanel.

update() is overridden to prevent the Panel being cleared to its background color, to save a little time.

Chaos Class
The Chaos class is the application's main class. The constructor (lines 108 to 139) is responsible for creating the control panel (controlPanel), which contains all the UI widgets and an instance of our GraphPanel (gp).

The control panel uses a grid layout to get some control over the layout of the UI components. It's added to the south of the Frame. The GraphPanel (gp) is added to the center.

Table 3. The effect of different ratios, or rates.
Values Consequence
ratio <> Population dies out.
1 < ratio=""><> Population tends to a fixed final value, without any overshoot, irrespective of the initial value.
2 < ratio=""><> Population tends to a fixed final value, with overshoot.
3 < ratio=""><> Population oscillates between 2, 4, 8, or 16 different values as the ratio is increased. This is known as bifurcation, with the number of possible values doubling ever more rapidly as the ratio is increased. At a ratio of about 3.57 the number of possible values is infinite. Beyond this is chaos.
3.57 < ratio=""><> Chaotic behavior but with islands of stability, e.g., try a value of 3.83.

All the action is handled by actionPeformed(). If the Clear button is pressed, then the GraphPanel is cleared (lines 155, 156). If the enter key is pressed when any of the text fields have focus, or the Plot button is pressed, then the set up values are copied into our instance of GraphPanel, and the GraphPanel's makePlot() method is called (lines 142 to 153).

ColorChoice
ColorChoice (lines 77 to 93) is simply a Choice component that presents a list of colors to the user. It provides an additional method, getColor(), that returns the Color object represented by the color chosen by the user.

Figure 6
Figure 6.
Sensitivity to initial values. Red, initial value = 0.10000; green, initial value = 0.10001. The ratio is 3.9. Complete divergence occurs after about 14 cycles.



Figure 7
Figure 7.
The effect of increased precision: The green plot was plotted to 30 decimal places, the red plot to 20. The two plots diverge after about 100 points.


EXPLORING THE LOGISTIC EQUATION

Now it's time to experiment with the logistic equation! Use Table 3 as a guide: some of the results are shown in Figures 3, 4, and 5.

Ratios above 3 start to produce some interesting results. Figure 6 shows how sensitive the results are at high ratios to a small change in the initial value.

So, did I need the extra precision that BigDecimal provided? Yes and no. Figure 7 shows that, in a chaotic situation, increased precision gives different results. However, the critical values (e.g., the values at which bifurcation occurs) appear to be independent of precision.

RECOMMENDED READING

1. Gleick, J., Chaos,Sphere Books, London, 1988. A very readable, non-mathematical, introduction to chaos. It reviews everything from the Mandelbrot set to Jupiter's great red spot.
2. Williams, G. P. Chaos Theory Tamed,Taylor & Francis, London, 1996. A more mathematical look at chaos. It reviews the basic math needed prior to a more detailed analysis.


comments powered by Disqus
Upcoming Events

AppTrends

Sign up for our newsletter.

I agree to this site's Privacy Policy.