Быстрое преобразование Фурье (халява)

[psilogic]

Все-таки Википедия рулит. Надыбал там то, о чем давно мечтал:
математические выкладки, позволяющие делать преобразование Фурье за время порядка N log(N). Причем, для произвольного N, а не только для степени двойки.

Поковырявшись с ними, поразбиравшись, пооптимизировав, родил описалово, как, что и почему, а главное - файлец на C++ с готовым работающим модулем, который не требует никаких специальных библиотек.

http://psi-logic.shadanakar.org/fft/fftf.htm

Можете юзать - ибо халява :)

Comments

[odinokov.livejournal.com]

а паскакалем не замутишь? 8)

[psilogic.livejournal.com]

Паскаль ацтой! :o)))
*смущенно* Да и забыл я яго нафик :)

[odinokov.livejournal.com]

ох...
а мне ему ещё детишек учить8))

[cybister.livejournal.com]

Я тож забыл, но далеко не отстой.
Недвано девушка мне сказала что ей потнесли си-ди со скринсеверами,
и там мой скринсевер (кажися фигуры лисажу в3д... что-то типа).
Под винду ! 4.5кб !!!
На Борланд паскакале. (На турбо кажись при навешивании соответствующих либ тоже пахало).Такие вот пирожки.
Если нужно - поищу, где-то валялось.

[ex-neo-is-fl156.livejournal.com]

У меня где-то валялось на паскале. Могу посмотреть, если надо.

P.S. FYI: Счастливые читатели Д. Кнута "Искусство Программирования" т.3. могли реализовывать FFT за O(NlogN) ещё задолго до того, как Википедия появилась на свет ;)

[psilogic.livejournal.com]

Только для числа отсчетов, равного степени двойки. Знаменитый алгоритм Кули-Тьюки. Здесь не о нем.

[odinokov.livejournal.com]

срочности нет, просто интерес8)

[metaclass.livejournal.com]

Перевести что ли на дельфи, все равно ж когда-нибудь понадобится самому...

[odinokov.livejournal.com]

вот и грю8))

[nazarovsky.livejournal.com]

дык это.. а готовую БПФ процедуру использовать и нулями добить до степени двойки религия мешает? :)

[psilogic.livejournal.com]

Если добить нулями до степени двойки, то в спектре получится бордель, а не только те частоты, которые формировали исходный сигнал. :) Попытка синтезировать длительный сигнал суммированием синусоид из полученного набора частот приведет к тому, что будет периодически возникать тишина в том месте, где забиты нули.

В порядке саморекламы...

[sanitareugen.livejournal.com]

dsp-book.narod.ru

Re: В порядке саморекламы...

[psilogic.livejournal.com]

Твою мать!!!!!!!!!!!!!!!!!
Как давно я искал что-нибудь эдакое!!!!!!!!!!

[vorobioff.livejournal.com]

Куда я попал???

[psilogic.livejournal.com]

На процедурку...

[metaclass.livejournal.com]

в 9 строке fft.cpp #include без имени файла.

[metaclass.livejournal.com]

math.h что ли?

[diches.livejournal.com]

Звучит как песня из параллельного измерения ))

[psilogic.livejournal.com]

сплошной профессиональный сленг, да? :)

[kelavrik-0.livejournal.com]

Спасибо, запомнил ссылочку.

[ex-travmatu.livejournal.com]

http://fftw.org/

[psilogic.livejournal.com]

да я знаю
просто лично мне не хватало, чтобы было все в 1 флаконе: теория, прога, бесплатно и на русском

[cunnilinux.livejournal.com]

ща попробуйу :)

[snzstorm-ru.livejournal.com]

Спасибо! ;)

[snzstorm-ru.livejournal.com]

мде... С Билдером быстро забывается, что и как =/