LETTERS

C and History

Regarding Al Stevens' inquiry as to the choices behind the current structure of C parameter declarations ("C Programming," DDJ, December 1994).

Functions in K&R C had arguments typed with parameter-declaration, allowing Example 1(a). The argument would effectively be "moved" into register storage by the compiler. Prior to this arrangement (predating K&R C), you had to do this manually; see Example 1(b). In other words, this was an improvement in the language. (Early C compilers used many compromises of this ilk.) ANSI C, of course, uses Example 1(c).

When ANSI C came on the scene, compilers were allowed to intermix K&R argument-declaration syntax with that of ANSI for backwards compatibility. Declaration semantics thus must be interchangeable. (All ANSI compilers will balk at this.)

With declaration syntax set, prototypes must again use the same syntax, since they may be generated by automatic means. (It would be unwise to have different ones, although in effect, compilers restrict you to a "specifier qualifier list.") However, in the case of prototypes, the point Al was making is well taken.

In fact, we could take this inquiry further. For example, what if we were to extend the language and add new storage classes? Might these be desirable to include in a prototype? For that matter, could there be an advantage in allowing a function prototype to enforce a "register" storage class in a prototype (meaning that the argument was always passed via register)?

One of the great strengths of C is that it permitted an implementor a good degree of latitude in exploiting machine architecture. Unlike PL/I, C attempts to be more of a high-level assembler than a high-level language. While PL/I allowed a rich set of operations to be embedded in the language itself, use of those features could involve considerable run-time overhead that the programmer needed to be aware of. However, with C, all of the operations typically matched the machine language almost one for one. (Many PL/I compilers of the time would detect and "fix" typing errors, allowing you to run programs with significant errors in the code. This went loggerheads with the obsessive type-checking of Pascal, which would flat-out refuse to execute any imperfect code--so much for the differences between the then "old" and "new" schools.)

In sum, C's role as a language is tightly tied to low-level implementation details, so that the syntax and semantics of variables must be fluid enough to match machine characteristics of the future. This is completely unlike "big" high-level languages, which attempt to offer versatility for the price of the same old complexity we've seen before.

Incidentally, what Al describes as "C minus minus" reminds me a lot of the B programming language. (B, the predecessor of C, was an inspired approximation of the Bootstrap Cambridge Programming Language, BCPL.) B was revived by Mark Horton (then at the University of California at Berkeley) for his thesis work on a language editor (bedit) that merged the concepts of text editor and incremental compiler. The language was simplified from C to allow for incremental parsing and "code" generation as the program was being composed in the editor (thus, it always was immediately syntax-checked and runable). In effect, it worked much like Microsoft's Visual products (which may not take the concept quite as far).

The code was part of past Berkeley BSD releases (in the /usr/src/contrib directory) and is probably still available on the Internet.

Bill Jolitz

Oakland, California

More FFTs

Dear DDJ,

In his article "Faster FFTs" ("Algorithm Alley," DDJ, February 1995), Iwan Dobbe describes a fast radix 2 FFT algorithm for complex data. It is good to see some numerical-methods articles in DDJ; I hope we will see more. Here are a couple of minor changes that can be used to improve speed and accuracy.

A small improvement in speed may be had by noting that in the routine Shuffle2Arr data is only swapped if the bit-reversed number is greater than the index. This means that you can avoid the unnecessary calls in Example 2(a) by using Example 2(b). This works because all the numbers after 2^b-2^((b+1)/2) will become smaller (or remain the same) when bit reversed. Unfortunately, the savings are not great because the array shuffle is a minor component of total time. I liked the idea of tabulating the sin and cos coefficients.

The second improvement involves the best way to generate the Q^k phase factors by recurrence relation. This is worth optimizing because with large transforms, the numerical rounding errors accumulate quickly. Classical wisdom is to use double precision for the Q^k relations. Starting from Example 2(c) and using the identity in Example 2(d) instead of using cos(x) directly, you can minimize rounding errors, as in Example 2(e).

Finally, and most interesting, because the coefficients have been stored in a table, it is possible to optimize them to minimize the rms error in the FFT phase factors, allowing for real truncation. This has to be done on the target hardware platform.

Basically the idea is to minimize the difference between phase factors computed by recurrence and the true trigonometric functions. To do this, work out all the exact phase factors once using double-precision, standard trigonometric functions, then truncate to real precision and save them in arrays TQr[], TQi[]. Set initial values for s, s2, Qr[0], and Qi[0]. Generate Qr[], Qi[] using the recurrence formulas. Compute the chi-squared error in Example 2(f). Then use any minimization routine that depends only on function evaluation (that is, Golden section search) to optimize chi-squared by varying the initial starting values and recompute Qr, Qi (a search range of +1e-6 is plenty). For example, calculated on a 486DX2, the chi-squared error made by using the recurrence relations instead of explicit trig functions works out as illustrated in Table 1.

In other words, by optimizing the coefficients, you can decrease the rms errors by a factor of 60 for long transforms (=1.8 extra sig. fig.). Just put the optimized values for s and s2 into the coefficient tables. It is only worth optimizing if you will compute a lot of big FFTs. This is a useful gain in accuracy for signal-processing work.

