Dear DDJ,
I really enjoyed Bruce Schneier's article "The GOST Encryption Algorithm" (DDJ, "Algorithm Alley" January 1995). Indeed, after taking a cryptography course, I decided to further investigate GOST. In a copy of (the translation of) the Russian standard, I noticed a slight error in Schneier's description of the algorithm. Schneier notes that:
...the outputs of the eight S-boxes are recombined into a 32-bit word, and then the entire word undergoes an 11-bit circular shift left, towards the higher-order bits. Finally, the result is added modulo 232 to the left half to become the new right half, and the right half becomes the new left half.
And later on, that:
...DES uses XOR to add the key to the right half and to add the right half to the left half; GOST uses addition modulo 232 for both these operations.
However, according to the standard, although addition modulo 232 is indeed used to add the key to the right half, the result of the S-box substitution rotated left is XORed with the left half, and not added modulo 232.
Please note that the code included with the article is correct. A copy of the standard is available at gopher://idea.sec.dsi.unimi.it/11/crypt/docs
Riccardo Pucella
McGill University
pucella@cs.mcgill.ca
Dear DDJ,
I enjoyed Michael Swaine's "Programming Paradigms" column (DDJ, June 1995) that discussed Douglas Hofstadter's book Fluid Concepts and Creative Analogies. I am looking forward to finding enough time to read the book. I have wondered for decades about the significance of problems which have an infinite number of logically correct solutions but only one "agreeable" solution. My favorite is to ask someone to give the next number in the sequence: 1,2,4,8,16,.... If your subjects give the agreeable solution 32, you then tell them that their answer is pretty good, but you will help them by giving them the generator for this sequence so that they may work it out for themselves.
The generator for this sequence is the "cutting the cake problem." You begin with a perfectly round cake. You mark off n equispaced points on the perimeter, then make perfectly straight cuts between every pair of points, then count the number of pieces of cake.
If your subjects bother to do this, they will get the solution:
Number of points:123456
Number of pieces:12481630
It isn't difficult to prove that 32 is the wrong solution; simple symmetry requires that the solution be divisible by 6.
W.R. Ayers
Los Altos Hills, California
Dear DDJ,
I entered, compiled, and executed the PList program by Paul Pukite published in the "Letters" section (DDJ, July 1995) and found line 4 in error. It should read: type Element is access all Item'Class; in the original, all was missing.
I look forward to seeing Ada 95 articles and programs in future issues.
John J. Cupak, Jr.
Nashua, New Hampshire
jcupak@isd99.sanders.LOCKHEED.COM
DDJ responds: Thanks for the correction, John. For information on Ada 95, be sure to check out David Moore's article in this issue.
Dear DDJ,
I would like to make a few comments about Jonathan Finger's article "Lightweight Tasks in C" (DDJ, May 1995). Although the approach Jonathan used will probably be sufficient in most cases, I find it to have some major disadvantages:
This scheme may be elaborated into a complete module for starting and stopping threads with stacks of user-definable sizes. In fact, I have used it to implement a portable version of a C++-based multitasking kernel.
Stig Kofoed
Herlev, Denmark
stk@craycom.dk
DDJ responds: Watch for Stig's article "Portable Multitasking in C++" in an upcoming issue of DDJ.
Dear DDJ,
In the August 1995 "Algorithm Alley," Peter Pearson reports on Leonard M. Adleman's article "Molecular Computation of Solutions to Combinatorial Problems" (Science, November 11, 1994). From my perspective, there appear to be several holes in Adleman's research, at least as described by Pearson.
For instance, Adleman's approach to the Directed Hamiltonian Path Problem is described as: "Given a map showing many cities and many one-way roads connecting cities, find the shortest itinerary that starts at City A, ends at City Z, and passes through every other city exactly once." The usual assumption is that the one-way roads are of different lengths. While this is not always true (consider subway or bus fares as the "length"), without it the task becomes almost trivial: Any complete path is the same length as any other. There is no mention of encoding length in the DNA (might "introns" be used? [Is the giant sea slug the solution to a problem?] If so, Adleman would have to do the steps in reverse order: First isolate the strings that pass through all the cities, then use electrophoresis to find the shortest. Another step would be needed to check that no city was duplicated).
Another difficulty is that, at heart, the procedure is still a search through randomly generated cases. If all of the DNA fails the testing, it may be that incomplete stirring is to blame and not the lack of a solution (pun intended). The large number of molecules simply provides a feasible way of generating an immense number of cases quickly.
Finally, doesn't the difficulty still favor the code maker over the code breaker? If the code maker uses one gram of DNA, wouldn't the code breaker need 10**18 grams?
Maybe the secret of the Universe is 43.
James Pendzick
nsrjwp4@mgic.com
Dear DDJ,
If I correctly understand Peter Pearson's article "Biochemical Techniques Take on Combinatorial Problems" ("Algorithm Alley," DDJ, August 1995), the technique might be summarized as "make really a lot of candidate molecules, and then select the ones that might be solutions." To quote from the article, "the number of guesses that can be tested...is limited....by the number of DNA molecules you can handle. Since a gram of DNA might contain 1018 smallish molecules..." it sounds like a lot, but the Knapsack Problem mentioned has 1030 or so possible solutions, meaning 109 kilograms of DNA for one solution, given an even distribution. I don't know the density of a DNA solution, but 109 kilograms of water would be a cube 100 meters on a side if I recall the physical constants approximately. It might not be enough for your pet whale, but probably too big for the back yard.
Of course, the Knapsack Problem for 100 points is small as such problems go. How about a Traveling Salesman problem for 1000 points (easily found in circuit-board assembly)? This is roughly 4e2567; that is, "4" followed by 2500 zeros. This problem can routinely be solved within a few percent of optimality by the best algorithms on a fairly fast computer in a few seconds.
David X. Callaway
dxc@mitron.com
Dear DDJ,
I am a hardware design engineer from Topmax and an avid reader of DDJ. Our company develops ICE, plotters, printers, and network boards.
I particularly enjoyed the article "68HC05-based System Design," by Willard J. Dickerson (DDJ, August 1995). However, when I tried to get in touch with Willard using the e-mail address in his bio, mail returned the message "Unknown user." Could you please give me Willard's correct e-mail address.
Joel Carvajal
Topmax Philippines Inc.
joel@polgas.tds.pfi.net
DDJ Responds: Thanks for pointing out that we dropped an "l" from the e-mail address, Joel. Our apologies to you, Willard, and to other readers. Willard's correct e-mail address is willd@amcu-tx.sps.mot.com.
Dear DDJ (DDDJ),
Lately, I see an increase (INC) in the use of nonsensical abbreviations (NAs) in computer "literature" (CL). I read an issue of Hewlett-Packard (HP) Professional (a BS sales 'zine): I (I) counted about 43 uses of NAs on two (2) pages. The writer actually defined an NA without using it subsequently!
For examples, MDD (multidimensional database), non-MDD (nonmultidimensional database), SI (systems integrator), IT (undefined), VAR (undefined), ISV (undefined), GUI (graphical/generic? user interface), BPR (business process reengineering), and SFA (sales force automation).
My question is this: Are these articles not meant to (2 too (2 2 eh ...)) be read, or are these people just showing off? And if the latter, what is it they are showing off?
I'm not sure why people do this, but I will suggest a few answers:
Utrecht, Holland (NL)
E.H.Terwiel@inter.NL.net
Dear DDJ,
We really enjoyed seeing a photo of our game Blood on the cover of Dr. Dobb's Sourcebook of Games Programming (May/June 1995). As you can imagine, Kevin Kilstrom, our senior artist, was particularly thrilled.
Readers might be interested in details about Blood (which should be published by Apogee's 3D Realms Division and FormGen later this year). Blood is a 3-D action/horror game using rendering technology similar to DOOM's, but with overlapping map areas, bridges, sliding and rotating walls and floors, translucencies, mirrors, and numerous other effects. The commercial version of the game will likely contain over 15 MBs of 256-color artwork. Blood will also have a top-end resolution of 1600x1200 for those happy Pentium owners.
Nick Newhard
Q Studios
Redmond, WA 98052
nnewhard@qstudios.com
Example 1: Lightweight tasks.
(a)
#include <setjmp.h>
#include <stdio.h>
jmp_buf jmp_main, jmp_cor;
void cor_to_main( void )
{
if( setjmp( jmp_cor ) == 0 )
{
longjmp( jmp_main, 1 );
}
}
void main_to_cor( void )
{
if( setjmp( jmp_main ) == 0 )
{
longjmp( jmp_cor, 1 );
}
}
void coroutine( int n )
{
int i;
if( n > 0 )
{
coroutine( n - 1 );
}
else
{
i = 0;
printf( "coroutine start\n"
);
for( ;; )
{
cor_to_main();
printf( "%d. coroutine\n",i++ );
}
}
}
int main( void )
{
int i;
printf( "main start\n" );
if( setjmp( jmp_main ) == 0 )
{
coroutine( 200 );
}
else
{
for( i = 0; i < 5; i++ )
{
printf( "%d. main\n", i );
main_to_cor();
}
printf( "main stop\n" );
}
return( 0 );
}
(b)
main start
coroutine start
0. main
0. coroutine
1. main
1. coroutine
2. main
2. coroutine
3. main
3. coroutine
4. main
4. coroutine
main stop
Copyright © 1995, Dr. Dobb's Journal