Path: utzoo!attcan!uunet!husc6!cca!g-rh
From: g-rh@cca.CCA.COM (Richard Harter)
Newsgroups: comp.lang.misc
Subject: Re: fft routine (was Re: m88000 benchmarks)
Message-ID: <30298@cca.CCA.COM>
Date: 3 Jul 88 08:41:03 GMT
References: <1359@claude.oakhill.UUCP> <12295@mimsy.UUCP>
Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 67

In article <12295@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes:

>The context of the following quote is benchmarking; in this case one
>is, of course, concerned with running existing code quickly.  Yet the
>code below is all too typical: there are no comments; the variables
>have names that tell nothing.  In short, the code is unmaintainable.

	.... fft routine deleted ....

The deleted code looks like a straight transliteration of a fortran
fft routine.  It is not as bad as Chris says -- if you are used to
the nomenclature conventions commonly used in fortran coding and know
how an fft works.  Thus xr and xi are *obviously* the real and imaginary
parts of the data, c and s are *obviously* cosine and sine, and wr and wi
are *obviously* roots of unity. 

>Can you tell what is going on?  If you are familiar with FFTs, I
>suppose it becomes clear enough after a while.  If not, it is a rather
>painful process to discover that the inner loop is really just
>
>	complex x[n], w[n], diff, half;

>	for i from 0 to n-1 step n/2^k:
>		half = i + n/2^(k+1);
>		diff = x[i] - x[half];
>		x[i] += x[half];
>		x[half] = diff * w[j * 2^k];
>	rof

>Unfortunately, C does not have a `complex' datatype.  The task is
>better suited to C++, or some other language with both shifts (which
>are lacking in FORTRAN) and complex expressions.  But I think one can
>do better than the code quoted with `>' above, without losing
>efficiency.  Here is one such attempt:

>	typedef struct complex {
>		float	re;
>		float	im;
>	} complex;

and Chris goes on to define macros for complex multiplies and adds.
He then reworks the code to use complex as a type with macro calls
to do the algebra.

Clearly this is a matter of style and what one is used to and so on.
However I find the original (which he dislikes) better than the proposed
substitute.

First a technical point.  In the original the real and imaginary parts are
passed separately; Chris replaces them with a structure array.  There are
reasons for having separate arrays.  The reasons don't matter -- what
does matter is that you don't change interfaces for strictly internal
reasons.

My reaction is that the algebra in the original is clear, immediately
recognizable, and easy to read; for me the macro calls obscure the code
rather than making it clearer.  I suspect, perhaps wrongly, that this will
regularly be the case with people who work with that kind of math.  This
says to me that the notion of clarity is not absolute.  

The major flaw in the original, as I see it, is simply that it lacked any
documentation.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.