It is also worth mentioning that many experimental datasets are real, rather than complex data, and there is a useful trick to transform a real dataset to a complex conjugate symmetric form. (See, for example, Numerical Recipes in C.)

Martin Brown

East Rounton, England

Interoperable Objects

Dear DDJ,

I read with interest the articles in Dr. Dobb's Special Report on Interoperable Objects (Winter, 1995). As a developer in a large corporation, I am very interested in choosing a technology to rebuild our applications for the hardware of today and tomorrow. We have found out the hard way that it is impossible to keep a business-application portfolio up to date without a great deal of reuse. The easiest way to write a new transaction may be to copy an old one, but it is impossible to keep hundreds of them up to date with the needs of the business.

I am being asked to deliver new business functions to the users within a couple of weeks of the request. If someone is already marketing an object with the function I need, then there is no problem. But what if the best available object has only 90 percent of the function? What if I need to modify an object in some way? What if I need to develop it from scratch?

I look for a few fundamental criteria in a software technology. Can it do what I want? How many lines of code will I have to write? How independent are the objects? How likely is it to succeed in the marketplace?

I would give Microsoft OLE a high score on the last point. I expect that it will not be too long before I use some OLE components in a business application. But regardless of what Microsoft says, I believe that object-oriented technology with inheritance is the easiest way to reuse code. If an object has 90 percent of the function I need, then I get all that function with a few lines of code. I only need to write the 10 percent that is different. In my case, transactions, a large portfolio of similar objects, makes this especially powerful.

The biggest shortcoming of object-oriented development tools has been the matter of independence. With SOM offering binary compatibility between different versions of an object, this problem is reduced. I can modify a SOM object that I bought without having access to its source code. I write a new object that inherits from the original one and override the methods I need to modify. The base class or the derived class can be changed without having to recompile the other.

In short, Microsoft can say "The problem with..." all it wants. SOM seems to me to be the best available technology for me to begin to build systems that can keep up with the needs of the business.

Ron Brubacher

London, Ontario

Ewoes

Dear DDJ,

Regarding "Swaine's Flames" in the March, 1995 DDJ: In medieval times, church was people's television, rock concert, and ball game all in one. Not only had the sermons (and writings and teachings) gotten self referential (religion talking about religion) but they were in Latin, a language most people did not even understand. Yet, people kept going to the show that the church gave.

The most powerful institution of its day had created a totally artificial, self-referential reality in which people actually lived--they thought those things were real, and they saw their real lives in terms of these artificial creations.

Wilhelm Sarasalo

pacsoft@netcom.com

Dear DDJ,

I'm sorry to hear that Michael Swaine's elife collapsed under the estrain of the eresponses to his emoticontest. If I had had any suspicion that he was still taken of the madness that he could, as an ecelebrity, expect to eread and eanswer even a modest portion of his email, I would have eoffered a more friendly and voluble eletter than my (correct, eattached) eentry of November 8.

Upon reading the March 1995 "Swaine's Flames," I have decided to ewrite this emissive and esend it redundantly to you and the DDJ editors, to help limit the erisk that you might elose this one!

Even if this isn't the right answer, the emoticons bear an uncanny resemblance to Siskel and Ebert.

Lyle Wiedeman

wiedeman@altair.acs.uci.edu

Example 1: C and History.

(a) foo(a)
      register int a;
    {
      ...
    }

(b) foo(a)
      int a;
    {
      register int ra;
      ra = a;
      ...(code uses ra instead of a)
    }

(c) foo(register int a)
    {
      ...
    }

Example 2: More FFTs.

(a) do
    {
        N = N*2;
        bitlength = bitlength-1;
    }  while (bitlength >0)
    for (IndexOld = 0; IndexOld <= N-1; IndexOld++)
    {....

(b) N =  (1<<bitlength) - (1<<((1+bitlength)/2));
    for (IndexOld = 0; IndexOld < N; IndexOld++)
    {....

(c) c = cos(x); s = sin(x);  /* from table */
    temp = Qr;
    Qr   = Qr*c - Qi*s;
    Qi   = Qi*c + temp*s;

(d) cos(x) = 1 - 2.(sin(x/2))^2

(e) s2 = 2*(sin(x/2))^2 ;   /* from table - replaces c */
    temp = Qr;
    Qr   = Qr - Qi*s - Qr*s2;
    Qi   = Qi + temp*s - Qi*s2;  /* note this adds two extra
                                             subtractions */

(f) for (i=0; i<= N; i++)
    {
    dr = (TQr[i]-Qr[i]);
    di = (TQi[i]-Qi[i]);
    chisq = chisq+ dr*dr + di*di
    }

Table 1: More FFTs.

Size       Original (c,s)  Modified (s2,s)  Optimized (s2,s)
   28        1.05E-11         5.83E-12       4.06E-14
 1024        6.90E-10         4.49E-10       2.17E-13
16384        5.83E -7         1.10E-7        1.49E-10