Слив засчитан, и да вася, когда ты пытаешься кого-то уличить знай, что ты обосрёшься

я знаю что ты не можешь решить школьную задачу.

https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm - что из этого. Ладно я уже не прошу реализацию - я прошу хотябы конечный алгоритм.

возьми этот. он самый простой. но на простых же числах тормозит.

Просил рисовалку же.

Рисовалку, да, с кодом и без заморочек.

Если без освещения, просто каркасами — сделай простейший 3D вид с камеры на разные объекты своими средствами (т.е. использовать стороннего только вывод готовой картинки) с анимацией и контролем движений, вращений и т.п. всего и вся, через матрицы, тригонометрию, кватернионы.

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

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

Какбэ анимация на 2дпиксмапе тоже рисовалка, только без заморочек.

Но так тогда без перформанса

И зачем оно мне надо?

чисто для демонстрации всех этих вещей

Я не пишу лабу/зачётку - мне это не интересно.

чтобы упереться в рисовалке это нужно что-то особого делать, для чего нужно разбираться.

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

Мне интересна постановка задачи вида: входны и исходящие данные, а между ними конкретная формула, которую мне надо реализовать, причём оптимально. Если мне понадобятся какие-то трансформации - я разбирусь в том, что мне нужно.

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

У меня нет цели ваять какой-то там новый рендер убицу чего-то. Чем один материал отличается от другого? Ничем, коэффициентами в формулке отражания или что там у вас. Чем отличается один шарик от кубика - ничем, формулкой пересечения, либо что там у вас.

Есть что-то такое, где есть основная вычислительная идея без всех этих заморочек? Именно для этого мне и нужен код. Безо всяких заморочек уровня реализации, аля это самое монтекарло, смысла которого я так и не понял. Мб ты мне объяснишь?

Я про DFT не говорил...

Я чет промазал - это было анонимусу, прости.

я знаю что ты не можешь решить школьную задачу.

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

возьми этот. он самый простой. но на простых же числах тормозит.

Почему тормазит, чем они отличаются?

Зачем мне простой, когда мне нужен юзабельный, чтобы я знал куда копать.

в чем конкретно ты меня уличил?

в анскильности. ну и про брутфорс ты мощно зарядил.

Почему тормазит, чем они отличаются?

чтобы понять надо разобраться как он работает.

Зачем мне простой, когда мне нужен юзабельный, чтобы я знал куда копать.

этот очень даже юзабельный. я бы сказал самый популярный.

Не, не, то что там перечислено для «просто каркасами» это детский сад, то есть пишется в мизер кода плюс дальше по желанию. Никакого освещения, монтекарло (хотя упомянутое вычисление pi им — тоже задачка) и материалов. На входе сцена в 3D (массив — точки и их связи), на выходе проекция в перспективе, т.е. плоская картинка, потом в цикле объекты на сцене плавно трансформируются в 3D, а плоская проекция пересчитывается (на выходе такой-то fps). На конкретные формулы ссылки были. Но если тебе не нужна вся эта базовая тригонометрия и линейка (не как запил по-поцански, а чисто как они есть в своей простоте), то забей, ок.

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

Понимаешь в чем штука, хорошо, что ты знаешь много умных слов, но мне они ни о чем говорят.

Я вот уже со многими говорил, но почему-то никто не осиливать описать задачу, т.е. считалку. Считалка - это безликий набор чисел - считалке насрать на гармоники, спектральное представлении и прочее.

Есть набор данных и есть операции над ними и все оптимизации уже строятся исходя из этих самых операций, а не исходя из «суперпозиции гармоник».

Это всё нужно в вузе на паре, вернее на лабе/зачетке, либо когда ты решаешь уже задачи какие-то по теме. Т.е. тот же спектральный анализ и тогда дпф для тебя просто его смысл коррелирующий с твоей задачей.

Из википедии я уже выяснил, что численный/вычислительный смысл дпф - это сумма всех входящих значений помноженных на коэффициент. В дпф - это степень экспоненты или как там называется e^n, а дкт косинус, с аргументом:

