Programming Assignment Checklist: N-Body Simulation


Frequently Asked Questions Part 1: Operating System Questions

I used the auto-installer, but when I compile in Terminal/Command Prompt, the Java compiler reports that it cannot resolve symbol StdDraw. Why is this? Make sure you are using the commands javac-introcs and java-introcs (instead of javac and java); these wrapper commands are modified to tell Java where to find our standard libraries.

I used the auto-installer, but when I compile with javac-introcs, the Java compiler reports that it cannot resolve symbol StdDraw. What should I do? You can try re-rerunning the autoinstaller; this should fix situations where you moved files that the autoinstaller added. Otherwise, check with a lab TA.

I used the auto-installer. I can compile my program in DrJava, but when I try to run it in Terminal/Command Prompt using java-introcs, it complains. A common reason is that DrJava is using one version of Java and your Terminal/Command Prompt is using a different version. See a lab TA. In the meantime, try compiling and executing in Terminal/Command Prompt (instead of compiling in DrJava and executing in Terminal/Command Prompt).

I did not use the auto-installer. How do I access stdlib.jar? We highly recommend using the auto-installer. If you are unable or unwilling to use the auto-installer, here are a few alternatives.

I am using an OIT cluster machine. How can I access stdlib.jar? It may work automatically. If not, here are a few alternatives. The simplest is to copy,, and into the same folder as (but you'll have to do this for each assignment). The lab TAs can help you with this.

DrJava doesn't let me redirect standard input. What should I do instead? Sorry, DrJava does not support redirection or piping; use the Terminal/Command Prompt.

What is the best way to download the helper files associated with this assignment? See the programming assignment FAQ.

Frequently Asked Questions Part 2: Programming Questions

What preparation do I need before beginning this assignment? Read Sections 1.4 and 1.5 of the textbook. You also should get familiar with using the command line.

Any advice on completing this programming assignment? This program is more involved than the previous ones, and you should budget more time accordingly. The best advice we can give you is to carefully test, debug, and re-test your code as you write it. Do not attempt to write the whole program at once—if you do, then you will have no idea where to find the error if the program doesn't work. Proactive testing will save you enormous amounts of time in the long run. Trust us!

Do I have to follow the assignment specifications for reading input from command-line arguments and standard input, and writing output to standard drawing and standard output? Yes, or you will lose a substantial number of points.

Where can I find the APIs for StdIn, StdOut, StdDraw, and StdAudio? They are on p. 716–718 of the textbook. They are also available online in this Java cheatsheet.

Why do I get an InputMismatchException or a NoSuchElementException when I try to read data using StdIn?

How do I plot a picture using StdDraw? The command StdDraw.picture(x, y, filename) plots the image in the given filename (either JPEG, GIF, or PNG format) on the canvas, centered on (x, y).

My computer doesn't display the animation smoothly. Is there anything I can do? Use to use the animation mode of standard draw and pause for t milliseconds. Call it once at the end of each time step (frame), not after each drawing command. A typical delay time would be between 10 and 50 milliseconds, but use whatever looks good on your computer.

Can I combine Steps 1, 2, and 3 for each body? No, as indicated in the assignment, you must separate Step 1 (compute all of the forces) from Step 2 (update the positions); otherwise, you will be computing the forces at time t using the positions of some of bodies at time t and others at time t + Δt.

My animation looks fine, but the numbers are off a little bit when I follow the tests below, what could be causing this? Read the question just above — this is the most common cause. Double-check that you followed the assignment instructions exactly in the order of how positions and velocities are updated.

I draw the bodies, but they do not appear on the screen. Why? Use StdDraw.setXscale() and StdDraw.setYscale() to change the coordinate system to use the physics coordinates instead of the unit box. Since we want it centered on the origin with a "square radius" of R, the minimum of each axis should be –R and the maximum should be +R.

My bodies repel each other. Why don't they attract each other? Make sure that you get the sign right when you apply Newton's law of gravitation: (x[j] - x[i]) vs. (x[i] - x[j]). Note that Δx and Δy can be positive or negative so do not use Math.abs(). Do not consider changing the universal gravitational constant G to patch your code!

What is Δx? It's the change in x-coordinate between two bodies (not between a body at time t and at time t + Δt).

How many steps should my program simulate if T is not a multiple of ΔT? Simulate the universe as long as t < T. For example, if T is 50,000 and ΔT is 25,000, you should simulate the system for two steps (t = 0 and 25,000). If T is 60,000 and ΔT is 25,000, you should simulate the system for three steps (t = 0, 25,000 and 50,000).

Does my program need to plot anything if T equals 0? No.

Everything works until I add"2001.mid") then everything hangs. What do I do? On some machines there may be a timing conflict (known in computer science as a "race") between between sending things to the drawing window and sending things to the sound card. Try moving to a place in the program after your initial calls to StdDraw.setXscale() and StdDraw.setYscale().

