# DST using FFT routine

Please can you help me with my problem? On Wikipedia, in article Discrete sine transform, this is written (chapter Computation):

"Although the direct application of these formulas would require O(N2) operations, it is possible to compute the same thing with only O(N log N) complexity by factorizing the computation similar to the fast Fourier transform (FFT). (One can also compute DSTs via FFTs combined with O(N) pre- and post-processing steps.)"

I would like to compute sine discrete fourier transformation and would like to use the FFT algorithm for that. What I have to do with the input sequence so that the data are transformed through discrete sine fourier transform? Adding the zeroes, I think?

FFTW can do this using certain options: RODFT00, etc. It's probably better to call a library like FFTW than coding it yourself unless you have very special needs.
An alternative to FFTW could be using Intel MKL (mkl_trig_transforms.h, in particular). Various trigonometric transforms are implemented there, and, in addition, using the wrapper interface to FFTW3 is also possible.