Java Number Cruncher: The Java Programmer’s Guide to Numerical Computation

by Ronald Mak

Comments, criticisms, or suggestions?  Please send them to ron@apropos-logic.com.

Buy it from www.amazon.com

Java Number Cruncher has been translated into Chinese!

Download Java Source Files

David H. Bailey, a widely-recognized expert on scientific programming, wrote a very nice review of this book entitled “Java Meets Numerical Analysis”.

From the preface:

The last time I looked, the Java programming language still had +, -, *, /, and % operators to do operations with numbers. It may be hard to believe today, but programming is not only about Web pages, graphics, enterprise software, database systems, and computer games.

I wrote this book to remind today’s programmers, especially Java programmers, that computers really are quite good at numerical computing, affectionately known as “number crunching.” In fact, some numerical computing underlies most programs — for example, not too many graphics applications or interactive computer games would get very far without crunching at least a few numbers. Of course, scientific, mathematical, statistical, and financial programs rely heavily on numerical computing.

So it behooves the typical Java programmer, besides knowing the standard API alphabet soup — JFC, RMI, JSP, EJB, JDBC, and so on — to know something about how to do good numerical computing. You’ll never know when a roundoff error will bite you, or why that “correct” formula you copied right out of your favorite physics textbook into your program somehow computes the wrong answer.

Another reason I wrote this book is that I’m fascinated by the dichotomies of pure mathematics and computer science. On one hand, you have mathematics, a rigorous, abstract world where it is possible to prove, absolutely, that a computation is correct. On the other hand, you have computers, where computations are, well, they’re fast. And yet, mathematicians and computer scientists can work together to devise some very clever ways to enable computers to do mathematics and, in the great majority of cases, to compute the right answer.

This book is an introduction to numerical computing. It is not a textbook on numerical methods or numerical analysis, although it certainly shows how to program many key numerical algorithms in Java. We’ll examine these algorithms, enough to get a feel for how they work and why they’re useful, without formally proving why they work. Because Java is ideal for doing so, we’ll also demonstrate many of the algorithms with interactive, graphical programs. After seeing how we can dodge some of the pitfalls of floating-point and integer computations, we’ll explore programs that solve equations for x, do interpolation and integration, solve differential equations and systems of linear equations, and more.

Numerical computing is not all work, either. This book also contains several chapters on lighter (but not necessarily less useful) topics, including computing thousands of digits of pi, using different ways to generate random numbers, looking for patterns in the prime numbers, and creating the intricately beautiful fractal images.

I tried hard to keep the math in this book at the freshman calculus level or below — knowledge of high school algebra should be enough for most of it. All the interactive programs in this book can run either as programs or as standalone programs. My friends and I have tested them with the Netscape 4.7 browser running on Windows, Linux, and Solaris, with Microsoft Internet Explorer 6.0 running on the PC, and Microsoft Internet Explorer 5.1 running on the Macintosh. I’ve tested the standalone programs on my Windows 98 PC with JDK 1.2, 1.3, and 1.4. Of course, there’s no guarantee they’ll all work perfectly for you, but the source code for all the programs, along with instructions on how to compile and run them, are available for downloading.

I wrote all the programs strictly as illustrative examples for this book. You’re free to use the source code anyway you like, but bear in mind that this is not fully tested, commercial-quality code. Neither Prentice-Hall nor I can be responsible for anything bad that may happen if you use these programs. I had a lot of fun writing this book and its programs, and I hope that comes through in the text. If you’re inspired to learn more about any of the topics, then I will be very happy.

Part 1: Why Good Computations Go Bad

Simply copying formulas out of a math or statistics textbook to plug into a program will almost certainly lead to wrong results. The first part of the book covers the pitfalls of basic numerical computation.

Chapter 1: Floating-Point Numbers are Not Real

The set of values and the operations of the float and double types are not the same as that of the real number system of mathematics. If we understand how floating point is a very crude approximation of real numbers, we can avoid having our computations go bad.

Chapter 2: How Wholesome are the Integers?

Even integer arithmetic can trap the unwary programmer! The values of the integer types such as int are not arranged linearly on a number line; rather, they’re arranged in a circle like on a clock face. Silent overflow errors can cause havoc if we’re not careful.

Chapter 3: Floating-Point Numbers—They’re a Standard!

