Накидайте задачек.

Чет твоя фигня всего в 25раз быстрее - http://rosettacode.org/wiki/Fast_Fourier_transform#C этого говнища. Чёт не особо челендж, ну да ладно.

Нужно http://rosettacode.org/wiki/Fast_Fourier_transform#Mathematica (http://reference.wolfram.com/language/ref/Fourier.html, он делит, можно умножить на sqrt(8), но ещё знак остаётся поменять у экспоненты), как через wolframalpha задать параметры я не знаю.

    static fftw_complex in[N] = {{1, 0}, {1, 0}, {1, 0}, {1, 0}};
    static fftw_complex out[N];
    // ...
    fftw_plan p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
    // ...
    for (int i = 0; i < 8; ++i)
        printf("%f %f\n", out[i][0], out[i][1]);

смотри чтобы было выравнивание как там хотят и FFTW_MEASURE, потом замерять fftw_execute.

FFTW_MEASURE

С ним оно так же тормазит как реализация из твоей линки.

потом замерять fftw_execute.

С какого это хрена?

Вообще нужно целую серию для разных N запускать и смотреть. Древний бенчмарк:

http://www.sharcnet.ca/~merz/CUDA_benchFFT/ (vs http://docs.nvidia.com/cuda/cufft/index.html)

там цикл по возрастанию N (N^2, N^3 для 2d и 3d) в котором 1) аллокация памяти на вход и выход (можно просто взять статически одну на всё, с выравниванием), 2) инициализация плана (FFTW_ESTIMATE или FFTW_MEASURE, in-place или out-of-place) _до_ инициализации данных (т.е. выше неправильно и оно только за счёт FFTW_ESTIMATE ок), 3) инициализация данных, 4) цикл с fftw_execute который измеряется чтобы получить mflops внешнего цикла (то есть для данного N), 5) освобождение плана и памяти (ненужно, если статически) и следующая итерация N.

+ вариант с параллелизмом потоками.

В итоге вывод в том, что для больших N GPU таки может быть лучше (это не только там такой вывод).

Вообще нужно целую серию для разных N запускать и смотреть.

Не имеет смысла. Тут нет особых причин для смены производительно для разных N.

аллокация памяти на вход и выход

Внешняя аллокация не учитываеться.

4) цикл с fftw_execute который измеряется чтобы получить mflops внешнего цикла (то есть для данного N)

Нет, задача измеряется полностью, а не мистическим говном. Т.е. от измеряется функция - на входе данные - на выходе данные. Какой жопой там он это делает меня не интресует. Частные случаи мериются отдельно.

Я понимаю, что таблицу експонент можно предрасчитать и потом накручивать, только толку?

5) освобождение плана и памяти (ненужно, если статически) и следующая итерация N.

Не измеряется. Плана измеряется.

В итоге вывод в том, что для больших N GPU таки может быть лучше (это не только там такой вывод).

Датычё, датычё. А ты понимаешь, что это дабл? х86 стоит 300баксов, а видяшка 3к+ баксов - такое прям ахриненное сравнение.

Кстати, пацаны в fftw запилили примерно то, что хочу сделать я. У них сам гинератор шедулит инструкции, что собственно я и делаю. Правда он днище, но всё же.

Значит я не одинок в своих идеях. Молодцы, вы мне нашли фигню даже, где это есть. Я вас хвалю.

Ну что там, забрали царя в армию? Когда шампанское открывать?

Ну что там, забрали царя в армию?

Зря ты так. Вернется оттуда императором.

С БПФ видюха реально лучше даже на небольших объемах данных (я проверял с изображениями 1000х1000). Проблема в том, что БПФ требует больших объемов оперативки → для более-менее серьезных вещей (скажем, фильтрация изображения 4000х4000 с реализацией свертки посредством БПФ) может потребовать 1 и больше ГБ оперативы на видюхе (у меня в некоторых вещах 2ГБ не хватало), т.е. видюху придется брать недешевую. Но учитывая то, что в среднем выигрыш не такой уж значительный (ну, 1-3 секунды, например), можно и потерпеть на CPU с fftw3.

То ли дело — задача, требующая миллиардов итераций, где вычисления сами по себе не такие уж и сложные. Ее, ясен пень, лучше распараллелить на видюхе. Правда, тут тоже желательно подороже брать видюху, где GPU'шных ядер побольше.

Уж не помню, давно это было, но на некоторых вещах недорогая видюшка, купленная пару лет назад за 3000 рубликов, давала выигрыш по времени на 1-1.5 порядка по сравнению с openmp.

Царя не забирают в армию, а открывать заватра-послезавтра.

