Вообще свободные реализации БПФ есть, на вскидку: fftw и fftpack.
fftpack - на фортране.
В свое время пользовался вот
такой реализацией. Это стандартное комплексное БПФ. Собирается без проблем (math.h, конечно должен у вас работать или сами реализовывайте sin и cos). Правда там используются 2 разных массива для действительной и мнимой части, тогда как сейчас используют структуру для представления комплексных чисел. Но это, я думаю, легко поправить.
И на счет ваших проблем с math.h не очень ясно. Думаю в любом случае нужно с ними разобраться.