Зависящим от веса шага(т.е. какая часть от N содержиться в одном шаге) по сумме и помноженный на номер элемента по данным.

Т.е. примитивная таблица с линейным ростом. Т.е. коэффициент для каждого шага просто предущий * 2. Естественно отсюда даже я понимаю откуда взялось бпф, ибо эта сумма нихрена не уникальна.

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

в анскильности. ну и про брутфорс ты мощно зарядил.

Я и не говорил, что у меня есть скилл в решании школозадачек, т.е. не уличил.

А про брутфорс я прав, ибо моя формуллировка не решается не брутфорсом.

чтобы понять надо разобраться как он работает.

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

этот очень даже юзабельный. я бы сказал самый популярный.

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

Понимал бы я хоть что-то в ваших методах и свойствах синусов/экспонент - я бы сам вывел это бпф, но я рак. И какбэ 5лет осиливать вузовскую программу у меня нет. Я потихоньку буду ещё осиливать, но пилить надо щас.

Ты мне дай ссылку, либо напиши пж - как они находят следующую сумму по текущей.

Ты понимаешь, что для решения любой задачи, имеющей практическое назначение (а не говна какого-нибудь учебного), нужно иметь знания?

А у тебя знаний нет. Как ты, скажем, без знания физики, матана и прочих вещей будешь что-то делать? Только пыхпыхерством страдать разве что.

Прочитай ешё http://practicalcryptography.com/miscellaneous/machine-learning/intuitive-gui....

Посмотри http://toxicdump.org/stuff/FourierToy.swf, частоты восстанавливаются прямым преобразованием, сигнал — обратным. Экспонента комплексная, так что комплексная плоскость слева.

Был пример про JPEG.

Как http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms (оттуда же http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf) получается из суммы дающей корреляцию написано всё там же http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm#The_radix-2_DIT_case.

А про брутфорс я прав

это само собой разумеется :) просто мне понравилось твоё «определение» брутфорса

Я итак пойму как она работает без математики - она работает с числами, на уровне арифметики

условно говоря, «без математики» и «на уровне арифметики» работает д(дискретное)пф. и сколько бы ты его не надрачивал оно всё равно будет тормозить. потому что асимптотическая сложность — o(n*n). чтобы сделать из дпф б(быстрое)пф нужен матан. в данном случае довольно примитивный и хорошо известный каждому программисту. тогда сложность будет o(n*log(n)). ещё более сложный матан доказывает, что быстрее нельзя посчитать в принципе (но ты можешь, я знаю... достаточно переформулировать задачу по-своему).

выполняет задачу наиболее вменяемо.

мне трудно судить что именно ты считаешь вменяемым... если самое быстрое решение на x86, это fftw. под капотом там модифицированный сильным матановым колдунством cooley-turkey, плюс что-то из prime-factor алгоритмов для некоторых случаев. плюс ручная оптимизация малых выборок (ботаны уже для 64 отсчётов вручную нахардкодили; не уверен что именно в fftw), плюс правильное раскладывание по памяти и строкам кеша, плюс хитрожопые преобразования данных чтобы там съэкономить одно умножение, а там — одно сложение и т.д.

короче, не зря там такая хренова гора кода.

но правильные пацаны сегодня считают дпф исключительно на видеокартах.

он хочет «вменяемый» (видимо, самый быстрый из известных) алгоритм, реализация которого занимает не больше пары сотен строк.

потом обмажет его инстринсиками и запостит сюда насколько быстрее у него получилось. что-то вроде этого тс называет «задачей».

ну это если он вообще осилит...

http://rosettacode.org/wiki/Fast_Fourier_transform, там и обратное тоже.

так толсто что аж тонко...

вчера тс уже mit-овский код говном облил...

Ты понимаешь, что для решения любой задачи

Ало, вася - я не решаю задачи. Задачи решают математики - я пишу к ним реализации. Задача меня не интересует - я пыхпыхер.

Связанно решение с матаном только одним образом - это постановка задачи. Всё. Ставиться задача, любая(которую надо вылислить) на уровне арифметики.

