Reply by glen herrmannsfeldt●February 21, 20082008-02-21
Steven G. Johnson wrote:
> Certainly that is practical to do as a simple check; Gordon made a
> similar suggestion. (Of course, the error that many students make in
> applying that suggestion is that they compare to the analytical
> Fourier integral that is tabulated in their textbooks, not to the
> analytical DFT; I can't count how many times someone has posted on
> Usenet that their FFT routine is not working because the transform of
> a Gaussian is not a Gaussian, etc.)
I thought I did that once. The transform has to be long enough that
it actually looks like a gaussian, and it has to be centered on zero.
Also, those negative frequencies come out again.
-- glen
Reply by Steven G. Johnson●February 20, 20082008-02-20
On Feb 19, 4:36 pm, Mark Borgerding <m...@borgerding.net> wrote:
> For many libraries,(kissfft included) to maximize the error-to-signal
> ratio, simply set the lowest significant bit of one input sample and
> leave the rest of the input zeros -- call that your signal. That single
> lsb is not likely to contribute enough on its own to make any non-zero
> output, making the error energy equal to the signal energy -- the
> maximum relative error of 1.0.
Remember, I specified that you should maximize the error over a fixed
L2 norm=1 of the signal, so your suggested signal doesn't have that
property. What you are doing is loosely analogous to choosing a
signal that is close to overflow/underflow in floating-point; it was
precisely to exclude such obvious cases that I suggested one constrain
the signal norm.
Steven
Reply by Mark Borgerding●February 19, 20082008-02-19
Steven G. Johnson wrote:
> On Feb 19, 11:16 am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>> One interesting problem that occurs to me is to ask what is the
>> "worst" input, i.e. the input that gives the worst errors in some
>> norm.
>
> To be more precise, since you could always get a big error just by
> making your numbers so large they approach overflow or something like
> that, let me pose the question (for fun and profit): can you find a
> vector of inputs x (exactly representable in your floating-point) with
> L2 norm |x| = 1 that maximizes the root-mean-square relative error
> |FFT(x) - exactDFT(x)| / |exactDFT(x)|
> for a given FFT implementation, where all expressions except FFT(x)
> are in exact arithmetic? (Of course, assuming a unitary DFT
> normalization, the denominator is |exactDFT(x)| = |x| = 1.)
>
> Steven
Steven,
That's a very interesting question. Even more so considering it comes
from someone who is so well versed in the state of the FFT art.
I agree it would be very implementation specific. You'd need to consider
not only the immediate precision of a single addition, but also the
cumulative effect it has on subsequent operations.
... for floating point FFTs ...
In order to find such a worst-case vector, you'd need to maximize the
energy that gets lost due to
a) limits of precision in addition/subtraction and
b) the amplification of those errors in multiplication.
When two floats get added or subtracted, whichever has the greater of
the two exponents drives the precision of the result.
Multiplications do not *add* much error per se, but they do amplify
errors from previous steps.
... for fixed point FFTs ...
Finding such a vector may be pretty easy.
For many libraries,(kissfft included) to maximize the error-to-signal
ratio, simply set the lowest significant bit of one input sample and
leave the rest of the input zeros -- call that your signal. That single
lsb is not likely to contribute enough on its own to make any non-zero
output, making the error energy equal to the signal energy -- the
maximum relative error of 1.0.
If the FFT library allows the possibility of overflow/saturation, you
can craft vectors to cause such overflow.
If the fft algo uses block floating point, then figure out ways to make
the blocks always have very few points that are maximal magnitude and
the rest are small enough so they will suffer precision loss, but big
enough to contribute handily to the overall error.
Again -- very implementation-specific.
-- Mark Borgerding
Reply by Steven G. Johnson●February 19, 20082008-02-19
On Feb 19, 11:16 am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> One interesting problem that occurs to me is to ask what is the
> "worst" input, i.e. the input that gives the worst errors in some
> norm.
To be more precise, since you could always get a big error just by
making your numbers so large they approach overflow or something like
that, let me pose the question (for fun and profit): can you find a
vector of inputs x (exactly representable in your floating-point) with
L2 norm |x| = 1 that maximizes the root-mean-square relative error
|FFT(x) - exactDFT(x)| / |exactDFT(x)|
for a given FFT implementation, where all expressions except FFT(x)
are in exact arithmetic? (Of course, assuming a unitary DFT
normalization, the denominator is |exactDFT(x)| = |x| = 1.)
Steven
Reply by Rune Allnor●February 19, 20082008-02-19
On 19 Feb, 16:31, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Feb 19, 9:13 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>
> > > On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > I agree with you that it is dangerous to assume anything from
> > > > students (or anybody else, for that matter). On the other hand,
> > > > one can almost never *force* other people to do things in a
> > > > certain way
>
> > > I'm confused. �Who is talking about "forcing" someone to do anything?
> > > We were just discussing how to answer a certain online question in a
> > > clear and useful way. �How would it even be possible to "force"
> > > someone to do something in an online forum?
>
> > Gordon's first post seems to have been based on pedagogical
> > principles similar to those outlined by me. You responded
> > with a very technical reply based on what might be expected
> > from students. The only contexts where such a highly technical
> > reply might be relevant are
>
> I responded that Gordon's answer was misleading, because the student
> asked how to measure X and Gordon gave a suggestion that would
> actually measure Y, not X.
...
> I gave additional information and references in response to a
> question, and I clarified a point that was arguably misleading; I'm
> really baffled regarding how this led to a long lecture about not
> "forcing" students.
Here is what you wrote previously and that I reacted to:
"In my experience, it's unreliable to assume that students will check
their answers in multiple redundant ways. They find one way that
seems to work, and stop there. So if you tell students to compare to
the O(N^2) algorithm, without warning them that the latter is less
accurate, it's quite likely they will just compare the two algorithms
for random inputs and stop there."
To me, this is text not about Gordon giving wrong or misleading
answers. This text is about your expectancy that students will not
do a complete investigation unless 'encouraged' (in practice,
that means 'forced') to do so. In my experience, it is no
point to suggest how to go beyond the basics ('incomplete'
or 'misleading') tests until one sees that whoever is ready
to go there.
Rune
Reply by Steven G. Johnson●February 19, 20082008-02-19
On Feb 19, 10:52 am, Jerry Avins <j...@ieee.org> wrote:
> Nobody commented on my suggestion, which was to transform a function for
> which the result was precisely known, and to compare the computed result
> to the known one. Is it practical?
Certainly that is practical to do as a simple check; Gordon made a
similar suggestion. (Of course, the error that many students make in
applying that suggestion is that they compare to the analytical
Fourier integral that is tabulated in their textbooks, not to the
analytical DFT; I can't count how many times someone has posted on
Usenet that their FFT routine is not working because the transform of
a Gaussian is not a Gaussian, etc.)
(Most published accuracy tests seem to prefer random inputs, to give
error statistics over a desired distribution, however, as opposed to a
handful of special inputs whose DFTs are known. But of course, it all
depends on what question you are interested in: accuracy for what
inputs?)
One interesting problem that occurs to me is to ask what is the
"worst" input, i.e. the input that gives the worst errors in some
norm. Of course, the precise answer probably depends on the FFT
algorithm/implementation, the compiler, and the floating-point
hardware, but I wonder if there are certain inputs that are
consistently "bad"? (Of course, since there is an O(log N) error bound
as proved by Gordon in 1966, it can't get *that* bad.) Also, I wonder
if there is a straightforward way, given an FFT routine, of finding
such a worst-case input, e.g. by throwing it at an optimization (err,
pessimization) algorithm, or if the problem has too many local minima
for this to be practical. Probably for the DC element, at least,
where the output is just a (cascade) summation, the identification of
the worst case inputs has been studied to some extent. Anyway, just
pondering aloud.
Steven
Reply by Jerry Avins●February 19, 20082008-02-19
Steven G. Johnson wrote:
> On Feb 19, 9:13 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>> On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>>
>>> On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>>>> I agree with you that it is dangerous to assume anything from
>>>> students (or anybody else, for that matter). On the other hand,
>>>> one can almost never *force* other people to do things in a
>>>> certain way
>>> I'm confused. Who is talking about "forcing" someone to do anything?
>>> We were just discussing how to answer a certain online question in a
>>> clear and useful way. How would it even be possible to "force"
>>> someone to do something in an online forum?
>> Gordon's first post seems to have been based on pedagogical
>> principles similar to those outlined by me. You responded
>> with a very technical reply based on what might be expected
>> from students. The only contexts where such a highly technical
>> reply might be relevant are
>
> I responded that Gordon's answer was misleading, because the student
> asked how to measure X and Gordon gave a suggestion that would
> actually measure Y, not X.
>
> This has nothing to do with "gentle" vs. "forcing" pedagogical
> approaches or "technical" versus "non-technical". It has to do with
> not giving trick answers.
>
> I gave additional information and references in response to a
> question, and I clarified a point that was arguably misleading; I'm
> really baffled regarding how this led to a long lecture about not
> "forcing" students.
Steven,
These days, Rune spends his time aboard ship, much of it (I'm guessing)
with little to stimulate his mind. Why not put it down to sensory
deprivation of the intellectual kind and move on?
Nobody commented on my suggestion, which was to transform a function for
which the result was precisely known, and to compare the computed result
to the known one. Is it practical?
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Steven G. Johnson●February 19, 20082008-02-19
On Feb 19, 9:13 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>
> > On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > I agree with you that it is dangerous to assume anything from
> > > students (or anybody else, for that matter). On the other hand,
> > > one can almost never *force* other people to do things in a
> > > certain way
>
> > I'm confused. Who is talking about "forcing" someone to do anything?
> > We were just discussing how to answer a certain online question in a
> > clear and useful way. How would it even be possible to "force"
> > someone to do something in an online forum?
>
> Gordon's first post seems to have been based on pedagogical
> principles similar to those outlined by me. You responded
> with a very technical reply based on what might be expected
> from students. The only contexts where such a highly technical
> reply might be relevant are
I responded that Gordon's answer was misleading, because the student
asked how to measure X and Gordon gave a suggestion that would
actually measure Y, not X.
This has nothing to do with "gentle" vs. "forcing" pedagogical
approaches or "technical" versus "non-technical". It has to do with
not giving trick answers.
I gave additional information and references in response to a
question, and I clarified a point that was arguably misleading; I'm
really baffled regarding how this led to a long lecture about not
"forcing" students.
Regards,
Steven G. Johnson
Reply by Rune Allnor●February 19, 20082008-02-19
On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > I agree with you that it is dangerous to assume anything from
> > students (or anybody else, for that matter). On the other hand,
> > one can almost never *force* other people to do things in a
> > certain way
>
> I'm confused. �Who is talking about "forcing" someone to do anything?
> We were just discussing how to answer a certain online question in a
> clear and useful way. �How would it even be possible to "force"
> someone to do something in an online forum?
Gordon's first post seems to have been based on pedagogical
principles similar to those outlined by me. You responded
with a very technical reply based on what might be expected
from students. The only contexts where such a highly technical
reply might be relevant are
1) Where the student is *known* (or at least would be expected)
to have relevant competence to handle the reply offered.
2) Where the instructor has the 'power tools' needed to
force the student in a particular direction.
At the time Gordon wrote his first reply, the technical
proficiency of the OP was not known, although subsequent
posts by the OP seem to indicate a certain level of both
knowledge and skills. But again, at the start of this
thread, this was not known.
The point I am trying to make is that one starts out
in 'gentle' ways on a general basis, and only follows
up with the highly technical stuff after one is sees
that the oposite party is able to handle it.
Starting to feed technical details too soon is not
useful unless one can force things to be done in a
certain way (and more often than not, it's not very
useful for teaching even then).
Rune
Reply by Steven G. Johnson●February 19, 20082008-02-19
On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> I agree with you that it is dangerous to assume anything from
> students (or anybody else, for that matter). On the other hand,
> one can almost never *force* other people to do things in a
> certain way
I'm confused. Who is talking about "forcing" someone to do anything?
We were just discussing how to answer a certain online question in a
clear and useful way. How would it even be possible to "force"
someone to do something in an online forum?