Sponsored Link • Fibonacci Forever
A Simulation of the Java Virtual Machine

 Advertisement The Fibonacci Forever applet, included below, demonstrates a Java Virtual Machine executing a sequence of bytecodes that generate the Fibonacci series. This applet accompanies Chapter 10, "Stack and Local Variable Operations, " of Inside the Java 2 Virtual Machine.

For some reason, your browser won't let you view this way cool Java applet.

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

```// On CD-ROM in file stackops/ex1/Fibonacci.java
class Fibonacci {

static void calcSequence() {
long fiboNum = 1;
long a = 1;
long b = 1;

for (;;) {
fiboNum = a + b;
a = b;
b = fiboNum;
}
}
}
```

The `calcSequence()` method produces the Fibonacci series and places each Fibonacci number successively in the `fiboNum` variable. The first two numbers of the Fibonacci series are both ones. Each subsequent number is calculated by summing the previous two numbers, as in: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on.

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

``` 0 lconst_1   // Push long constant 1
1 lstore_0   // Pop long into local vars 0 & 1: long a = 1;
2 lconst_1   // Push long constant 1
3 lstore_2   // Pop long into local vars 2 & 3: long b = 1;
4 lconst_1   // Push long constant 1
5 lstore 4   // Pop long into local vars 4 & 5: long fiboNum = 1;
7 lload_0    // Push long from local vars 0 & 1
8 lload_2    // Push long from local vars 2 & 3
10 lstore 4   // Pop long into local vars 4 & 5: fiboNum = a + b;
12 lload_2    // Push long from local vars 2 & 3
13 lstore_0   // Pop long into local vars 0 & 1: a = b;
14 lload 4    // Push long from local vars 4 & 5
16 lstore_2   // Pop long into local vars 2 & 3: b = fiboNum;
17 goto 7     // Jump back to offset 7: for (;;) {}
```

The `javac` compiler placed local variable `a` from the source into local variable slots 0 and 1 on the stack frame. It put `b` into slots 2 and 3 and `fiboNum` into slots 4 and 5. As this method calculates each successive Fibonacci number, it places the number into the `fiboNum` variable. As you run the simulation, therefore, you will see the Fibonacci series appear in the `long` value stored in local variable slots 4 and 5.

You may notice that `long` values are split across the two words they occupy in the local variables by placing the lower half (bits 0 through 31) in the first slot and the upper half (bits 32 through 63) in the second slot. For example, the lower half of the `fiboNum` variable is stored in local variable slot 4. The upper half of `fiboNum` is stored in local variable slot 5. On the operand stack, a similar representation is used. When a `long` value is pushed onto the operand stack, the lower half of the word is pushed, then the upper half.

Keep in mind that this manner of representing `long` values in the local variables and on the operand stack is an artifact of this particular (simulated) implementation of the Java virtual machine. As mentioned in Chapter 5, "The Java Virtual Machine," the specification does not dictate any particular way to layout `long`s and `double`s across the two words they occupy on the stack frame.

Although according to the best mathematical minds, the Fibonacci series does indeed go on forever, the `calcSequence()` method is able to generate Fibonacci numbers only for a while. Unfortunately for `calcSequence()`, the `long` type has a finite range. The highest Fibonacci number this simulation can calculate, therefore, is the highest Fibonacci number that can be represented in a long: 7540113804746346429L. After the simulation arrives at this point in the Fibonacci series, the next addition will overflow.

To drive the Fibonacci Forever 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 Fibonacci Forever applet. Web Artima.com