COS 126

N-Body Simulation 		Programming Assignment Checklist

Assignment Page

Goals

Frequently Asked Questions (Operating System and Configuration)

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? Be sure to use the commands javac-introcs and java-introcs (instead of javac and java); these wrapper commands tell Java where to find our standard libraries. If you are using the wrapper commands, try re-rerunning the autoinstaller; this should fix situations where you moved files that the auto-installer 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 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 StdIn.java, StdOut.java, StdAudio.java and StdDraw.java into the same folder as NBody.java (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 (General)

What preparation do I need before beginning this assignment? Read Sections 1.4 and 1.5 of the textbook and familiarize yourself with the command line.

Any advice on completing this programming assignment? This program is more involved than the previous ones, so 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 errors when 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 pp. 1140–1141 of the textbook. They also appear in this Java cheatsheet.

How do I draw an image to standard drawing? The command StdDraw.picture(x, y, filename) reads the image (either JPEG, GIF, or PNG format) from the specified file and draws it to standard drawing, centered at (x, y).

Frequently Asked Questions (Simulation)

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

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 Τ is not a multiple of Δt? Simulate the universe as long as t < Τ. For example, if Τ is 50,000 and Δt is 25,000, you should simulate the system for two steps (t = 0 and 25,000). If Τ 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.

Frequently Asked Questions (Errors and Bugs)

Checkstyle complains about the variable I named T because it begins with an uppercase letter. Which name should I use instead? By convention, a variable in Java should begin with a lowercase letter and use camel case, such as isLeapYear. A constant variable (a variable whose value does not change during the execution of a program, or from one execution of the program to the next) should begin with an uppercase letter and use underscores to separate any word boundaries, such as GRAVITATIONAL_CONSTANT. So, a Java variable name might not always perfect align with the corresponding domain-specific mathematical notation. In this case, tao or stoppingTime would be fine choices.

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

My computer doesn't display the animation smoothly. Is there anything I can do? Be sure to follow the template in BouncingBall.java. In particular, call StdDraw.enableDoubleBuffering() once at the beginning of your program; and call StdDraw.show() and StdDraw.pause(20) at the end of each time step (frame), not after each call to StdDraw.picture().

My animation looks fine, but the numbers are off a little bit when I follow the tests below, what could be causing this? Check that you followed the assignment instructions exactly. In particular, you should have separate loops for Steps A, B, and C and you should update the velocities before the positions in Step B.

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

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!

Frequently Asked Questions (Sound)

When I add the music, I get the following error message on OS X. 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 6 sound library. Consult a lab TA if you need help updating from Java 6 to Java 8.

I can play MP3s using my favorite media player, but no sound plays in Java. What could be wrong? If you are running Windows, 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 on Windows. 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.

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", radius);
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 materials). 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 fragment, with or without citation.

Here are our results for a few sample inputs. 

% java-introcs NBody 0.0 25000.0 < planets.txt           // zero steps
5
2.50e+11
 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
5
2.50e+11
 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
5
2.50e+11
 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
5
2.50e+11
 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
5
2.50e+11
 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       
3
1.25e+11
 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.

The key to composing a large program is decomposing it into smaller steps that can be implemented and tested incrementally. Here is the decomposition we recommend for this assignment.

  1. Parse command-line arguments
  2. Read universe from standard input
  3. Initialize standard drawing
  4. Play music on standard audio
  5. Simulate the universe
    1. Calculate net forces
    2. Update velocities and positions
    3. Draw universe to standard drawing
  6. Print universe to standard output
These are the order in which the components will appear in your code. However, to facilitate testing and debugging, we recommend implementing them in the following order.

Step 1: parse command-line arguments

Step 2: read universe from standard input

Step 6: print universe to standard output

Step 3: initialize standard drawing

Step 4: play music on standard audio

Step 5: simulate the universe

Step 5B: update the velocities and positions

Step 5C: draw universe to standard drawing

Step 5A: calculate the forces

Enrichment

What is the music in 2001.wav? 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 analytic 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/R6 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.