нужно иметь знания?

Знания которые нужны для реализации почти в этом мире у меня имеются.

Как ты, скажем, без знания физики, матана и прочих вещей будешь что-то делать?

Зачем они мне нужны? Я не решаю задачи, которые решает матан и физика - я лишь пишу реализации.

Мне нужна дискретная формула - всё. На основании какого матана её вывели - мне не интересно.

просто мне понравилось твоё «определение» брутфорса

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

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

условно говоря, «без математики» и «на уровне арифметики» работает д(дискретное)пф

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

и сколько бы ты его не надрачивал оно всё равно будет тормозить.

Зачем ты пытаешься нести херню?

чтобы сделать из дпф б(быстрое)пф нужен матан

Нет, матан нужен чтобы вывести бпф.

но правильные пацаны сегодня считают дпф исключительно на видеокартах.

Я не собираюсь их считать, я собираюсь их пилить.

он хочет «вменяемый» (видимо, самый быстрый из известных) алгоритм, реализация которого занимает не больше пары сотен строк.

Там итак не больше пары сотен строк. Если ты не осиливаешь это понять - мне тебя жаль.

вчера тс уже mit-овский код говном облил...

А он не говно? Ты мне скажи, пж, в каком веке считали кол-во умножений? Я уж не знаю - годах в 80-х.

Т.е. портянка и компетентность пацана её написавшую осталась в 80-х, т.е. все его ухищрения с подстчётом умножений не имеют смысла.

потом обмажет его инстринсиками и запостит сюда насколько быстрее у него получилось. что-то вроде этого тс называет «задачей».

Ещё раз, вася, начнём с того, что ты даже этого не осилишь, а продолжим тем, что ТС считает выполненной задачей то, что обоссывает всё ныне существующие. Это уже давно пора понять.

Она выдаёт такие же результаты как fftw?

на уровне реализации - сортировка это набор подзадач.

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

Нет, на уровне арфиметики работают любые численные методы

ну что же, накормим тебя говном ещё раз... реализуй дфт по формуле (eq. 1) отсюда: http://en.wikipedia.org/wiki/Discrete_Fourier_transform и сделай так чтобы это было быстрее чем по ссылке motto (одна из самых тормозных реализаций со сложностью o(n*log(n))). вперёд, балаболка.

Там итак не больше пары сотен строк

придётся и здесь тебя слить. давай ссылку на код самого быстрого алгоритма, которая занимает эту самую пару сотен строк.

Ты мне скажи, пж, в каком веке считали кол-во умножений?

в 21-м.

начнём с того, что ты даже этого не осилишь

у тебя и пруф есть? задача-то твоя. зачем мне её «осиливать»?

ТС считает выполненной задачей то, что обоссывает всё ныне существующи

мы уже который месяц всем лором ждём...

Они вычисляют правильные, то есть приближение exp(-2 pi i k 0 / 8) + exp(-2 pi i k 1 / 8) + exp(-2 pi i k 2 / 8) + exp(-2 pi i k 3 / 8) или 1 + сos(pi k / 4) + cos(2 pi k / 4) + cos(3 pi k / 4) и -(sin(pi k / 4) + sin(2 pi k / 4) + sin(3 pi k / 4)) или [4, 1, 0, 1, 0, 1, 0, 1] и [0, -1 - sqrt(2), 0, 1 - sqrt(2), 0, -1 + sqrt(2), 0, 1 + sqrt(2)].

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

Нет, ибо в отличии от тебя в это понимаю и херню не несу.

ну что же, накормим тебя говном ещё раз... реализуй дфт по формуле (eq. 1) отсюда: http://en.wikipedia.org/wiki/Discrete_Fourier_transform и сделай так чтобы это было быстрее чем по ссылке motto (одна из самых тормозных реализаций со сложностью o(n*log(n))). вперёд, балаболка.

С чего я должен реализовывать дпф, ты серанул и пытаешься как-то выехать?

К чему ты высираешь сюда это говно? Ты мне хочешь решить бпф не 4-мя операциями?

