LETTERS

3-D Morphing

Dear DDJ,

I really enjoyed the fine article, "Morphing 3-D Objects in C++" by Glenn Lewis (DDJ, July 1994) and would like to congratulate Glenn, as well as discuss a few points with him. How can I get in touch with him?

Ben Allen

Los Angeles, California

DDJ Responds: Thanks for your note, Ben. Glenn is an engineer with Intel's real-time group and can be contacted at glewis @pcocd2.intel.com.

Timing is Everything

Dear DDJ,

I just read Tom Swan's June 1994 "Algorithm Alley" column, where he shows how recursion can be removed by essentially replacing the system stack with a private stack. At the end of the column he says: "I didn't profile any of the code listed here...but removing recursion usually produces a speed boost."

I have read similar statements in many algorithm books, but I have not found any evidence for the general validity of this rule of thumb. Over the years, I have used many techniques to enhance performance, including recursion removal, and I have learned to always time code if time is important. What I have found (in general) is:

1. Tail recursion removal is always beneficial. It is also a very simple adaptation.
2. General recursion removal requires a private stack and routines to deal with this private stack. It depends on the algorithm, the compiler, and the operating system whether you may expect an increase in performance. C has very little overhead for a function call, so recursion can be very fast. C++ and Windows require more function prologue and epilogue, which makes recursion slower.
3. A benefit of recursion routines is that they are very simple. But similar to their nonrecursive brothers, recursive routines can be optimized. Most recursive routines begin by testing whether to exit immediately. A very simple optimization is to move this test before each recursive call; if the recursive function call would exit immediately, there is no need to call the routine.
4. Sometimes you find a nonrecursive routine that does not need a stack. Here you have, in fact, found a completely different algorithm. This algorithm is often much faster then the recursive routine.
5. Don't trust profilers. Use a stopwatch or the internal timer of the computer.

The Right Tool_

Dear DDJ,

I read Jay Frederick Ransom's letter ("Letters," DDJ, April 1994) commenting on P.J. Plauger's "Programming Language Guessing Games" (DDJ, October 1993). I agree with Mr. Plauger, C/C++ is a complex language. Not everybody, unless you have special training, can read this cryptic language. C was written by two excellent professionals (Kernighan and Ritchie) to create an operating system--UNIX. Since C and C++ are actually high-level assemblers, why would you use them to write scientific and mathematical or financial and commercial applications? Why use a plier to tighten a nut if you can use a wrench? Fortran is the correct tool for the first, and Cobol is the correct tool for the second.

Simple programs, like that shown by Mr. Ransom, can be written in any language (he chose C++). Example 1 is the same solution written in Visual Cobol (I must admit that I originally wrote it in Fortran), but with a great difference: I'm sure everybody can read and understand it. [Editor's Note: Executables and related files are available electronically; see "Availability," page 3.] And using his words, note the "simple and elegant'' code used to solve the problem. No tricks, no hidden features; and straightforward, too.

Jaime Orozco-V.

Santafé de Bogotá, Colombia

More on Secure Algorithms

Dear DDJ,

In a recent "Letters" column discussing secure algorithms (DDJ, July 1994), William Hause suggested what's essentially the one-time pad system. Although unbreakable, it produces many security difficulties in practical use--especially with multiple correspondents, where every pair exchanging messages must always use different random keys. If any two messages use the same key, decryption becomes much easier.

All users must take great care not to reuse any part of any key, yet must ensure that the recipient always know where to start. This point is a major problem with the system, exaggerated by the weaknesses of human nature.

Natural random numbers require a high-quality electronic source not available to most people. The British government uses a complex electronic device (ERNIE) to generate the random numbers used for the monthly national-savings-prize draw. A technical article describing the equipment stated that each number combined two electronic sources to avoid any risk of nonrandom output. Additionally, actual output is checked statistically after every use.

The distribution of keys produces a major security problem. How does one ensure--even with a personal messenger--that no one has taken a copy en route? Even sending multiple keys by different routes and combining them for use must always leave some element of doubt.

The most secure methods avoid transmission of any data sensitive to interception. Widely published data, such as new books in the lists of agreed large publishers, easily provide the several numerical values to derive indirectly the multiple seeds necessary for a secure key. Each pair of correspondents agrees--and keeps secret from all others--when to change lists and books and how to calculate the several seeds from each chosen book.

Although every message requires a completely different key, book references may be infrequent. The message date, time, number, and so on can provide--again indirectly--some of the necessary variability in seeds.

A Poisson test provides the most critical test of randomness, sensitive to any trace of sequence repetition. Many computer algorithms pass more-popular tests but fail with a Poisson test. The best methods encipher each bit independently. Check for and avoid correlations between bits in the same sequence, as found with most shift-register designs.

Do not delete zeros from any random key; omission of the expected plaintext characters actually assists decryption.

For any message, there are 128N possible different keys (one is plain language), where N is the number of characters in the message. The best methods approach this limit.

R.G. Silson

