Step one, download the source.
Step two, install a bunch of libraries which will allow you to compile it:
sudo apt-get install libaudiofile-dev libaudiofile0 libvorbis0a libvorbisenc2 libvorbisfile3 libfltk1.1 libportaudio0 libportaudio2 libportaudiocpp0 libmad0 libfftw3-3 fluid g++
Update
Here's the full list of stuff I installed when I was trying to get this compiled.Bit of a scatter-gun approach really, I probably didn't need them all, but it helped me get it compiled:
sudo apt-get install libmad0-dev libmadlib-dev libibmad-dev
fftw-dev fftw3-dev libfftw3-dev mffm-fftw-dev portaudio19-dev libaudiofile0 libvorbis0a libvorbisenc2 libvorbisfile3 libfltk1.1 libportaudio0 libportaudio2 libportaudiocpp0 libmad0 libfftw3-3 fluid g++
Step three, unpack the downloaded file :
tar jxvf paulstretch-2.0.tar.bz2
Step four, edit a file in the source:
cd paulstretch-2.0/Input
vim MP3InputS.cpp
add the following just after the line that says :
#include <stdlib.h>
this is near the top of the file. Add this line:
#include <string.h>
Step five, compile.
Go back to the paulstretch-2.0 directory:
cd ..
compile:
./compile_linux_fftw.sh
You should end up with an executable file called:
paulstretch
Have fun!