Ты пытаешься спорить с очевидными вещами (нет разницы для разных N, ога). Расчёт производит fftw_execute, fftw_plan_dft_1d не знает про in, она знает про параметры и N и подбирает экспериментами оптимальный алгоритм из множества (потому что N таки имеет значение, ну и параметры тоже), потом с планом можно считать сколько угодно fftw_execute для разных in (для данного N и параметров, ты попробуй). Вывод — для данного N нужно крутить fftw_execute (разные или одни и те же in) и измерять это дело. Вывод 2 — если всё равно упираешься и не видишь что написано в доках, то крути fftw_plan_dft_1d + fftw_execute для данного N, первый раз fftw_plan_dft_1d задумается, потом будет реюз и ты получишь небольшой вклад в результат, так что это и не важно. Но для разных N нужны разные оценки производительности, то есть как графики по ссылке (и в других местах) в итоге, если и тут упираешься, то всё равно делай для разных N и доказывай что нет разницы.

И я ничё, опять — тестируй FFTW, cuFFT, что-то своё на CPU и GPU (на amd есть туториал про FFT) и показывай бенч по разным N.

открою тебе 2 страшные тайны:

1. сложность бпф по памяти == o(n)

2. его можно считать по месту

царя слили. так я и думал.

Царь, я не понял, а че ты Plan 9 не пилишь? Вот это самый что ни на есть царский проект, как деды завещали, и пилить дам дофига чего есть. А то покукарекать ты горазд, по-царски тебе надо, но при этом чтобы анимешечку посмотреть, в дотку поиграть и на лоре пофлудить. Короче, или ты идешь пилить Plan 9, или ты лох последний, а не царь.

Царь, я не понял, а че ты Plan 9 не пилишь?

Патамучто говно. Царю не нравится копаться в коде посредственностей и пилить бесполезную маргинальную универсальщину.

Вот это самый что ни на есть царский проект

Да говно проект - я смотрел. Я уже искал царские ОС - одно говно.

как деды завещали, и пилить дам дофига чего есть.

А зачем? У меня есть пробелы в операционостроении, но с таким же успехом я могу попилить и линукс, пока не особо интересно, ибо нахрен не нужно.

А то покукарекать ты горазд

Я горазд и попилить, правда а) у меня не особо есть время, б) я не люблю пилить бесполезный мусор, а мне интересно решать конкретные задачи, а не ваять либы для домохозяек - для этого есть такие же домохозяйки.

Да и я же не просто кукарекаю - я учусь. Всё ровно хоть тут 99% малоквалифицированных балаболов, но в чем-то их знания сильнее моих. Да и мне интересно кукарекать - я всю жизнь не кукарекал и вообще не умею говорить, а так авось научусь. Мне нужно социализироваться.

но при этом чтобы анимешечку посмотреть

Да нечего смотреть - я уже всё посмотрел. За год авось тайтлов 5-10 набирается. Мне лень искать, а жена смотрит сопливый мусор и кидает меня.

в дотку поиграть

Дотка мертва уже сотню лет, да и мне лень играть. Все игры говно. Иногда меня питушок склоняет поиграть в лолапарашу «чалик апнуть», но моя жопа этого цирка не выдерживает и меня хватает на неделю, а когда этот ублюдок трансфернул аки на рашку - мою жопу окончательно разорвало после недели мучений - я забил.

Короче, или ты идешь пилить Plan 9, или ты лох последний, а не царь.

Да не пойду я пилить мусор. Что оно мне даст? Копаться в коде написанным левой ногой некомпетентной обезьяны?

Мне интересно пилить считалки - я занимаюсь в основном этим. Проблема в матаноязыке, который нахрен не нужен и котого я не знаю, но пацаны не умеют говорить по другому. Я уже пытался, но за рамки своих абстракций пацанчик выйти не осиливает. Я пытался им показать реальный мир, но это слишком сложно для них. Ну и я как наиболее способный из набора «я и пацаны» - решил пожертвовать, изучая их язык.

Потихонечку буду учить - потихонечку пилить.

Короче, ясненько, у лоха мозгов не хватает оценить царские ОСи. Лох будет пилить говночислодробилки для бюджетных заедушных обезьян. А мог бы сидеть в Microsoft Research и творить будущее.

9-классник

жена смотрит сопливый мусор

Иногда меня питушок склоняет поиграть

Мне одному кажется что что-то здесь не так?

Он же где-то в трущобах живет, они там в 15 лет уже с двумя детьми и тремя судимостями.

Нужны какие-то не особо замороченные задачки активно юзающие тригонометрические функции, желательно с каким-то легко проверяем результатом. С кодом.

А Царь то! Не настоящий! ;)

