Sponsored Link • Prime Time
A Simulation of the Java Virtual Machine

 Advertisement The Prime Time applet, included below, demonstrates a Java virtual machine executing a sequence of bytecodes that generates prime numbers. This applet accompanies Chapter 12, "Integer Arithmetic," of Inside the Java 2 Virtual Machine.

For some reason, your browser won't let you view this way cool Java applet.
(Apparently, your browser is not ready for Prime Time.)

The bytecode sequence in the simulation was generated by the `javac` compiler for the `findPrimes()` method of the class shown below:

```// On CD-ROM in file integer/ex1/PrimeFinder.java
class PrimeFinder {

static void findPrimes() {

int primeNum = 1;
int numToCheck = 2;

for (;;) {

boolean foundPrime = true;

for (int divisor = numToCheck / 2; divisor > 1;
--divisor) {

if (numToCheck % divisor == 0) {
foundPrime = false;
break;
}
}

if (foundPrime) {
}

++numToCheck;
}
}
}
```

The `findPrimes()` method places prime numbers, one at a time and in increasing numerical order, into the `primeNum` variable. To find the primes, the `findPrimes()` method checks each positive integer in increasing numerical order starting with integer value two. It keeps the current number it is checking in the `numToCheck` variable. The outer for loop, a "forever" loop, keeps this process going indefinitely. To check a number, it divides the number by smaller integers and looks for a zero remainder. If it encounters a zero remainder, then the number has integral factors other than one and itself and therefore isn't prime.

For each number to check, the `findPrimes()` method divides the number by two. The result of this integer division is the first value checked as a possible integral divisor for the number.

In the inner for loop, the `findPrimes()` method tries each number as a divisor between the result of the division by two and the divisor two. If the remainder of any of these divisions is zero, it breaks out of the inner for loop and skips to the next number to check. If it reaches divisor two and has found no divisor that yields a zero remainder, it has found the next prime number. It exits the inner for loop and sets `primeNum` equal to the number to check.

For example, when `numToCheck` is 10, `findPrimes()` first divides 10 by 2 to get the first divisor, 5. It then performs the remainder operation on 10 and 5 and discovers a zero remainder. So it breaks out of the inner for loop and sets `numToCheck` to 11. (It doesn't ever set `primeNum` to 10.) It divides 11 by 2 to get the first divisor to check, once again 5. It performs the remainder operation on 11 and integers 5, 4, 3, and 2, none of which yield a zero remainder. It completes the inner for loop, sets `primeNum` equal to 11, and continues on to check 12.

The bytecodes generated by `javac` for the `findPrimes()` method are shown below:

``` 0 iconst_1      // Push int constant 1
1 istore_0      // Pop into local var 0: int primeNum = 1;
2 iconst_2      // Push int constant 2
3 istore_1      // Pop into local var 1: int numToCheck = 2;

// The outer for loop (the "forever" loop) begins here:
4 iconst_1      // Push int constant 1
5 istore_2      // Pop into local var 2: boolean foundPrime = true;

// The inner for loop begins here. First, initialize divisor.
6 iload_1       // Push int in local var 1 (numToCheck)
7 iconst_2      // Push int constant 2
8 idiv          // Pop two ints, divide them, push int result
// Pop int into local var 3:
9 istore_3       // int divisor = numToCheck / 2;

// Next, test the inner for loop's termination condition
10 goto 27       // Jump to for loop condition check

// The body of the inner for loop begins here.
13 iload_1       // Push the int in local var 1 (numToCheck)
14 iload_3       // Push the int in local var 3 (divisor)
15 irem          // Pop two ints, remainder them, push result
// Pop int, jump if equal to zero:
16 ifne 24       // if (numToCheck % divisor == 0)
19 iconst_0      // Push int constant 0
20 istore_2      // Pop into local var 2: foundPrime = false;
21 goto 32       // Jump out of inner for loop

// At this point, the body of the inner for loop is done. Now just
// perform the third statement of the for expression: decrement
// divisor.
24 iinc 3 -1     // Increment local var 3 by -1: --divisor

// The test for the inner for loop's termination condition
// begins here. This loop will keep on looping while (divisor > 1).
27 iload_3       // Push int from local var 3 (divisor)
28 iconst_1      // Push int constant 1
29 if_icmpgt 13  // Pop top two ints, jump if greater than

// At this point, the inner for loop has completed. Next check
// to see if a prime number was found.
32 iload_2       // Push int from local var 2 (foundPrime)
33 ifeq 38       // Pop top int, jump if zero: if (foundPrime) {
36 iload_1       // Push int from local var 1 (numToCheck)
37 istore_0      // Pop into local var 0: primeNum = numToCheck;
38 iinc 1 1      // Increment local var 1 by 1: ++numToCheck;
41 goto 4        // Jump back to top of outer for loop.
```

The `javac` compiler placed local variable `primeNum` from the source into local variable slots 0 on the stack frame. It put `numToCheck` into slot 1, `foundPrime` into slot 2, and `divisor` into slot 3. As mentioned above, as this method finds each successive prime number, it places the number into the `primeNum` variable. As you run the simulation, therefore, you will see the prime numbers appear sequentially in the `int` value stored in local variable slot 0.

One thing to note about this bytecode sequence is that it demonstrates the way in which `boolean`s from Java source code are treated on the stack frame by Java bytecodes. The value stored in local variable slot 2, which represents the `boolean` `foundPrime` variable from the source, is an `int`. It is set to `true` or `false` by instructions that push a constant `int` zero or one. Its boolean value is checked by instructions that compare an `int` against zero.

Another thing to note about this simulation is that eventually the `numToCheck` value will overflow. When it does, the virtual machine will throw no exceptions. It will just continue executing the `findPrimes()` method with `int` values that no longer hold any relationship to the prime numbers.

To drive the Prime Time simulation, use the Step, Reset, Run, and Stop buttons. Each time you press the Step button, the simulator will execute the instruction pointed to by the pc register. If you press the Run button, the simulation will continue with no further coaxing on your part until you press the Stop button. To start the simulation over, press the Reset button. For each step of the simulation, a panel at the bottom of the applet contains an explanation of what the next instruction will do. Happy clicking.

Click here to view a page of links to the source code of the Prime Time applet. Web Artima.com