I can play MP3s using my favorite media player, but no sound plays in Java. What could be wrong? If you are running Windows XP, be sure that the audio stream that Java uses is not muted via Start -> Programs -> Accessories -> Multimedia -> Volume Control -> Wave Out.

When I add the music, I get the following error message. How can I fix it?

java.util.prefs.WindowsPreferences (init).
Could not open/create prefs root node Software\JavaSoft\Prefs at root 0x80000002.
Windows RegCreateKeyEx(...) returned error code 5.
Try running your command prompt as administrator (right-click on the shortcut icon). Then use it as before and try again. If this doesn't help, consult a lab TA.

When I add the music, I get the following error message. How can I fix it?

This application, or a library it uses, is using the deprecated Carbon Component Manager
for hosting Audio Units. Support for this will be removed in a future release.
You can ignore it. It is a warning intended for the authors of the Mac OS X Java sound library.

Testing and Debugging

Inserting print statements is a good way to trace what your program is doing. Our input files were created with the following StdOut.printf() statements.

StdOut.printf("%d\n", N);
StdOut.printf("%.2e\n", R);
for (int i = 0; i < N; i++) {
    StdOut.printf("%11.4e %11.4e %11.4e %11.4e %11.4e %12s\n",
                   px[i], py[i], vx[i], vy[i], mass[i], image[i]);

As indicated in the collaboration policy, you may not copy or adapt code (except from the course mateials). Moreover, you need to cite any code that you copy or adapt (except for code provided with the assignment). So, you are free to copy or adapt this code, with or without citation.

Here are our results for a few sample inputs.

% java-introcs NBody 0.0 25000.0 < planets.txt           // zero steps
 1.4960e+11  0.0000e+00  0.0000e+00  2.9800e+04  5.9740e+24    earth.gif
 2.2790e+11  0.0000e+00  0.0000e+00  2.4100e+04  6.4190e+23     mars.gif
 5.7900e+10  0.0000e+00  0.0000e+00  4.7900e+04  3.3020e+23  mercury.gif
 0.0000e+00  0.0000e+00  0.0000e+00  0.0000e+00  1.9890e+30      sun.gif
 1.0820e+11  0.0000e+00  0.0000e+00  3.5000e+04  4.8690e+24    venus.gif

% java-introcs NBody 25000.0 25000.0 < planets.txt       // one step
 1.4960e+11  7.4500e+08 -1.4820e+02  2.9800e+04  5.9740e+24    earth.gif
 2.2790e+11  6.0250e+08 -6.3860e+01  2.4100e+04  6.4190e+23     mars.gif
 5.7875e+10  1.1975e+09 -9.8933e+02  4.7900e+04  3.3020e+23  mercury.gif
 3.3087e+01  0.0000e+00  1.3235e-03  0.0000e+00  1.9890e+30      sun.gif
 1.0819e+11  8.7500e+08 -2.8329e+02  3.5000e+04  4.8690e+24    venus.gif

% java-introcs NBody 50000.0 25000.0 < planets.txt       // two steps
 1.4959e+11  1.4900e+09 -2.9640e+02  2.9799e+04  5.9740e+24    earth.gif
 2.2790e+11  1.2050e+09 -1.2772e+02  2.4100e+04  6.4190e+23     mars.gif
 5.7826e+10  2.3945e+09 -1.9789e+03  4.7880e+04  3.3020e+23  mercury.gif
 9.9262e+01  2.8198e-01  2.6470e-03  1.1279e-05  1.9890e+30      sun.gif
 1.0818e+11  1.7499e+09 -5.6660e+02  3.4998e+04  4.8690e+24    venus.gif

% java-introcs NBody 60000.0 25000.0 < planets.txt       // three steps
 1.4958e+11  2.2349e+09 -4.4460e+02  2.9798e+04  5.9740e+24    earth.gif
 2.2789e+11  1.8075e+09 -1.9158e+02  2.4099e+04  6.4190e+23     mars.gif
 5.7752e+10  3.5905e+09 -2.9682e+03  4.7839e+04  3.3020e+23  mercury.gif
 1.9852e+02  1.1280e+00  3.9705e-03  3.3841e-05  1.9890e+30      sun.gif
 1.0816e+11  2.6248e+09 -8.4989e+02  3.4993e+04  4.8690e+24    venus.gif

% java-introcs NBody 31557600.0 25000.0 < planets.txt    // one year
 1.4959e+11 -1.6531e+09  3.2949e+02  2.9798e+04  5.9740e+24    earth.gif
-2.2153e+11 -4.9263e+10  5.1805e+03 -2.3640e+04  6.4190e+23     mars.gif
 3.4771e+10  4.5752e+10 -3.8269e+04  2.9415e+04  3.3020e+23  mercury.gif
 5.9426e+05  6.2357e+06 -5.8569e-02  1.6285e-01  1.9890e+30      sun.gif
-7.3731e+10 -7.9391e+10  2.5433e+04 -2.3973e+04  4.8690e+24    venus.gif

// this test should take only a few seconds. 4.294E9 is bigger than the largest int
% java-introcs NBody 4.294E9 2.147E9 < 3body.txt       
 2.1470e+12 -7.8082e-03  5.0000e+02 -3.6368e-12  5.9740e+24    earth.gif
 1.2882e+14 -1.5100e+17  3.0000e+04 -3.5165e+07  1.9890e+30      sun.gif
-1.2882e+14  1.5100e+17 -3.0000e+04  3.5165e+07  1.9890e+30      sun.gif

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. If you get stumped or frustrated on some portion of the assignment, you should not hesitate to consult a preceptor.


What is the music in 2001.mid? It's the fanfare to Also sprach Zarathustra by Richard Strauss. It was popularized as the key musical motif in Stanley Kubrick's 1968 film 2001: A Space Odyssey.

I'm a physicist. Why should I use the leapfrog method instead of the formula I derived in high school? In other words, why does the position update formula use the velocity at the updated time step rather than the previous one? Why not use the 1/2 a t^2 formula? The leapfrog method is more stable for integrating Hamiltonian systems than conventional numerical methods like Euler's method or Runge-Kutta. The leapfrog method is symplectic, which means it preserves properties specific to Hamiltonian systems (conservation of linear and angular momentum, time-reversibility, and conservation of energy of the discrete Hamiltonian). In contrast, ordinary numerical methods become dissipative and exhibit qualitatively different long-term behavior. For example, the earth would slowly spiral into (or away from) the sun. For these reasons, symplectic methods are extremely popular for N-body calculations in practice. You asked!

Here's a more complete explanation of how you should interpret the variables. The classic Euler method updates the position uses the velocity at time t instead of using the updated velocity at time t + Δt. A better idea is to use the velocity at the midpoint t + Δt / 2. The leapfrog method does this in a clever way. It maintains the position and velocity one-half time step out of phase: At the beginning of an iteration, (px, py) represents the position at time t and (vx, vy) represents the velocity at time t - Δt / 2. Interpreting the position and velocity in this way, the updated position (px + Δt vx, py + Δt vy). uses the velocity at time t + Δt / 2. Almost magically, the only special care needed to deal with the half time-steps is to initialize the system's velocity at time t = -Δt / 2 (instead of t = 0.0), and you can assume that we have already done this for you. Note also that the acceleration is computed at time t so that when we update the velocity, we are using the acceleration at the midpoint of the interval under consideration.

Are there analytic solutions known for N-body systems? Yes, Sundman and Wang developed global analytical solutions using convergent power series. However, the series converge so slowly that they are not useful in practice. See The Solution of the N-body Problem for a brief history of the problem.

Who uses N-body simulation? N-body simulations play a crucial role in our understanding of the universe. Astrophysicists use it to study stellar dynamics at the galactic center, stellar dynamics in a globular cluster, colliding galaxies, and the formation of the structure of the Universe. The strongest evidence we have for the belief that there is a black hole in the center of the Milky Way comes from very accurate N-body simulations. Many of the problems that astrophysicists want to solve have millions or billions of particles. More sophisticated computational techniques are needed.

The same methods are also widely used in molecular dynamics, except that the heavenly bodies are replaced by atoms, gravity is replaced by some other force, and the leapfrog method is called Verlet's method. With van der Waals forces, the interaction energy may decay as 1/R^6 instead of an inverse square law. Occasionally, 3-way interactions must be taken into account, e.g., to account for the covalent bonds in diamond crystals.

Kepler's Orrery uses an N-body simulator to compose and play music.

What techniques are used to do N-body simulation in practice? Here's a wealth of information on N-body simulation.

Any ideas for creating my own universe? Here are some interesting two-body systems. Here is beautiful 21-body system in a figure-8 —reproducing this system (in a data file in our format) will earn you a small amount extra credit.