Letters

Java and CRC Feedback

Dear DDJ,

In the April 1997 "Letters" section of DDJ, Steen Lehmann took exception to Michael Swaine's comment that "Java is slow." Steen said that "Sun has already demonstrated the Java Virtual Machine running in hardware, so what interpretation stage?" This is equivalent to saying since Mac applications run on PowerPC, it will run fast on any platform. Anything running on something other than its native platform needs to be either recompiled or interpreted.

Java was developed for ease of interpretation. Unless every workstation uses the JavaChip as a coprocessor or main CPU (not likely), portable Java applications will need to be interpreted. There is talk of "just-in-time compilation," where Java code is compiled to native code on the target machine. This may be an effective solution, but not part of the mainstream use.

The hype surrounding Java is tremendous. I just read several posts from a CAD forum that the next CAD version should be written entirely in Java. Yikes. The compiled version is already a huge, multimeg program. I see a dual future for Java: Small interpreted applications that float around a network, and larger native-compiled programs that can run relatively fast on specific hardware.

I also want to thank Tim Kientzle for explaining CRCs in the April 1997 issue. I thought I was just stupid after reading many articles on CRCs and not understanding how the CRC polynomial actually related to the implementation. Some CRC articles that I have read actually implied that the input bit stream is multiplied (XORed) by the polynomial and then added to the CRC. I guess after I learned it wrong, it stuck. Once Tim correctly explained how the CRC is divided by the polynomial, everything made sense.

Scott G. Henion
[email protected]

Nothing New Under the Sun

Dear DDJ,

"The software field is one of constant reinvention," write Richard Stallman and Simson Garfinkle in their passionate "Against Software Patents" (Communications of the ACM, January 1992). No doubt this massive obscure heritage leads one to suspect he has stumbled onto something new more often than is the case.

The method described by Dean Clark in "A 2-D DDA Algorithm for Fast Image Scaling" (DDJ, April 1997) falls into this category. It describes a method that was well known in the circles in which I traveled almost a decade ago, when I wrote ("Full-color imaging on amplitude-quantized color mosaic displays," SPIE Vol. 1075 "Digital Image Processing Applications" (1989) p. 199ff)

Scholars may notice that single-branched error propagation is isomorphic with the rendering of straight lines using Bresenham's algorithm and modern methods of rescaling binary raster images....

As Dean's well-written article points out, nonbinary images can obviously exploit the method for the sake of speed at the sacrifice of image quality, relative to interpolation methods.

R.I. Feigenblatt
[email protected]

Dean responds: Thank you Mr. Feigenblatt. Your quote of Stallman and Garfinkle is almost painfully true. While I did "invent" the method presented independently (though more like eight years ago, not ten), I'm certainly not surprised that someone else thought of it first. Even so, the only other place I've seen it presented is in one of the Graphics Gems books -- and not until after I'd already submitted the article to DDJ.

Ada95 Fan

Dear DDJ,

In looking at back issues recently, I re-read "Comparing Object-Oriented Languages," by Michael Floyd (DDJ, October 1993), which compared several languages implementing a double-ended linked list class capable of handling multiple object types (a heterogeneous linked list). At the time of the article Ada(83) didn't support run-time binding. I've been working with Ada95 lately and thought I'd write the Ada95 implementation (available electronically; see "Availability," page 3). It uses tagged types, abstract types, Class and Tag attributes, and access parameters, all of which did not exist in Ada(83). It weighs in at approximately 111 lines of code.

Glen Shipley
[email protected]

Correction Noted

Dear DDJ,

In the article "Graphical Embedded Real-Time Systems," by Harry Beker, (DDJ, April 1997) I believe Examples 1(a) and 1(b) were inadvertently reversed.

Timothy Thao Pham
[email protected]

DDJ responds: Right you are, Timothy. Thanks for pointing that out. Our apologies to Harry Beker.

Turing's Textures

Dear DDJ,

I enjoyed Rafael Collantes-Bellido's article on Alan Turing's reaction-diffusion system model for chemical pattern formation in the "Algorithm Alley" column in DDJ, December 1996.

As a fan of graphics programming in general and cellular automata in general, I decided to try a quick-and-dirty implementation of the equations presented, using Microsoft Basic PDS. On the first run, I got some interesting changing patterns, but within a small number of iterations, my program halted with an overflow error. Upon examining Rafael's C source code, I realized that I had not bounded the "concentration" values at a lower limit of zero. I fixed the problem, and my program began to function correctly.

However, looking at Rafael's source, I noticed he calculated the new concentrations "in place" within the A[][] and B[][] matrices. This means that, for example, as you calculate the DiA value for A[2][2], you are using the values for A[1][2] and A[2][1] that have already been changed to their new values.

Strictly speaking, shouldn't the algorithm use the values of A[1][2] and A[2][1] from the previous generation? I note that Rafael correctly saves the old version of A[i][j] in Aold, to be used later when calculating the ReB value after A[i][j] has been updated (ReB = 16.0-Aold*B[i][j];). I suspect that Rafael's program retains its basic function because of the relatively slow change of the cellular pattern after it has reached some kind of dynamic equilibrium. Thank you for a great article!

Jeffrey P. Moore
[email protected]

Rafael responds: Jeff, thanks very much for your comments on my article. Your remark is very interesting, since you are looking at the system as a cellular automata (I assume so because of the terms "generation" and "cellular pattern"). I do not know much about cellular automata, so I am not sure whether the system can be regarded as one or not. The only cellular automaton I know only admits two values for its cells, but as I said, I'm not familiar with this topic. However, Turing did not think of the system as a cellular automata, but as a system of differential equations. What the code does is find the steady-state solution for this system of differential equations. It is similar to the equations for solving an electric circuit, but the steady-state solution is an N×N matrix instead of a single real value. The system starts with random values for the N×N matrix, and these values are changed slowly (as you noticed) to the steady-state solution. So in every iteration, we get closer to this solution. Using the "better" values for A[1][2] when computing A[2][2] simply helps speed up the calculations and saves a lot of memory!

Jeff responds: Rafael, the cellular automata I have worked with generally have a single matrix of cells, with an arbitrary number of states for each cell, and with rules for the next "generation" that use the information of the cell's current state -- plus the state of its neighbors -- to calculate the next generation.

This system comes close to satisfying the criteria for a cellular automaton, with the exception that I have never seen one that maintained two matrices and displayed only one of them.

And yes, I did notice the problem of using a lot of memory to maintain two copies of each of the two matrices. In my particular implementation on a DOS-target machine, this limited me to matrices with a size less than or equal to 64×64.

Another way to address the memory problem is to:

1. Store the two main matrices in the same way that is done now.

2. Assume that we scan the matrices in order, by rows.

3. For each matrix, maintain a two-row "slice" that contains the "old" value of the elements in the current row and the row just above it in the matrix.

4. Compute the "new" value of each element in a row using values from the "slice" (for the elements in the current row and the row above) and using values from the matrix (for the elements in the row below) since those values are still "old."

5. After computing a complete row of "new" values per step 4, update the slice before computing the next row.

Pointing to Zero

Dear DDJ,

In "Usability and Class Library Design," (DDJ, October 1996), Arthur Jolin states, "By definition, a reference always points to something." That's true, and it can point to zero; see Example 1.

Is this perverse? Only if done intentionally.

Thomas Steger
[email protected]

DDJ