[Kst] [Bug 87447] New: pass filters are very inefficient for some filter lengths

[netterfield at astro.utoronto.ca]

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
      
http://bugs.kde.org/show_bug.cgi?id=87447      
           Summary: pass filters are very inefficient for some filter
                    lengths
           Product: kst
           Version: unspecified
          Platform: unspecified
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: NOR
         Component: general
        AssignedTo: kst kde org
        ReportedBy: netterfield astro utoronto ca


Version:           0.99-devel (using KDE 3.2 BRANCH >= 20040204, Mandrake Linux Cooker i586 - Cooker)
Compiler:          gcc version 3.3.2 (Mandrake Linux 10.0 3.3.2-6mdk)
OS:                Linux (i686) release 2.6.3-7mdk

The pass filters use 'gsl_fft_real_transform' to fft the data.

>From the GSL documentation for this function:
"Efficient modules are provided for subtransforms of length 2, 3, 4 and 5. Any remaining factors are computed with a slow, O(n^2), general-n module. "

Consequently, for many vector lengths, the transform will become catestrophically slow - eg, 
NS = 199981 (ie, 10000 frames at 20 samples per frame vs index with 1 sample per frame) has none of the magic factors, so the vector will be transformed with an n^2 algorithm.  200001 samples (10001 frames) is ~9x faster, since it is dividable by 3, but is still very slow!

The correct behavior is to use well chosen padding (eg, a linear extrapolation) up to a multiple of 2,3,5....