[Vorbis-dev] Butterflies in mdct.c

[Monty]

On Wed, Jan 26, 2005 at 05:49:15PM +0100, petshome at atlas.cz wrote:

> In mdct.c there's some functions including some-point butterfly. In
32-point and 16-point there are calling of smaller-point function
everytime twice on each half of data. When I looked on it I found
that's just linear algebra. So it can be rewritten to matrix
multiplication.

This takes an O(n log2(n)) operation and makes it O(n^2); That's not
an optimization.  Matrix multiplication is a powerful concept in
theory and nearly always the last resort in practice.  Also, the
smallest butterflies are better than O(n log2 (n)) because of identity
cases.

>Can anyone prove that this can't be faster? Even there's possibility
>to use MMX when working with matrixes.

It's unlikely enough that I don't want to take it seriously unless
someone has an example in hand of it running faster.

Monty