Java implements most, but not all, of the IEEE 754 standard for floating-point numbers. This chapter covers what Java programmers need to know about the standard, and how it affects floating-point computation. It also discusses when it may be appropriate to use the strictfp modifier. We have to decide which is more important: taking advantage of the underlying floating-point hardware to achieve the greatest accuracy and performance, or ensuring that a computation always returns exactly the same result on any hardware platform.

Part 2: Iterative Computations

Computers are certainly good at looping, and many computations are iterative in nature. But loops are where errors can build up and overwhelm the chance for any meaningful results.

Chapter 4: Summing Lists of Numbers

Yikes! Even a seemingly innocuous operation such as summing a list of numbers can get us into trouble. Examples show how running floating-point sums can gradually lose precision, and some ways to prevent this from happening. This chapter concludes with a wonderful algorithm that employs feedback in a summation loop to alleviate floating-point problems.

Chapter 5: Finding Roots

Finding the roots of an algebraic equation is another way of saying, “Solve for x.” This chapter introduces several iterative algorithms that converge upon solutions: bisection, regula falsi, secant, improved secant, Newton’s, and fixed-point. We see how to decide which algorithm is appropriate.

Chapter 6: Interpolation and Approximation

Given a set of points in a plane, can we construct a smooth curve that passes through all the points? Or how about a straight line that passes the closest to all the points? This chapter presents algorithms for polynomial interpolation and linear regression.

Chapter 7: Numerical Integration

Freshman calculus teaches integration as mostly algebraic manipulation — if the integrand fits a certain pattern, perform a prescribed set of transformations, and then plug in the values to get the answer. Unfortunately, in the real world, these patterns aren’t always apparent, and so we use the computer to do numerical integration. This chapter introduces several basic algorithms, including the trapezoidal method and Simpson’s rules.

Chapter 8: Solving Differential Equations Numerically

Just as with integration, computer solutions of differential equations are numerical, not analytical. The solution function is described by a set of points in the plane. This chapter introduces several basic algorithms, including Euler’s, predictor-corrector, and the Runge-Kutta methods.

Part 3: A Matrix Package

This part of the book incrementally develops a practical matrix package. We can then import the classes of this package into any Java application that uses matrices.

Chapter 9: Basic Matrix Operations

The basic matrix operations include addition, subtraction, and multiplication. This chapter develops the matrix class that has methods for these operations. It also creates subclasses for vectors and square matrices. The interactive demo uses graphic transformation matrices to animate a three-dimensional wire-frame cube.

Chapter 10: Solving Systems of Linear Equations

We learned to solve systems of linear equations in high school algebra as a tedious manual procedure. After reviewing this procedure, this chapter introduces LU decomposition to solve linear systems. The interactive demo creates polynomial regression functions of any order from 1 through 9, which requires solving a system of “normal” equations.

Chapter 11: Inverting Matrices

LU decomposition also allows us to compute the inverse of a matrix efficiently and reliably. A demo program tests how well we can invert the dreaded Hilbert matrices, which are notoriously difficult to invert accurately.

Part 4: The Joys of Computation

Numerical computation isn’t all work and no play. The final part of the book covers its lighter side.

Chapter 12: Big Numbers

Java’s BigNumber and BigDecimal classes support “arbitrary precision” arithmetic — subject to memory constraints, we can have numbers with as many digits as we like! This chapter explores how these classes can be useful and leads into topics such as encryption algorithms.

Chapter 13: Computing pi

Mathematicians over the centuries have created formulas for computing the value of pi. The enigmatic Indian mathematician Ramanujan devised several very ingenious ones in the early 20th century. An iterative algorithm supposedly can compute over two billion decimal digits of pi. This chapter tests some of these formulas.

Chapter 14: Generating Random Numbers

There are several commonly known algorithms for generating uniformly distributed random numbers. But how can we generate random numbers of other distributions, such as the normal distribution? This chapter explores random number generation. For example, random numbers and the Monte Carlo method can compute the value of pi.

Chapter 15: Prime Numbers

Mathematicians have mulled over prime numbers since nearly prehistoric times. This chapter’s programs explore primality testing, factoring, and the generation of prime numbers such as the Mersenne primes. We also look for patterns in the distribution of prime numbers.

Chapter 16: Fractals

Fractals are beautiful and intricate shapes that are recursively defined. There are various algorithms for generating different types of fractals. In fact, Newton’s algorithm for finding roots (Chapter 5), when applied to the complex plane, can generate a fractal.