Ещё раз, зачем ты продолжаешь нести и нести херню? Ты надеешься меня взять на понт и съехать с темы? Жалкая попытка свести тему разговора, типа я не согласен, что бфп быстрее дпф или на что ты надеешься?

придётся и здесь тебя слить. давай ссылку на код самого быстрого алгоритма, которая занимает эту самую пару сотен строк.

Вперёд, дай код самого быстрого алгоритма не на пару сотен строк.

у тебя и пруф есть? задача-то твоя. зачем мне её «осиливать»?

Да, ты слишком нулёвый. Но я тебя хвалю - ты мне помогаешь.

мы уже который месяц всем лором ждём...

Чего конкретно ты ждёшь?

Давай так - ты сказал, что http://rosettacode.org/wiki/Fast_Fourier_transform - норм и рабочая, только тормазная. Дак вот я тебе попрошу только одно - дай мне код, который юзая fftw, либо что-либо ещё, которое самое быстрое на цпу, ну вроде ты сказал ффтв - выдавал такие же результаты.

Т.е. функция f(cmplx * in, cmplx * out, int len), как по ссылке.

Они вычисляют правильные

Дак результаты одинаковые или нет?

Ничё не понял

exp(-2 pi i k 0 / 8) + exp(-2 pi i k 1 / 8) + exp(-2 pi i k 2 / 8) + exp(-2 pi i k 3 / 8) - ну это фрде из формулки.

1 + сos(pi k / 4) + cos(2 pi k / 4) + cos(3 pi k / 4) и -(sin(pi k / 4) + sin(2 pi k / 4) + sin(3 pi k / 4))// это как я понял, что exp() - это cos() + sin()

[4, 1, 0, 1, 0, 1, 0, 1] и [0, -1 - sqrt(2), 0, 1 - sqrt(2), 0, -1 + sqrt(2), 0, 1 + sqrt(2)].//щито это? почему sqrt(2)?

В 20 и 21 веке на уровне реализаций под универсальную железку(собственно под которую пацан и пишет на сишке) умножение == сложение, а умножение + сложение < умножение. Представляешь себе, да? Т.е. уменьшать кол-во умножений за счёт сложений уже лет 20 как не имеет смысла, разве что для хадварных реализаций и чисто форфан.

С чего я должен реализовывать дпф

те же «4 операции», тот же конечный результат. что не так?

Ты мне хочешь решить бпф не 4-мя операциями?

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

Ещё раз, зачем ты продолжаешь нести и нести херню?

объясняю. я кормлю тебя говном по причине твоей анскильности. а ты забавно чавкаешь.

дай код самого быстрого алгоритма

возьми fftw для x86. может что-то быстрее и есть, но об этом мало кто знает. я, например, не знаю.

Да, ты слишком нулёвый.

значит пруфа у тебя нет. слив засчитан.

Чего конкретно ты ждёшь?

где-то полгода назад у тебя должен был быть готов скильный компилятор лоя правильной сишки, например

умножение + сложение < умножение. Представляешь себе, да?

хочешь меня удивить?

уменьшать кол-во умножений за счёт сложений уже лет 20 как не имеет смысла

можешь мне не напоминать что ты ничего не понимаешь в погрешности вычислений.

речь о другом. было 112 сложений+умножений на обсчёт блока данных, стало — 110. как они это нашаманили — есть статья на fftw.org. результат, разумеется, тот же.

Ну мне нужна фигня тормазная и не торамзная, которая выдавала одинаковые результаты.

И вот у меня будет задача запилить из тормазной быстрее не тормазной. Всё просто.

хочешь меня удивить?

Нет, хочу чтоб ты не нёс херню.

можешь мне не напоминать что ты ничего не понимаешь в погрешности вычислений.

Пацан приравнивает бпф к дпф и ещё что-то говорит об погрешности.

речь о другом.

Это называется уменьшение кол-ва операций в целом, но везде кукарекается про уменьше умножений за счёт сложений и прочего.

было 112 сложений+умножений на обсчёт блока данных, стало — 110.

Это не гарантирует буст производительности.

