The Artima Developer Community
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) {
                primeNum = numToCheck;
            }

            ++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 booleans 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.


Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use