Tring, Herts, England

Big Numbers, Cont.

Dear DDJ,

I would like to take you up on an offer which was extended to DDJ readers in the September 1993 issue, page 10. You were responding to Mike Neighbors, who wrote a letter entitled "Searching for Mr. Big Number," in which he asked readers for good references on high-precision arithmetic.

I am the founder of Nth Power Software, a software-development company which specializes in symbolic-algebra applications. Currently, we have a symbolic-algebra programming language called the "Nth Programming Language,'' which runs on DOS- and Windows-based systems. Nth has been under development for several years, and Version 1.0 was released in December of 1993. Nth has a robust, multiple-precision number capability with far more than the 40-decimal-place accuracy mentioned by Mike Neighbors. Its key features include multiple-precision numbers, multivariate rational polynomial procedures, and the capability for you to build your own distributable applications which utilize the full power of the Nth language via the NthDX module.

Lloyd E. Nesbitt,

Nth Power Software

Adair, Oklahoma

Ray Tracing and POV-Ray

Dear DDJ,

As a member of the POV-Team, I was pleased to see Craig Lindley's article, "Ray Tracing the POV-Ray Toolkit" (DDJ, July 1994). While the article was essentially correct for POV-Ray Version 1.0, it contains some outdated information that may cause some confusion with users of the current version.

Craig's article and sample code was based on POV-Ray 1.0. The current version of POV-RAY is 2.2. While the sample code that was provided will run, POV-Ray 2.x must be run in "backwards-compatibility mode" to prevent syntax errors. This mode can be set via the command line or by using the #version 1.0 directive in the scene file itself. More information is available in the POV-Ray documentation.

Also, Drew Wells is still a POV-Team member, but the job of coordinator has been assumed by Chris Young (CompuServe 76702,1655) and inquiries should be addressed to him.

Because of the large number of platforms that POV-Ray can run on, it is advised that downloaders first look for the file POVINF.DOC, which will explain a little about POV-Ray and which files are necessary to get it working on any particular platform. An alternate Internet site for POV-Ray related files is now available at uniwa.uwa.edu.au in the pub/povray directory.

While the article mentioned POVCAD as one possible modeler for the PC, it should be noted that another modeler, Moray, is probably in more common use. There is a great need for a portable modeler for POV-Ray.

There are a couple of DOS modelers, but nothing for non-DOS platforms. Because of POV-Ray's portable nature, it would be extremely desirable to have a freeware portable modeler. Many issues arise from this, some of which have been covered in DDJ, particularly portable GUI issues. I have tried to get a group of Internetters together to work on this, but it's been really tough and I'm not so sure that it'll happen. It'd sure make an interesting DDJ project for someone, though.

Dan Farmer,

POV-Team Member

CompuServe 74431,1075

DDJ Responds: You're absolutely right, Dan. A portable modeler for POV-Ray would be a great project. If any readers are interested in working on such a project, please contact Dan or DDJ.

Example 1: The right tool...

Id Division.
 Program-Id.            TeamPlay.

 Data Division.
 Working-Storage Section.
 01  TeamsTable.
     05  Team Occurs 100 Times, indexed by TeamX, TeamY
                        Pic  X(25).
 01  Temp               Pic  X(25).

 01  NroTeams           Pic  9(3).
 01  LastTeam           Pic  9(3).

 01  Dia                Pic  9(3).

 Procedure Division.
 Begin-TeamPlay.
*----------------------------------------------------------------*
*    Read in Team names... And no more than expected!            *
*----------------------------------------------------------------*
     Display "Enter Teams Names... Ends with *"
     Perform With Test After Varying NroTeams From 1 By 1 Until
          Team (NroTeams) (1:1) Equal "*" or
          NroTeams Greater 100
          Accept Team (NroTeams)
     End-Perform
*----------------------------------------------------------------*
*    Delete the "*" Team and calculate an even number of teams   *
*----------------------------------------------------------------*
     Subtract 1 from NroTeams
     Compute LastTeam = Function Integer ((NroTeams + 1) / 2) * 2
*----------------------------------------------------------------*
*    Print out playing schedule                                  *
*----------------------------------------------------------------*

     Perform Varying Dia From 1 by 1 Until
          Dia Greater LastTeam - 1
          Display "Day " Dia

          Set TeamY to LastTeam
          Perform Varying TeamX from 1 by 1 Until
               TeamX Greater TeamY
               Display Team (TeamX) " .VS. " Team (TeamY)
               Set TeamY Down by 1
          End-Perform
*----------------------------------------------------------------*
*         Rotate Teams for next day                              *
*----------------------------------------------------------------*
          Move Team (LastTeam) to Temp
          Perform Varying TeamX from LastTeam by -1 Until
               TeamX Equal 2
               Move Team (TeamX - 1) to Team (TeamX)
          End-Perform
          Move Temp to Team (2)
     End-Perform
     Stop Run.

Copyright © 1994, Dr. Dobb's Journal