как они это нашаманили — есть статья на fftw.org. результат, разумеется, тот же.

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

Т.е. функция f(cmplx * in, cmplx * out, int len), как по ссылке.

возьми здесь: http://fftw.org/fftw3_doc/Complex-One_002dDimensional-DFTs.html#Complex-One_0...

те же «4 операции», тот же конечный результат. что не так?

К чему ты это кукарекнул.

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

Ну зачем ты вася, о5 несёшь херню. В х86 нету ничего, кроме протухшего фпу говна. Есть только корень.

объясняю. я кормлю тебя говном по причине твоей анскильности. а ты забавно чавкаешь.

Да кого ты там кормишь. Вот выкати мне 2 функции(одну можешь не выкатывать - она есть.) f(cmpl in, cmplx out, int N) на fftw, которая бы выдавала такие же результаты, как и «тормазная функция по ссылке пацана». Пж.

Пацан приравнивает бпф к дпф и ещё что-то говорит об погрешности.

как одно связано с другим?

рассуждения о сложениях и умножениях не имеет смысла - есть операции

это если пофигу на точность результата. тебе, впрочем, не понять.

Ну блин, если fftw тоже считает правильно (я полагаю), то одинаковые. Они все одинаковые — DFT это функция, результаты известны наперёд аналитически (три формулы это одно и то же, 1) определение, 2) Эйлер, exp(ix) = cos(x) + i sin(x), да 3) ну вот так http://en.wikipedia.org/wiki/Trigonometric_functions), значение может быть непредставимо конечной последовательностью бит в бинарном представлении и быть иррационально — алгоритм будет приближать с некоторой точностью (если он детерминированный, то специфицируется некоторой аппроксимирующей функцией).

умножение == сложение

кто тебе такую чушь сказал? или у тебя особый пацанский процессор?

fftw тоже считает правильно (я полагаю)

некоторые реализации нормализуют по sqrt(1/n)

Как и http://reference.wolfram.com/language/ref/Fourier.html, например. Забыл дописать, что надо знать а что там вообще считается, для начала :)

ну дык погрешность обратного преобразования :) в математике с этим строго

как одно связано с другим?

Не ассоциативностью фп + не факт, что твоё слияние выдаёт начальную точность, скорее всего плывёт.

это если пофигу на точность результата. тебе, впрочем, не понять.

Как это связанно - пример, а так кукарекать «тебе не понять», может любой питух.

кто тебе такую чушь сказал?

Матчасть. Берёшь мануал и читаешь.

или у тебя особый пацанский процессор?

С тех самых пор, как в процессор впихнули пайплайн. На текущем штеуде трупут сложения в 2раза меньше трупута умножения. Т.е. add - 1штука за такт, а mul - 2штуки за такт. Я уже писал про это, правда есть нюансы и это обходиться.

Чем на видяшках похоже одни нули пишут, ибо нормально описания архитектуры и трупута их кудавёдер я не нашел, только говноупоминание в http://docs.nvidia.com/cuda/cuda-c-programming-guide/#arithmetic-instructions - тоже самое.

Забыл дописать, что надо знать а что там вообще считается, для начала

Зачем? какая разница?

Чёт твой линк, вольфрам и ффтв выдаёт совершенно разные результаты.

FFT : (4, 0) (1, -2.41421) (0, 0) (1, -0.414214) (0, 0) (1, 0.414214) (0, 0) (1, 2.41421) 

fftw: (8, 0) (0, -3.14018e-16) (0, -4.44089e-16) (0, -3.14018e-16) (4.44089e-16, 0) (8, 3.14018e-16) (8, 4.44089e-16) (8, 3.14018e-16) 

http://www.wolframalpha.com/input/?i=Fourier[{1%2C+1%2C+1%2C+1%2C+0%2C+0%2C+0%2C+0}%5D

Ничего не понятно.

Спасибо, странно почему у меня не работало, зря я поверил в: If you have a C compiler, such as gcc, that supports the C99 standard, and you #include <complex.h> before <fftw3.h>, then fftw_complex is the native double-precision complex