Царь на чужой код только плюётся и математикой руки не испачкает. :)

Он же так и говорит всем, вы мне мол переведите со своего матана на сишку, опишите структуры там, алгоритмы, а я буду сидеть и критиковать: вот там пробел лишний - не по стандарту, там комментарий не выровнен - неэстетично, ну и названия функция и переменных чтобы понятные были, не матан там всякий, а про петухов что-нибудь, по-пацаночке.

Короче, ясненько, у лоха мозгов не хватает оценить царские ОСи.

Что в этой оси царского, кроме ущербности кода и тормазов?

Лох будет пилить говночислодробилки для бюджетных заедушных обезьян.

Для обезьян.

А мог бы сидеть в Microsoft Research и творить будущее.

Я лучше буду сидеть на помойке и жрать говно, чем очернить себя такой чернухой. Это примерно как заявлять притензии на трон, а потом уйти творить будущие, метя двор метлой.

Можно мне поглядеть на плоды «трудов» этой тварилки?

Мне вот интересно, зачем ты записываешь в мои цитатки то, чего я не писал? Даёшь мне лишний повод макнуть тебя в говно? Про 9-тиклассника можно узнать подробней, откуда ты это спастил?

Мне одному кажется что что-то здесь не так?

И что же - удиви.

Царь на чужой код только плюётся и математикой руки не испачкает.

Ну дак это задача царей - учить плебеев. Ты реально думаешь, что кто-то со способностями выше посредственности будет сливать их на реализацию уровня заедушной пхп обезьянки?

Мир так устроен - одни орудуют лопатой - другое решают глобальные задачи развития лапатаносцев.

А Царь лопаты подаёт? ;)

Он же так и говорит всем

Зачем ты пытаешься это кукарекать, на что надеешься, что я не пошлю искать мне источник цитаты? Ну дак я тебя посылаю, а ты обсираешься.

вы мне мол переведите со своего матана на сишку

Источник.

опишите структуры там

Источник.

алгоритмы

Источник.

а я буду сидеть и критиковать

Источник.

вот там пробел лишний - не по стандарту

Источник, хоть один примеры критике такого порядка.

ну и названия функция и переменных чтобы понятные были

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

не матан там всякий

Конкретней.

а про петухов что-нибудь, по-пацаночке.

Источник.

Ну да, нули, которые обосрутся-то лопату поднять копают, а кмс по копке подаёт лопаты.

Понимаешь, суть царя в том, что он способен делать любую работу доступную плебею лучше плебея. Царь превзойдёт тебя в любом направление за минимальное время.

А от тебя я пока услышал только «что ты вырыл», когда сам нихрена не вырыл и единственное, что пацан может предоставить «я помогал рыть отхожие ямы под сортиры пацанам, а даже их я не покажу» и всё. Своего ничего нет. Да ладно - что-то это дело наживное. Царь подходит к балаболу и говорит - пошли выкопаем что-то, кто лучше? Нет, балабол всегда обосрёться. Зато копатель он первоклассный, ха-ха-ха я сослил, царь лопатки подаёт, как сишно - ха-ха.

А так единственное дело в котором пацаны обходят царя - это лизание жоп за еду. Молодцы - вперёд.

Да, не барское это дело! Особенно, когда не знаешь с какой стороны лопату ту брать то. ;)

Ладно, меня уже радует, что ты «снизошёл» до просьб о помощи в обучении.

Не закидывай матан — он тебе ещё пригодится!

Ладно, меня уже радует, что ты «снизошёл» до просьб о помощи в обучении.

Собственно снизошёл до этого я с появления на лоре. Я никогда не отрицал, что балабол полезен. Любой балабол несёт в себе частичку опыта, а т.к. суммарный опыт превышает мою жизнь в миллионы раз, то даже частичка его, даже учитывая крайне посредственные способности балабола может быть полезна.

Не закидывай матан

Вот ты запастил пасту, а самое смешное знаешь что? Её ваял нуль, который всязал херню никак не связаную с матананом с матаном. Т.е. уже бесполезный для мира мусор, хотя за еду драить сортиры может.

Точно так же пойдут драить сортиры и «матанамены» комнатные, которые это постят в интернетах. Писать маткор будет илита, знания которой намного за пределами примитивного школокурса, который типа «матан». За еду в вебчик/гуйню. От там их матан проявляется - ой как проявляется.

Мамин ривалюцеанер подрастает.

Напиши длинную арифметику произвольной длины. gmplib эталон. Не заморочено. Легко проверяется. С кодом - тысячи его. Не сложно - те самые 4 операции. Ну и сделать лучше gmplib вполне себе челлендж.